ナンクロ解答

2005/10/23

1. はじめに

(日本語かな文字の)ナンクロ解答プログラムを作成したので紹介する。

プログラムはこちら。 実行には最新かそれに近いバージョンのJava実行環境が必要である。 辞書は含まれていないので,豚辞書ワークショップから豚辞書(第14版)を入手して利用するとよい。

使い方は numcro.txt を参照してほしい。

2. 解法

通常の日本語かな文字のナンクロで使用可能文字は以下の72文字である。

ー, あ, い, う, え, お, か, が, き, ぎ, く, ぐ, け, げ, こ, ご, さ, ざ, し, じ, す, ず, せ, ぜ, そ, ぞ, た, だ, ち, ぢ, つ, づ, て, で, と, ど, な, に, ぬ, ね, の, は, ば, ぱ, ひ, び, ぴ, ふ, ぶ, ぷ, へ, べ, ぺ, ほ, ぼ, ぽ, ま, み, む, め, も, や, ゆ, よ, ら, り, る, れ, ろ, わ, を, ん

文字の種類を表す各番号にこの72文字を片っ端からあてはめていけばよいだけである。 その結果盤上にできたすべての単語が辞書に含まれていれば,その文字の組合せは解であり, 辞書にない単語ができていたらその文字の組合せは解ではない。

問題で使用されている文字の種類を n とすると,可能な組合せの総数は,72Pn = 72 × 71 × ... × (72-n+1) である。 実際には,枝刈りが効くので,完全探索は十分可能である。

このやり方では,辞書にない単語が1つでも使用されていれば解答が求められないことになる。 そこで,辞書にない単語をいくつまで認めるかというパラメータを用意した。 辞書にない単語を許すことにより,辞書に使われていない単語が使用されている問題に対しても解答を出すことができるが,逆に誤りの解答を出す可能性も大きくなる。

また,豚辞書には8文字以下の単語しか含まれていない。 そこで,9文字以上の単語については,辞書と照合せずに,あらゆる単語を正しい単語と認めるということとした。 したがって,もし9文字以上の単語のみに含まれる文字があった場合,その文字は決まらない。

3. ナンクロ3解答結果

豚辞書を使用して,市販のナンクロ問題がどれだけ解けるか試した。問題としては,ニコリ発行のペンシルパズル本「ナンクロ3」を用いた。 問題の内容については,ナンクロ統計の記事も参照してほしい。 この本の問題数は全88問だが,そのうち英語または漢字のものおよび,特殊形状のマスを含むものを除いた83問について解かせた。 結果を図1に示す。

図1 解答個数の分布

このグラフの見方は次の通りである。 まず初めに,すべての単語が辞書に含まれるような解を求めた。 すると,83問中複数解となったものが3問,解が1つのみのものが50問,解が求まらなかったものが30問であった。 次いで,解が求まらなかった30問について,辞書にない単語を1つだけ許すことにして解を求めた。 その結果,30問中複数解となったものが2問,解が1つのみのものが21問,解が求まらなかったものが7問であった。 次いで,解が求まらなかった7問について,辞書にない単語が2つだけ許すことにして解を求めた。 以下同様である。

以上を合わせて,辞書にない単語の数が最も少なくなる組合せを解と見なすと,83問中解が1つに定まるのが78問,複数解となるのが5問となる。

なお,辞書にない単語数を1つも認めない場合に複数解となった問題が3問あるが,これは9文字以上の単語に関してはすべての単語を認めているためであり,決して問題が悪いわけではない。 8文字以下の単語しか含まない辞書を用いる限り,仮に辞書に全ての単語が網羅されていたとしても,解が1つに定まらない問題があるということである。 辞書にない単語を1つ認める場合に複数解となった2問については,まさに辞書にない単語を認めたせいで解が複数となったのであり,9文字以上単語の調査有無とは関係ない。

4. 課題

今回のプログラムでは,探索速度は特に追求していない。 探索速度を向上するには,効率的に枝刈りが効くように探索順序を工夫するとか,辞書をあらかじめ細分化しておくとか,他にもさまざまな工夫が考えられる。 考えてみるとおもしろいかもしれない。

通常のナンクロの問題では,何文字か手がかりのヒントが与えられているのが普通である。 その問題をヒントなしで解かせるとどうなるか。 今回のプログラムでは,規模の小さい問題では解が1つに定まったり複数解となったりであったが,中規模以上の問題では探索が終わらない。 上に書いた探索効率化で何とかなるのかもしれないし,ならないかもしれない。


index