もしかしたら、日本よりアメリカやイギリスなどのほうが有名かもしれないパズルゲーム数独(Sudoku)。
新聞にはクロスワードに並んで掲載され、Web サイトでもいろんなところに載るなど認知度も高い。 そんな数独を解くプログラムが digg.com で紹介されていた。
C言語で書かれたプログラムだが、コメントや入出力処理などを除くと、実際のアルゴリズムは1500行ぐらいで構成されている。 かるく見てみたが、データ構造も比較的簡単で、人が数独を解く考え方をプログラムでうまく表現したような作りになっている。
使われているアルゴリズムをまとめると、空いている(まだ埋まっていない)マスは 1-9 全てが入る可能性があるものだと考え、既に埋まっている数字を元に可能性を減らしていき、1つに絞れたらマスが埋まったと判断するようになっているようだ。
もう少し具体的に書くと
- 各マスに入れられそうな数字の候補リストから、縦、横、3×3 エリア(region) で既に使われている数字を除く。
- 縦、横、3×3エリア のそれぞれで、そのマスに入る可能性の数字のコンビネーションと、空いているマスの数が同じなものがあったら、他の空いているマスの候補から除く。
- 3×3エリアを調べ、入る可能性のマスが1つの行、もしくは列に狭められたら、その数字を同じ行(もくは列の)他の空いていマスの候補から除く。
- それでも埋まらないマスは試行錯誤でマスを埋めていく
といったステップ。 最後は、やはり試行錯誤になってしまうが、いくらか試してみたがちゃんと解いてくれるし、Webサイトによるとそれでも1秒で 10,000 以上のパズルを解いてしまうほどの速さだというのでなかなかのモノのようだ。 オレは 3つめのヤツをよく忘れてハマるんだよなぁ。
みなさんも、このアルゴリズムを頭にいれてトライしたら早く解けるようになるかも。
そうそう。 オレが数独で遊ぶときはいつも Life.com の Sudoku (Flash版) を使っている。システムはうまくできているし、Easy でも結構手応えのあるパズルが出てくる。 おためしあれ。
2006年3月29日 at 8:37 PM
SQLで解くってのもあるみたいです。 テーブルなだけに得意なのか?
http://www.vsj.co.uk/articles/display.asp?id=540
2006年3月31日 at 6:11 AM
▼数独発売中：子どもからおじいちゃんまで「ニンテンドーＤＳ」で脳力ＵＰ
１．始めに 数独というパズルが世界的な人気で、第１回世界選手権がイタリアのルッカで今年の３月に開かれ、日本から参加した西尾徹也さん（東京都）が４位、青木真一さん（愛知県刈谷市）が６位に入賞しています。数独とはどういうものか、そして、ニンテンドーＤＳで…
2006年4月12日 at 5:31 AM
ブラウザ＋JavaScriptで数独を解く
”アメリカでがんばりましょう”で、 数独を解く C プログラムが紹介されていました。 数独とは、 3×3 のブロックに区切られた 9×9 の正方形の枠内に、それぞれ縦・横・ブロックで同じ数字が被らないように、 1～9 までの数字を入れるパズルの一つです。 今回、これを…
2006年4月19日 at 9:22 PM
数独（すうどく）
あいあい。どうもどうも。みなさまいかがお過ごしでやんすか？ ところで、みなさまパ…