カナオレ解答プログラム

市川　宙  （Gimite 市川）

カナオレというのはペンシルパズルの1つです。ルールはWebニコリを参照してください。

「カナオレ解答プログラム」はこのカナオレの問題から答えを求めるプログラムです。数独と同じく、バックトラックというアルゴリズムを採用しています。方法は簡単で、1から順にとにかく適当に配置していき、うまく行かなくなったら戻って配置を修正する、の繰り返しです。

この方法の難点は、運悪く最初の方で間違った配置をすると、それになかなか気づかずに時間をロスしてしまう事です。大抵の問題は2、3秒も有れば解けますが、ある問題では418秒もかかってしまいました。特に長い単語が有ると、配置のバリエーションがやたらと多いので時間がかかります。

単語を埋める順番を入れ替えたり、明らかに間違った配置に早めに気づかせたりすればもっと高速化できそうです。

プログラムとソースのダウンロード

• GUI版プログラムはWindows Me/2000/XPで動作します。Win98では動作しない場合が有るかもしれません。
• ソースはC++で書かれています。コンソール版のコンパイルにはWindowsとC++コンパイラとBoostが必要です。
• GUI版のコンパイルにはBorland C++ Builder （6推奨）とBoostが必要です。