Sudoku Solver
はじめに
なんで急に数独を解き始めたかというと、がっこの先生が図書室にプログラミングコンテストチャレンジブックを入れてくれて、それをやっと借りることができて（プログラミングの本としては超人気、現在5件も借りられてる）、それの二章に再帰関数が書いてあって、その部分和集合問題（n個の要素を持つ集合が与えられて、その和がkとなる部分集合は存在するかどうかを判定する問題）を理解したので、「チョット難しめなの解いてみるか〜」とおもったからです。（日本語力がないのでここまですべて一文）
ちなみに私は数独超ニガテです。小学校6年ぐらいの時以来解いてないし、ちょっとでもむずかしい問題は解けません。
深さ優先探索（depth-first search）です。その名の通りまずノードをできるだけ深いところまで伸ばしてから最も近い未探索ノードへ遷移します。
数独は深さが定まらない木には使えませんが、数独は問題にかかわらず深さは常に一定以下（9×9なら最大81）なので使えます。
また数独の問題は基本的に解を一つしか持ちません（持つ場合もあるがすぐに対処できる）。そのため、不正解となる探索はすべての空きマスを埋める前に空いているマスに打てる数字の候補がなくなります。そのため終了条件は「探索をおこなって空きマスがなくなったら終了」となります。
実装
こういう感じで実装しました。（一部の英語がカス！）
アルゴリズムのところでも言ったように、すべての空きますが埋まったら表示してtrueを返すというふうに書いてあります。実は最初に判定するところを組んでいたのですが、途中で枝刈りがすでに十分であることに気づいて消しました。(nは空きマスの番号)（つまり深さ）
ちなみに斜めでも1〜9を揃えたい場合は斜めで判定するメソッドを書いて、return trueをreturn target.jadge();的な感じに変えればいけます。
解が複数あるときは、trueをfalseに変えればいけます。（下のようにいっぱい表示される）
（画像長すぎ）
この状態のプログラムでも9×9の数独ならば問題にほぼ関係なく瞬時に、世界最高難易度と言われている問題でも0.5秒程度で終わります。
16×16への挑戦
9×9が瞬殺できるなら16×16に挑戦するまでです。16×16は計算量が飛躍的に向上するようで（詳しい近似とかはしらんけど）、今までのものをそのまま拡張しただけでは現実的な時間（数時間）内に終わりそうにありません。（目標は数秒以内）（これも問題によりけりだけど）
高速化手法① 分岐の少ない順にソート
数独を解くときに左上から当てはめていくドアホなんて普通いません。普通候補が少なそうなところから順に埋めていきます。
途中で枝が刈れない木なら、分岐の少ないところから埋めたところでノードの総数は変わりません。しかし数独の探索木の場合、探索を進めて行くと多量の枝刈りが自動的に行われるので分岐の少ないところから埋めたほうが有利に埋めていくことができます。
実際、実験用に適当に選んだ問題は普通に解くと右側の4ブロックが早い段階で埋まるらしく、プログラムでもそこを先に探索されるように左上に配置して入力したら8分ぐらいとかなり速くなりました。
ただ、どこのマスの候補が一番少ないかは常に変化します。なのでノードごとにソートし直すものを組んだところ、400分経っても終わりませんでした。
これの効果が薄かった（あるいは確認できなかった）のにはいくつか理由があります。
・まず一つに、ノード一つあたりの処理コストが向上したことです。すべての空きマスに対して打てる数を列挙してソートするので非常に高コストです。
・そして二つ目に、脈絡のない場所を次々に探索しすぎという問題です。横や縦に並んだブロック中の空きマス（相互に影響しあう空きマス）ならば効果的に枝刈りができていたかもしれませんが、斜めのブロック（相互に影響しない）中の空きマスが次々に探索されていくことが考えられるアルゴリズムなため、浅いノードでの枝刈りがあまり発生しなかったという点です。
これらを解決するために考えたのは、縦横のブロック同士の干渉を計算しながら探索順序を最初に決め、あとは変更しないというものなのですが、いかんせん具体的にどうすればいいかというのが思いつきません。しょんぼり。
高速化手法② 自明な場所を埋めておく
あるマスにNが入っていたとすると、それと縦横とブロックないにNは存在しません。ボード上のすべてのNについて、Nが入らないマスを埋めて、Nが存在しないブロックの空きマスがひとつならそこがそのブロック中のNであるとわかります。これをすべてのNについて行って、わかるところを探索無しで埋めてしまおうというのがこれです。
まだ実装が不完全なためなんとも言えませんが、この方法はゲーム全体においてかなり効果を持つように思います。
ゲーム序盤では、簡単な問題ならば膨大な自明なマスがあります。これは完全に確定するので、探索を行わなければならない場所が大幅に減ることになります。
探索を行っている途中でも、探索中に仮においた数字によってボードのどこかで矛盾（候補がなくなる）が起きればいいので早期に枝を刈ることができる気がします。
ただ、一回自明なマスを確定させて、その確定によって新たな自明なマスが発生する可能性があります。（まあアップデートがあったかを受け取ればいいんだけど、実装が面倒っていうね、それだけだよ）
まとめ
まあと言った感じで、16×16の数独には結構悪戦苦闘してるというわけです。プログラミングの勉強としての数独ソルバーですが、とても良い題材なのではないかなと思います。再帰関数を用いたプログラミングは始めたばかりなのですが、これを解くことによって結構自信がついたし、実際簡単なものなら瞬殺できる実力がつきました。
暇すぎて爆発しそうな人は数独ソルバーを作ってみてはいかがでしょうか。
私からは以上です。
P.S.このプログラム17個問題とかだとクソ
