- sdsol -
Ver0.60
2011.01.06
大野 和彦


○使い方
ナンバープレースパズル(Sudoku)を自動的に解くプログラムです。
盤面上のマス目をクリックして、問題を入力して下さい。
・左クリック：数字を一つ大きくする
・中クリック：そのマス目を空にする
・右クリック：数字を一つ小さくする

盤面の右側のコマンド欄を左クリックすることで、問題を解いたり保存したりできます。
・問題消去
    盤面をすべて空にします。
・解答消去
    解答(コンピュータが記入した欄)だけクリアし、出題時の状態に戻します。
・開始
    解答を開始します。選択すると一ステップずつ解法を当てはめて解いていき、
    盤面がすべて埋まるか手詰まりになると停止します。
    解答中は「開始」が「一時停止」に変化し、ここを左クリックすることで
    解答を中断できます。
・次STEP
    現在の状況に対し、解法を1ステップ適用します。
・次の数字
    新たに数字が一つ確定するまで、解法の適用を繰り返します。
・読込
    「保存」で作成した"problem.txt"を読み込んで問題を盤面上に復元します。
・保存
    問題を"problem.txt"というファイル名で保存します。解答は保存されません。
    選択すると確認なしに保存するので誤操作に注意してください。
    複数の問題を保存したいときは保存後にリネームするなどしてください。
・テキスト保存
    現在の状況(問題および記入済みの解答)を"result.txt"というファイル名で保存します。
・終了
    プログラムを終了します。

○解答中の表示色

解答中は、注目しているブロック／行／列／マスが太枠で強調されます。
また、マス目が以下のように塗り分けられます。
・黄：新たに数字が確定した
・赤：制約により注目している数字を置けないマス
・青：制約を発生しているマス
・

○解法について

もともと人手で解けるパズルなので、適当に制約を適用してやれば探索空間は
かなり小さくなり、バックトラックを用いた探索で簡単に解けるはずです。
それだとおもしろくないので、あえて人間が解くのと同じようなやり方で解いています。

具体的には、以下のような制約を順に適用していきます。
一回の制約適用を1ステップとしていますが、明らかに適用できない場合
(注目数dがすでにすべて判明している、など)はステップに数えません。

1. 注目ブロック(3x3マス)の注目数dについて、縦横に並ぶブロック中のdによる制約を
   チェックし、位置が一意に絞り込めたら決定する。
2. 注目行／列の注目数dについて、他のdによる制約をチェックし、
   位置が一意に絞り込めたら決定する。
3. 注目するマスについて、そのマスを含むブロック・行・列による制約をチェックし、
   そこに入れられる数字が一意に絞り込めたら決定する。
4. ブロック／行／列の空きマスが残り一つになったら、残っている数字に決定する。

適用順も、可能な限り(人がチェックしやすい)1.を適用し、
手詰まりになったら2.を適用し、進展があれば再び1.の適用に戻る、という流れで、
1,2,3の順に優先度をつけています。4.は新たに数字が判明するたびに、
関連するブロック・行・列に適用します。

現バージョンは比較的簡単な制約しか用いていないため、
あまり難しい問題は手詰まりになって解けません。
たとえば以下のような状況を考えます。
  8 4 1
    5 9 
  6 
下段の2つの空きマスが2と3であると決まれば、両者の位置が確定しなくても、
中断左の空きマスは残っている7に確定します。
しかし現バージョンはこのような複数マスの「予約」は行いません。

○プログラムについて

全体を以下のように分けています。
・main.h, main.c
  GUIを含むトップレベルの処理
・puzzle.h, puzzle.c
  盤面の保持と変更、内容のチェック
・solver.h, solver.c
  制約適用によりパズルを解く

盤面の参照・変更はすべてpuzzle.cの関数を経由して行うことで、
盤面の実装方法の変更をpuzzle内の修正だけで行えるようにしています。

また、解答をループや再帰呼び出しで行ってしまうと操作を受け付けなくなったり、
画面の更新速度が速すぎたりするため、
solver.cでは一ステップだけ進める関数を用意し、
main.c側からタイマハンドラにより一定時間毎にこの関数の呼び出しと画面更新を
行うようにしています。