数独解答プログラム Sudoku と Sudoku2 の概要・使い方について説明します。
アーカイブには以下のファイルが含まれています。
ソースや問題ファイルはすべて Shift-JIS で記述しているので、Windows 以外の環境で利用する場合は適宜文字コードを変換してください。また、同梱のバイナリは Windows 2000 と Windows XP 以外の環境では動作しません。
sudoku.exe, sudoku2.exe はコマンドプロンプトから起動してください。エクスプローラなどからダブルクリックして実行すると、出力後にすぐウィンドウが閉じてしまって非常に悲しい思いをすることになります。
1問をじっくり解くためのプログラムです。起動して
% problem
と表示されたら、キーボードから問題を入力してください。
とにかく 0 から 9 までの 81 個の数字を打ち込めば問題として認識されます。0 は空いているマスを、1 から 9 はそれぞれの数字で埋められたマスを表します。数字以外の文字は全て無視されるので、スペースや改行が途中にあっても構いません。ただし、ドット・ハイフンだけは無視されず、数字の 0 と同様に処理されます。
以下に入力例を示します。
045000000 200009700 300008060 000000970 000030000 062000000 090300004 001400002 000000510
% solution 1 8 4 5 7 6 3 1 2 9 2 1 6 5 4 9 7 3 8 3 7 9 2 1 8 4 6 5 1 3 4 8 5 2 9 7 6 9 5 8 6 3 7 2 4 1 7 6 2 1 9 4 8 5 3 5 9 7 3 2 1 6 8 4 6 8 1 4 7 5 3 9 2 4 2 3 9 8 6 5 1 7 1 solutions found
問題の入力が完了すると、プログラムはその答えを出力します。問題に複数の解があれば、そのすべてを表示し、見つかった解の個数を出力して終了します。たとえ解がいくつあろうともすべてを表示しようとするので、もし終わりそうになければ強制終了してください。また、問題に解がない場合は "can't solve" と出力して終了します。
たくさんの問題を一括して処理するためのプログラムです。コマンドラインから
D:\works\sudoku100>sudoku2.exe sudoku.dat
のように問題ファイルを引数で指定して実行してください。
問題ファイルのフォーマットは基本的に Sudoku のものと同じですが、# 以降の文字は行末までコメントとして扱われ、数字であっても無視されます。また、スペースや改行は読み取りには影響せず、81 個の数字が出現した時点で 1 つの問題として認識されます。もし問題の途中に EOF があれば、そこで読み取りを中断します。
以下に入力ファイルの例を示します。
#this is comment 045000000 200009700 300008060 000000970 000030000 062000000 090300004 001400002 000000510 000300000 001460000 090000800 250000000 080000040 000000063 004000070 000018200 000002000 #end of file
% problem 1 8 4 5 7 6 3 1 2 9 2 1 6 5 4 9 7 3 8 3 7 9 2 1 8 4 6 5 1 3 4 8 5 2 9 7 6 9 5 8 6 3 7 2 4 1 7 6 2 1 9 4 8 5 3 5 9 7 3 2 1 6 8 4 6 8 1 4 7 5 3 9 2 4 2 3 9 8 6 5 1 7 % problem 2 5 6 2 3 8 9 4 1 7 8 7 1 4 6 5 3 2 9 4 9 3 2 7 1 8 5 6 2 5 6 9 3 4 7 8 1 3 8 7 1 5 6 9 4 2 1 4 9 8 2 7 5 6 3 6 2 4 5 9 3 1 7 8 7 3 5 6 1 8 2 9 4 9 1 8 7 4 2 6 3 5
問題ファイルが正しく読み込まれれば、プログラムは問題ファイルに記録されたすべての問題の解を出力します。もし問題に複数の解があれば、そのうちの一つを表示します。また、問題に解がない場合は "can't solve" と出力します。すべての問題の解を表示すると、プログラムは終了します。
基本はバックトラックによるアルゴリズム（試行錯誤）ですが、以下のアルゴリズムを併用することで高速化しています。
複数の方法を組み合わせることにより、明らかに答えでない組み合わせを探索の早い段階で打ち切ることができると同時に、いちいち答えが正しいかどうかをチェックしなくても、マスが全て埋まれば正答であると判定することができるようになっています。
ちなみに、手元の環境（メモリ1024MB、Athlon64 3200+）で1万個の問題を解くのに掛かった時間はおよそ 3.266 秒でした。
稚拙なプログラム故、どんなバグが混入されているか分かったものではありません。At your own risk で実行してください！