Web ブラウザと JavaScript で数独を解く

Permalink URL
http://www.magicvox.net/archive/2006/04122121/
Posted by
ぴろり
Posted at
2006/04/12 21:21
Trackbacks
関連記事 (0)
Comments
コメント (7)
Post Comment
コメントできます
Category
ソフトウェア カテゴリ

　数独とは、3×3 のブロックに区切られた 9×9 の正方形の枠内に、それぞれ縦・横・ブロックで同じ数字が被らないように、1〜9 までの数字を入れるパズルの一つです。"アメリカでがんばりましょう"で、数独を解く C プログラムが紹介されていましたが、今回、これを Web ブラウザで動作するよう JavaScript で作ってみました。

このエントリーをはてなブックマークに追加  

、Netscape、 をお使いの場合、解決の過程が見えて幸せになれます。IE をお使いの場合、プログラムを開始すると解決するまで途中経過が見えません。

プログラムの仕組み

　コンピュータパワーに任せて総当り というのもアリかも知れませんが、できるだけ人間が解く手順と同じようにプログラム化してみました。

上のは総当り方式ですが、普通に遅いです(^^;

　処理の最適化などはほとんど考えていないので、無駄な走査が多々あると思います。 見通しはそれほど悪くないと思うので、興味のある方は改造してみてください。
solve_init
　空いているマスに数字候補として (1)縲・9) を入れます(setCandidate)
solve_step1
　行・列・ブロックを見て、確定している数字があった場合、それを数字候補から除きます(clearCandidate)
solve_step2
行・列・ブロックを見て、数字候補が一つしかない場合、そのマスの数字が確定されます
solve_step3
　ある数字候補が、注目したブロックの一つの行あるいは列にだけ存在する場合、他ブロックのそれと同じ行あるいは列にあるその数字候補を除きます
solve_step4
　あるマスに数字候補を仮定しながら再帰的に処理を進めます。最終的に全てのマスが埋まっても矛盾があった場合、手数を戻って次々と数字候補を使って処理を進めます。深さ優先の再帰処理を行います。

いろいろ

更新履歴

  • 1.10 step4 をちょっぴり賢く
  • 1.00 初版公開
このエントリーをはてなブックマークに追加  

この記事を読んだ人はこんな記事も読んでいます記事リコメンデーションについて

カバー画像：Open Graph Protocol 付きで「いいね！」ボタンを設置する

関連記事/トラックバック

関連記事/トラックバックはまだありません

この記事にトラックバックを送るには？

寄せられたコメント (全 7 件中、最新 5 件まで表示しています)

Posted by
ぴろり ◆OLEEi.VOX.ぴろり ◆OLEEi.VOX.
at
2008/10/30 23:01
ID
ddrn5u.Y
＞あき さん
ご自由にどうぞー
Posted by
あきあき
at
2008/10/30 20:18
ID
KpkhOqFA
さっそくの改造どうもありがとうございました。
このスプリクト（ソース）をDLして、自分のHPで利用してもよろしいでしょうか？
サンプル問題を追加して利用したいと考えております。
Posted by
ぴろり ◆OLEEi.VOX.ぴろり ◆OLEEi.VOX.
at
2008/10/30 15:02
ID
ddrn5u.Y
＞あき さん
ご意見ありがとうございました。
Ver.1.20にバージョンアップしました(=ﾟωﾟ)ﾉ
・ドロップダウンリストからサンプル問題を幾つか選べるようにした
・解決途中の動作ログを出さないオプションを追加した
Posted by
あきあき
at
2008/10/29 18:02
ID
ZUdpvAao
×そこに難問かサンプル問題を入力し
○そこに何問かサンプル問題を入力し
間違いです、すみません。
Posted by
あきあき
at
2008/10/29 18:00
ID
ZUdpvAao
はじめまして、JavaSprict数独解析プログラム利用させていただいております。
現在URLの後に#数値で初期の問題を設定する事が可能ですが
プルダウンメニューから問題を選ぶような形に改造していただく事はできないでしょうか。
１行テキストボックスに問題を入力できますが、そこに難問かサンプル問題を入力し
それをプルダウンメニューにして、問題を設定することができれば助かります。
もし可能でしたら、改造をお願いしたいです。
なお、ログを表示させないようにするには
どの部分を削除すればいいのでしょうか？
もし簡単に変更できるようでしたら教えていただきたいです。
初めてのコメントでいきなりのあつかましいお願いで申し訳ございません
全てのコメントを見る (全 7 件)

コメントを投稿する

 
 (必須, 匿名可, 公開, トリップが使えます)
 (必須, 匿名可, 非公開, Gravatar に対応しています)
 (必須)
スパム コメント防止のため「投稿確認」欄に ランダムな数字 CAPTCHAについて を入力してから送信してください。お手数ですがご協力のほど宜しくお願いいたします。