tomabouの日記

勉強したことなどを書いていきます

数独を焼きなましてみた

はじめに

数独という9*9のマスに数字を入れていく有名なパズルがあります。
飛行機に乗っている間、機内ゲームの数独で遊んでいたのですが、一番レベルが高いものがなかなか解けませんでした。
足元を見るとカバンにパソコンが入っていたのでパソコンで答えを見つけることにしました。

アルゴリズムの選択

dfs

選択肢が少ないマスを選択して、深さ優先探索するというアルゴリズムがすぐ思いつきます。それを実装するとほぼ問題ないのですが、ワクワク感が無いのが難点です。

焼きなまし

アニーリングとも呼びます。このアルゴリズムは厳密解を求めるには向いていませんが、数独ぐらいなら解けそうな気もします。ワクワク感があるので実装してみることにします。

実装

pythonでちょろっと書いてみました
python/sudoku.py at master · tomabou/python · GitHub

結果

適当にパラメータを定めて数回試したら数分で解けました。やったね
アニーリングで解けるかは運ですが、実装をもっと高速にして、温度スケジューリングをちゃんと調整すればそこそこ高速に求まるでしょう

アニーリングの雑感

アニーリングは統計力学に触発されて開発されたアルゴリズムです。適当なコスト関数を用意して、そのコスト関数の最小値を求めたいとします。(今回の数独であれば、同じ行、列、ブロックに含まれている同じ数字のペアの個数をコスト関数にすると、正答のときに最小になり、その最小値を取る数の入れ方を定めれば良いとわかります。)
そのとき、そのコスト関数をその準位が持っているエネルギーとして、温度Tのカノニカル分布を考えます。温度が高ければ熱ゆらぎによりエネルギーが大きな準位も取りますが、温度0のときはエネルギー最小の準位しか取りません。
カノニカル分布を直接計算することはほぼ出来ないので(出来るなら最小解が解析的に求まります)モンテカルロサンプリングで近似することを考えます。
マルコフ連鎖モンテカルロを用いることにします。マルコフ連鎖モンテカルロとは求めたい分布が定常分布となるようなマルコフ連鎖を用いて、時間発展させることによってその分布に従うサンプル列を得るという方法です。
その上で温度パラメータをゆっくりと下げていけば真の解に収束することが期待できます。
今回は一番単純な一つの数字をランダムに選び、ランダムに変更していく、というマルコフ連鎖を用いました。
マルコフ連鎖は様々なとり方が考えられて、良いマルコフ連鎖を用いると収束が早くなったりもするみたいです。
ちなみに、イジングモデルMCMCは非常に頭の良いアルゴリズムがあるので、知らない人はぜひ調べてみてください