Cazperのつれづれ日記: 【SUDOKU：数独】自動解法プログラム【ナンバープレース：ナンプレ】

2009年2月14日

本屋を眺めていたらSUDOKU(数独)の本が目に入りまして手に取ってみたものの、あまりの面倒臭さにストレス100倍になってしまいました。そこで、自動解法プログラムを作ってみました。

決まった数字を入れて、「Solve」ボタンを押すと...

自動的に答えを探索します。

JavaScriptで出来た自動解法のサイトもあるのですけれども、複雑な問題を解けなかったり、時間が掛かりすぎたりします。特にバックトラック法(深さ優先探索法)を実装しているサイトでは計算途中でブラウザがビジー状態になってしまう事があります。

というわけで、適当にアルゴリズムを考えてJava Appletで作ってみたところ、ナンプレの解法を紹介しているサイトで掲載されていた上級問題も1秒も掛からずに見つけ出しました。

ナンバープレースを解くのも面倒くさいのですけれども、プログラムを書くのも面倒くさいので、手抜きをしてあります。とはいえ、直感的にはプログラムに手抜きをしたとしても複数解答が見つけだせるものと思っております。(ただし、1つのマス目に4つ以上の解候補がある状態で解法が詰まると計算を放棄します。)

＜プログラミング備考＞
所要コーディング時間は2日間ぐらいかな。殆どの時間はGUIのレイアウトに使われています（涙。再帰関数を利用していて2分木、3分木での探索をしております。

(注)
「数独（スウドク）」はニコリの登録商標(第3327502号など)です。そのためナンバープレース(ナンプレ)とも呼ばれるみたいですね。

PS1
数独はかなり昔に流行ってたから解法ソフトなんてのはザラにあるわけですけどね。

PS2
英語版サイトも作ってみたり。さらに中国語版サイトも作ってみたり。

投稿者 cazper : 2009年2月14日 00:01 |
Tweet

このエントリーのトラックバックURL:
http://www.cazoo.jp/cgi/mt/mt-tb.cgi/2445

凄いですね！
一瞬で問題が解けるのは、なんだか気持ち良いです（笑）

興味深いのでブログで引用させてもらいました。

投稿者 jar^2 : 2009年2月15日 09:54

＞JarJarさん
引用ありがとうございます。

バックトラック法は最初知らずに、たまたま組んだアルゴリズムがバックトラック法になってました。

ちょっとした便利ツールをどんどん作っていきたいのですが、時間が無いのがネックです。(/_;)