ホームページへ戻る
数独(ナンバープレイス)を解く
ペンシルパズルの代表とも言える数独の問題を、どんな難問でも瞬時に解きます。
|
|
既にサンプル問題が表示されています。
[探索開始]をクリックしてみて下さい。
水色で表示された数字が見つけた解です。
問題の入力の仕方
[全消去]ボタンで総ての数字が消えます。
入力位置(点滅箇所)は、方向キー(↑→↓←)で移動するか、または、マウスで入力位置を直接クリックします。
数字の入力はキーボードを使うか数字ボタンをクリックします。
結 果 の 確 認
| 探索終了 |
解答が出ました。 |
| 問題異常 |
問題または入力にミスがあります。 |
| 重複あり |
解が複数あります。
(赤表示が別解のある全箇所) |
|
一般的にペンシルパズルの解き方は、局所的な部分に対して解を確定出来る部分を探し、それを何よりも優先します。これによって、また新たな部分で解を特定出来るという状況が連鎖的に発生して、やがて総てのマスが埋め尽くされるという性質を持っています。
このような解き方を「制約伝播」と言いますが、このような人が解く解き方をそのまま真似てプログラミングしても、特に上級レベルの問題では最後まで解けない場合が出てきます。
かと言って、しらみ潰しのバックトラッキングを使って解こうとしても始めの空きマスの量は非常に多く、答えを出すまでの探索時間は膨大なものになってしまいます。
そこで選択の余地なく確定出来るマスは制約伝播で優先的に書き込んでしまう。という処理をバックトラッキングの中に組み込むことによって、探索空間を常に縮小しながらのバックトラッキングとなり、とても効率良く探索を行うことが出来るようになります。
さて、数独でも制約伝播に使えそうな確定ルールは幾つかありますが、本プログラムで使ったのは右図の、たったひとつだけです。
ある行にまだ未配置の数字で配置可能なマスがその行に１箇所だけなら、その数字をそこへ配置する。同様のことを列と3×3ボックスについても行い、この２７エリア×９種類の数字について、解が特定出来なくなるまで何度もループする探索をします。
「確定探索付き再帰」のプログラミング構造については、お絵かきロジック(ののぐらむ)を参照して下さい。
|
 |
htmlファイル内のどこかに、
<canvas id="canvas" width=420 height=420></canvas>
<script type="text/javascript" src="sudok.js"></script>
|
と書き、同一フォルダに下のファイル(数独を解くJavaScript)を置き、htmlファイルを起動してみて下さい。
ホームページへ戻る
|