数独解答プログラム

市川　宙　（Gimite 市川）

数独というのはペンシルパズルの1つです。ルールはWebニコリを参照してください。皆さん、1度はやった事が有るのではないでしょうか。

「数独解答プログラム」はこの数独の問題から答えを求めるプログラムです（そのまんま）。バックトラックというアルゴリズムを採用しています。このアルゴリズムは単純です。例で説明しましょう。

1.	まずは端から入れる数字を適当に入れていくぜ。（1、3、5、7、9、4） おっと、これじゃ右上のマスに入る数字がねえ。じゃあさっき入れた4を6にしてみるか。 今度は大丈夫だ。また適当に4、6、5、1、8…。 おっと、また次のマスに入る数字がねえ。その前は8以外は入らねえから、さらに1個前の1を8に変えてっと…。
2.	3.

このように、「うまく行かなくなったら戻って他の数字を試す」を延々と続けると、その内解けます。単純なのであまり効率は良くないのですが、試した中で最も遅い物でも0.2秒で解けます（pentiumIII 800MHzでテスト）。数独では「全体の80%ぐらいまで埋まれば、大抵は上半分ぐらいは正解である」ので、この方法でもそれほど効率が悪くなりません。カナオレやスリザーリンクではそうもいかないので、この方法だとやたらと時間がかかる時が有ります。

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

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