数独の解き方

数独をやってみたけど、めんどいので機械に解かせることにした。
解き方は簡単。

まず、絞込み

• 各セルに全部の数値を入れておく。
• 問題からひとつづつ値を取り出し
  • 該当セルはその値だけにする
  • グループ、縦、横で、同族になるセル全部からその値を取り除く
    • セルの値が1つになったら、同様にチェックする

これだけでは必ず一つの解が出るとは限らない。解けない状況は発見される。

このデータを下に探索:

• 複数候補のあるセルのひとつを、どれか適当な値で拘束して再び上記手順で絞り込む。
  • 解けないときはその候補を消す。
  • 複数候補が残るときはさらに消す。
  • 1つになれば終わり

解をひとつ見つければよい場合は、上記手順を繰り返せば見つかる。全部見つける場合は8クイーンのようになるかな。