割と丁寧な数独プログラムについての説明

tondol <hosakanpo@gmx.net>
2007-09-11

0. はじめに

数独解答プログラム Sudoku と Sudoku2 の概要・使い方について説明します。

アーカイブには以下のファイルが含まれています。

sudoku.exe
Sudoku の Win32 用バイナリ
sudoku2.exe
Sudoku2 の Win32 用バイナリ
sudoku.c
Sudoku のソース
sudoku2.c
Sudoku2 のソース
common.c
Sudoku, Sudoku2 の共通ソース
sudoku.dat
Sudoku2 対応の問題ファイル
yomanaito-shinu.html
この説明書

ソースや問題ファイルはすべて Shift-JIS で記述しているので、Windows 以外の環境で利用する場合は適宜文字コードを変換してください。また、同梱のバイナリは Windows 2000 と Windows XP 以外の環境では動作しません。

sudoku.exe, sudoku2.exe はコマンドプロンプトから起動してください。エクスプローラなどからダブルクリックして実行すると、出力後にすぐウィンドウが閉じてしまって非常に悲しい思いをすることになります。

1. Sudoku <全解探索版>

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" と出力して終了します。

2. Sudoku2 <一括処理版>

たくさんの問題を一括して処理するためのプログラムです。コマンドラインから

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" と出力します。すべての問題の解を表示すると、プログラムは終了します。

3. アルゴリズム

基本はバックトラックによるアルゴリズム(試行錯誤)ですが、以下のアルゴリズムを併用することで高速化しています。

  1. 全てのマスについて候補リストを作成し、候補が1つだけならそれに決定。
  2. 行、列、3x3 ブロックのそれぞれで、数字 N が候補に入っているマスが1つしかなければ、そのマスは N に決定。

複数の方法を組み合わせることにより、明らかに答えでない組み合わせを探索の早い段階で打ち切ることができると同時に、いちいち答えが正しいかどうかをチェックしなくても、マスが全て埋まれば正答であると判定することができるようになっています。

ちなみに、手元の環境(メモリ1024MB、Athlon64 3200+)で1万個の問題を解くのに掛かった時間はおよそ 3.266 秒でした。

4. 決まり文句

稚拙なプログラム故、どんなバグが混入されているか分かったものではありません。At your own risk で実行してください!