数独というパズル

”数独”というパズルが、最近流行っているようで。知らない香具師はこれとかこれ見てから出直してこい！　というか、僕もさっきまで知らなかったんですけど。

こちらのサイトに、フラッシュ版の数独（ナンバープレイス）があり、手軽に遊べます。

なるほど面白い！と一瞬熱くなったのですが、「でもコレって、簡単なプログラムを書いたら、どんな問題でも一瞬で解けちゃうよな」と気付いて、少し醒めました。

むしろ、問題を作るほうが面白そうな。ヒントの数字が少ないほうが、難しくなるわけですが、どこまで少なくできるのでしょうか。Wikipediaによると、今のところ確認されている最小は17個だそうです。

じゃあ、16個の問題が作れるかどうか、これもプログラムを書いて、手当たりしだいにやったらどう？とも思えますが、直感的には、計算量爆発を起こしそうですね。ちと概算してみると、

まずは、数字を入れる16個のマス目を選ぶのが、何パターンあるのか考えてみます。これは「81個の異なるものから16個取る」という、単純な組み合わせ問題なので、

81!/(16!(81-16)!)

となります。 回転対称と線対称を考慮すれば、その1/8でいいのかな？

さらに、それぞれのマス目に入れる数字を、総当りで試すとすれば、「9個の数字から重複を許して16個取る」わけなので、9^16 です。

ということは、総当りのパターン数は、 81!/(16!(81-16)!)/8*9^16 であり、これをgoogle電卓さんに計算して頂くと、約 7.78*10^30 となりました。

PCで、この全パターンを計算すると、何年かかるでしょうか。CPUが4GHzで、仮に、1つのパターンが10クロックで計算できるとすると、81!/(16!(81-16)!)/8*9^16*10/(4*1000*1000*1000)/(60*60*24*365) なので…

約 600兆年？！　ホントかな？　なんか間違えた気もしますが、気が遠くなったので寝ます。オヤスミナサイ…

Comments

[投稿情報: Sak]

これ、昔やりましたよー。
頭の運動にはなかなか良いです。
しかしトオルさんは違う方で盛り上がってますな（笑）

[投稿情報: ちあき♪]

あぁ・・・見ただけで吐き気が。。。

りりかには夫トヲルの遺伝子が受け継がれていることを
心から祈りつつ・・・

[投稿情報: トヲル]

Sakさん：
昔からあったそうですね。僕は知らなかったけど。”Sudoku”という言葉の響きが、欧米人にとってカッコイイに違いない。

ちあきさん：
リリカは、僕が立派なゲーマーに育てるので大丈夫です。

[投稿情報: ちあき♪]

じゃあ、メイドさんの格好をしたゲーマーで
売り出すのはどう？？？

[投稿情報: たけこぷたー]

〇＃★илйЭЯФ☆♪！＆・・・・？