数独

M. K. — Thu, 26 May 2011 14:57:18 +0000

思いつきで、sudokuのエディター兼自動解析を作成してみました。
Web上にあるいくつかの問題を解かせてみましたが、中級クラスの
問題は解けてるようです。

数独解析
ソース:sudoku.js

人間向けの定石として以下のサイトを参考にさせてもらいました。

実装したアルゴリズムは以下の二つです（数独っていかにも数学的な問題な気ましますが、そんな説明は一切出来ませんorz)。

単純候補抽出

各セルの縦、横及びリージョンから配置可能な数値を抽出します。

　抽出した結果、候補が一件しか無ければセルの値は確定です。

残り物

　「単純候補抽出」で配置可能なセルが見つからなかった場合に実行します。
余談ですが、先の「ナンバープレイス解法教室」で初級の常識として紹介されていたルールも（結果的に）ここに含まれます。
人間と機械では簡単な事が異なりますね。

ここでは、縦、横およびリージョンを見渡して以下の候補が無いか検討します。

「唯一、そのセルでした候補になっていない値は無いか」

例えば、残りさん３セルで候補がそれぞれ[6,9],[6,9],[1,6,9]だった場合、「1」を配置できるセルは一カ所しかありません。よって「1」が当該セルの値です。

仮ぶろぐ » 数独