数独を焼きなましてみた

はじめに

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

アルゴリズムの選択

dfs

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

焼きなまし

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

実装

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

結果

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

アニーリングの雑感

アニーリングは統計力学と少し関係しているアルゴリズムです。適当なコスト関数を用意して、そのコスト関数の最小値を求めたいとします。（今回の数独であれば、同じ行、列、ブロックに含まれている同じ数字のペアの個数をコスト関数にすると、正答のときに最小になり、その最小値を取る数の入れ方を定めれば良いとわかります。）
そのとき、そのコスト関数をその準位が持っているエネルギーとして、温度が高ければ熱ゆらぎによりエネルギーが大きな準位も取りますが、温度０のときはエネルギー最小の準位しか取らないという分布を考えます
求めたい分布が定常分布となるようなマルコフ連鎖を用いて、時間発展させることによってその分布に従うサンプル列を得るというマルコフ連鎖モンテカルロをします
その上で温度パラメータをゆっくりと下げていけば真の解に収束することが期待できます。
今回は一番単純な一つの数字をランダムに選び、ランダムに変更していく、という近傍を取りました