Sudoku Solver

うまく動かない場合はダウンロードして実行して下さい.

ごく普通のソルバーです.ただし,バックトラック法は用いずに,人間が解くときと同じように よく知られたテクニックを用いて解くのが特徴です. 問題を入力して Solve をクリックし,Next をクリックすると徐々に解き進めていきます. 問題を入力するには,盤面上で直接テンキーを叩いて入力します. また,一度入力すると Problem 欄に数字を81文字並べたものが表示されるので,これを保存しておけば以降はこれを Problem 欄に入れて Input を押すだけで入力することができます.

実装されているのは以下のようなテクニックです(名前は Tom Davis "The Mathematics of Sudoku" によります).

この2つのただちに決まるテクニックで,市販本の中級程度の問題まではほとんどを解くことができますが,難しい問題では さらに以下の候補を除外するテクニックが必要になります.

さらに難しいテクニックもありますが,今のところ実装してあるのはこれだけです. 市販本の問題のほとんどはこれらのテクニックを用いれば解くことができます. ただ,数独の問題全体では,これらのテクニックを適用しても解くことのできない問題もたくさんあります. もちろん,バックトラック法を使えば全ての問題を解くことは可能ですが, バックトラック法を使わずに,つまり上記のようにルールから導かれる論理的テクニックだけを用いて 全ての問題を解く方法があるのか,というのもまた興味深い問題です(ただ,数独が NP 完全であることを考えるとそのような完全なテクニックの体系は無いように思われます).

また,上記テクニックは問題の難易度とも密接に関連しています. というのは,たとえば Hidden Singles だけで解ける問題は簡単であると言えますし,X-Wing を 使わなければ解けないような問題は難しいと言えます.Sudoku Constructor で表示される "Difficulty" はこれに基づいて簡易的に判定し,表示しているものです.



Last-Modified: May 5, 2009