/mushikui_solver

虫食算ソルバー

Primary LanguageC++Creative Commons Zero v1.0 UniversalCC0-1.0

概要

虫食算ソルバーを実装しています。虫食算の問題を標準入力として与えると、それを解いて解を出力します。

虫食算は、足し算や掛け算や割り算の筆算において、いくつかの数値が ⬜︎ や文字で置き換えられたものが与えられ、もとの筆算を復元するパズルです。筆算を復元するためのルールは次のとおりです。

  • ⬜︎ や文字には 0 から 9 までのいずれかの数値が入る
  • 最上位の桁の ⬜︎ や文字には 0 は入らない
  • 同一の文字 (⬜︎ 以外) には同じ数値が入る
  • 異なる文字 (⬜︎ 以外) には異なる数値が入る
  • ⬜︎ にはほかの文字と同じ数値が入ってもよい

下図は、虫食算の例と、その解答を表しています。

(虫食算の問題例)

(虫食算の問題例の解答)

使い方

使用言語

  • mushikui.cpp を C++11 上でコンパイルして実行します。
  • Wandbox 上の gcc 10.1.0 で動作します。

入力

虫食算の入力はリスト 1 のような形式で、標準入力で受け取るものとします。リスト 1 は、上図の虫食算を表しています。

1 行めには、掛けられる数の桁数 と、掛ける数の桁数を記入します。続く 2 行は、掛けられる数の情報と、 掛ける数の情報を表します。その後、筆算の過程を表します。そして最後の行は、筆算の結果を表します。また、虫食算の ⬜︎ に対応するところは文字 * で表しています。

4 3
4*F*
*O*
F*U*
**O*R
**U*
***R***

(虫食算の入力例)

出力

一意解の場合は、たとえば先述の入力例に対しては、以下の結果を出力します。

0 th result:
-----------
4794
232
9588
14382
9588
1112208
  • 解なしの場合は "no solutions." と出力します。
  • 解が複数個ある場合は "more than one solutions." と出力します。

実行例

下図のような超巨大虫食算数に対しても 0.38 秒の計算時間で解くことができます。なお、計算実行環境は、次の通りです。

  • MacBook Air (13-inch, Early 2015)
  • プ ロ セ ッ サ：1.6 GHz Intel Core i5
  • メモリ：8GB

(超巨大虫食算)

アルゴリズム

ソルバーのベースは、深さ優先探索 (バックトラッキング) です。探索順序の工夫や枝刈りなどを行うことで高速化を図っています。詳細については下記の参考資料に書かせていただきました。

参考資料

以下の連載記事に詳細の解説を行っています。

License

These codes are licensed under CC0.

CC0