ナンクロをコンピュータで解く

最近バ先に、ナンクロ(ナンバークロスワードパズル)にハマっている同僚がいる。それを見ていると、これはコンピュータで解けるかもしれないと思うわけだ。究極的には辞書を片っ端から見続けて埋めていけばいいので、コンピュータにはもってこいの作業になるはずだ。しかし、探したところ「ナンクロを解くときに便利な補助ソフトウェア」はあるものの「ナンクロ自体を1から解くプログラム」というのがない。なんでじゃ。

というわけで、ナンクロをコンピュータで解くことを考えよう。

説明用の例を下においておく。これはWikipediaからの引用。

スクリーンショット 2015-08-25 21.54.51

まずはすべての単語になりうる部分をリストアップする。横向きは「2, 4, 1, 3, 4」「2, 4」「2, 2」「2, 5」「5, 3」「1, 3, 2, 5, 3」、縦向きは「2, 4, 2」「2, 5, 3」「1, 2」「3, 2」「3, 4, 2」「5, 1, 3」で、全部で12単語できるはずだ。

つぎに、最初のヒント「トキ」および単語の構成から、最も入れやすそうなものを選ぶ。単語の構成というのは、たとえば「2 2 3 4 3 4」であれば、2がキとわかっている以外にも、6文字の単語なのに2, 3, 4の3文字しか使わないので絞り込みやすい、ということである。この入れやすさを点数にして最も高いものを選ぶとよいだろう。というか実際に解くときもこういうところから埋めるはずだ。

さて、ここでたとえば 2 4 1 3 4 が最も入れやすいと選んだとしよう。つぎにこれを辞書と照らし合わせながら候補を探す。これは単純作業で、5文字の単語で「き○と○○」となり、さらに2文字目と5文字目がおなじになるようなものを探せば良い。辞書によれば「きんとうん」「きんとぎん」が挙がる。

次にこれを試しに当てはめて進める。ここでは間違えたいので「きんとぎん」を当てはめることにする。ここで3にギ、4にンがはまるので、 たとえば縦に2 4 2の部分は「ぎんぎ」、縦に3 4 2の部分は「ぎんき(銀器)」がはまることになる。「ぎんぎ」なんていう単語はないので、これは無効になる。

したがって「きんとうん」が2 4 1 3 4にハマることになる。これで1 3 2 5 3は「とうき○う」となる。辞書によれば「とうきゆう(冬宮、投球など)」「とうきよう(東京)」が挙がる。

などと続けていって決めるわけだ。もし突き進んでみて失敗したら戻って別の候補を選ぶことになるので、再帰的に選ぶことになる。したがって関数の再帰的定義を用いて考えることになる。

つまり、例えば関数searchは

  1. 各列の点数を計算して、埋まっていない中で最も埋めやすそうな単語を選ぶ
  2. 辞書と照合して候補をあげる
  3. 候補に関して foreach
    1. まず埋めてみて、これにより完成した単語がすべて辞書にあるかを確かめる
    2. なければ次の候補を探す
    3. あるならば対応表を更新してsearchを再帰的に呼び出す
    4. searchに失敗したら別の候補を選ぶ
    5. searchに成功したらそのままそれを答えとして返す

という流れで実行すればよいことがわかるだろう。最終的に失敗が返れば、そのナンクロは現段階の辞書では「解けない」ということになる。

これを実際に実装したのを gist にあげてみた。ここでは、たとえば2文字の単語のリストが dictionary/2.txt にリストアップされているものとする。

このリストを作るのが makedic.rb である。これは全単語のリストが書いてあるファイルを読み込ませて使う。テスト時には「豚辞書 ver0.14」もしくは「デジタル大辞泉」にある単語を用いた。実際にはほとんど豚辞書で十分であろう。

このプログラムでは一応解き進めてみて答えが出なくても、一番答えに近づいたであろう解答を出す機能をつけてある。最悪そこから人間の手で解いてもよいからだ。

ここまでは多少考えれば実装できるので、ここから先が問題である。たとえば「知らない単語があっても突き進む」とか「一部漢字のナンクロに対応する」とかである。両方結構めんどうくさそうなので手を付けていないが、暇な人は挑戦して欲しい。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です