36x36数独ソルバー

→Update記事です。

https://www.blogger.com/blog/post/edit/5717006239822465509/2437457069466716609

内部の変数と式数です。
 100715 472635

この数独パズルは、平均的なナーススケジューリング問題より規模が大きいです。
さすがに、コンパイルが重くなりまして、10解出力で18秒かかっています。
36ｘ36のソルバというと、殆どないと思います。さらにブランク状態から連続して解を求める例は、見渡したところないので、速度は世界一と言ってよいと思います。なお、解析的に答えを出す方法は、

http://en.wikipedia.org/wiki/Sudoku_solving_algorithms
にBlank　Sudoku gridsとして載っています。

数独は、通常バックトラッキングで、穴埋め問題を解きますが、全部がブランクだと、この方法では、規模が大きいときに破綻してしまいます。そこで、なんらかの探索方法が必要になってきます。

関連する文献としては、数理計画として解く方法、
http://www.is.titech.ac.jp/~okamoto/PDF/2007/puzzleip.pdf

SATにエンコードする方法
https://www.ipsj-kyushu.jp/page/ronbun/hinokuni/1002/C-5/C-5-4.pdf

SMTソルバを使う方法
http://bach.istc.kobe-u.ac.jp/sugar/puzzles/sugar-puzzles.pdf

スケジュールナースでは、9x9から出発して、16x16、25x25、そして36x36まで解きました。

->
２０１７RAMP講演でMIP　Solver CPLEXとの比較について触れました。１００ｘ１００まで解きました。



３６シフトの入力画面です。

１０解のうちのひとつです。

ソルバの検証は、Excelに解を貼り付けてブロック内の和でチェックします。

GUIが対応していないので、現在は無理ですが、81x81までは行けることが分かっています。それ以上どこまで行けるかについて、検討中です。
->時間はかかりますが、100x100までは、行けることを確認しました。
In conclusion, we can say our solver solves 100x100 sudoku matrix finally.Jun.24.2015