[個人用ページ] :
一言 「数独なんてきらい」
初出: 2007/03/20 T.Shirai
更新: 2007/03/20 T.Shirai
流行っているね．数独．以前に携帯電話のアプリケーションをダウンロードして試してしまったため，ルールは知っています．ダメなんですよ，こういうパズルは．キライなんです．アルゴリズムが単純だから，２時間（補注）もあれば（解法プログラムを作成）できちゃいますよ．いままで避けてきたのに．
（補注）デバッグやこれらのファイルを用意するのも入れて３時間くらい掛かりました
ミソは，（１）確定しているマスを元にして数字の候補が一つに絞られるマスを前処理で埋めてしまう．（２）数字の候補が二つ以上のマスは再帰呼び出し（リカーシブコール）を使って推定し，全パターンをバックトラックしながら探す．とてもProlog向きの問題だし，再帰呼び出しの例題としては好適．．．時間が無いはずなのに何しているんだろう．さて，開き直って．
以下にソースと実行形式とサンプルのデータをアップロードしておきます．面倒な人は全て一括でダウンロードして下さい．ウィルスチェックは自己責任で．なお，９×９のみに対応．もっと大きなものにも対応できますが，初期状態の数字を入れるの，面倒ですよね．ソースはC++言語，Borland C++ Builder6のbcc32で開発しましたが，標準関数ばかり使っていますので（getch()を除く），他の環境でもほぼそのままコンパイルできるでしょう．データのファイル（initial.csv）はプログラムと同じフォルダに置いて下さい．エクセルのファイルからinitial.csvを作成するには，保存したいワークシートを選択した状態で，名前（＝initial.csv）を付けて”CSV(カンマ区切り）”形式で保存して下さい．繰り返しますが，このプログラム，Windowsのデスクトップ画面上でダブルクリックしても動きません（データファイルを読めない）．日本語や空白を含まないフォルダ（例． C:\tempなど）を作成し，そこで実行して下さい．
全て： Sudoku.zip
ソースリスト： sudoku.cpp
実行形式： Sudoku.exe （コマンドプロンプトで実行，Windows2000/XP専用）
サンプルデータ： Puzzle01.csv， Puzzle02.csv，Puzzle03.csv，Puzzle04.csv，157.csv （これらをinitial.csvにリネームする）
サンプルデータの素： initial.xls （このファイルに新しい問題を記録してCSV(カンマ区切り)形式で保存する．
実行すると，データファイルを読み込んで，自動的に数字が決まるマスは埋めてしまいます．
これは157.csvの例．自動的に埋まるマスはありませんので，結構難しい問題です．
計算過程の試行錯誤を見てみたいという奇特な方のために，画面出力をテキストファイルに保存したものを用意しました．
結構，長いですよ．（157.txt)
なお，１５７番の問題は，こちらのホームページに掲載されていたものを利用させて頂きました．
キーを押すと推定開始．試行錯誤している過程が画面に表示されます．速くて動きが見えないという方は，sudoku |
more のようにmore.exeをフィルタとして通して下さい．でも，途中で飽きると思います．
最終結果が表示されます．答えがない場合はきちんとエラーが出ますが...猛烈に時間が掛かります．ソースリスト頭の#define
DISPLAYを#define NODISPLAYにしてコンパイルし直せば余計な表示はしません．
アルゴリズムの最適化は一切行なっていません．もっと効率を上げることは可能です．