Giant sudoku solver by nurse rostering software

I would like to introduce my nurse rostering solver "schedule-nurse".

Sudoku is NP-Complete
Nurse Scheduling Problem is NP-Hard.
Both can be solved by constraint programming.
You don't need to write program on how to solve, you only need to write constraint for the problem.
Nurse rostering software "schedule-nurse" is fast enough to solve huge blank sudoku, though it is not exclusive sudoku solver. It is free software, you can develop your own pencil game. From the point of another view,it  may be the tool to get answer(SAT/UNSAT) for other fields of  problem.It's just fun...


Is there a limit or maximum size to how big can be made?
That is the natural question. Crrent software can generate up to 36x36 sudoku. But the latest study shows 81x81 sudoku is possible within reasonable time. As for 100x100 sudoku, I can say it's very hard and challenging problem. To the best of my knowledge, I don't know such a sudoku generator.

プレゼン動画

プレゼンを動画にしてみました。

プレゼンテーション

KingSoftというPowerPoint互換ソフトで作成しました。

http://www.nurse-scheduling-software.com/tutorial/schedule_nurse_presentation.ppt

動画にする機能はないのですが、細かい点を除けばほぼ互換（PowerPoint2003）が
とれています。

しょうがないので、ビデオでキャプチャすることにしました。

勤務シフト表自動生成ソフトの評価

とりあえず、VirtualBox上で、評価してみました。
結果はこちらです。

http://www.nurse-scheduling-software.com/tutorial/test_bench2.htm

強く思ったのは、もし低レベルのソフトでシフト表を作成すると影響を最も被るのは、スタッフナースになるということ。希望の休みが取れなかったり、理不尽なシフトを強いられる可能性が高くなる、人の生活がかかっているのに...こんなにひどいとは思わなかったのでちょっとショックを受けました。

早くメジャーに上がらなくては！

スケジューリングソフトの評価

今まで、特許を書くことを第一優先にしていたので、他のソフトを評価する余裕がありませんでした。で、アピールポイントは何か?と考えていたら、やはり他と比較してみるのがよろしかろうという結論に達しました。

評価環境を整えるために、Virtual環境を構築しました。Windowsは、Microsoftがよかろうと思いきや、VirtualPCは、WindowsInstall途中でErrorになってしまい立ち上げに失敗。代わりにVirtualBoxでやってみると、問題なくInstallできました。任意時点のSNAPSHOTを取れるので、いつでも前の状態に戻せます。使い勝手もVirtualBOXの方がよい感じです。

で、肝心の評価状況ですが、

あ社：起動せず。３２Bit版・６４Bit版でトライも致命的エラーで立ち上がりませんでした。
いソフト：ほぼよい感じで動きます。評価できそう。エラーチェックが甘いがソルバは真面目に作ってありそう。
うソフト：ひどいです。よくこれでお金を頂けるなあと感心。評価データを採取するには、制約を大分緩めなければならない。

なるほど、こういうソフトばっかりだから、看護師長から見ると、ソフトは...になるのですね。

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

25x25 数独ソルバ

25x25数独は、変数数、式数で以下の通りとなりました。

32607 154556

これぐらいだと、ナーススケジューリング問題の典型的な規模になります。

さすがに、解の出力速度は、遅くなり0.8 sec/1解/Thread/となりましたが

ブランクの数独を連続的に解くスピードは、世界最高の可能性があります。

 

シフトを２５個定義しています。

解を１０個出力しています。


 



Excelに解を貼り付けてソルバを検証しています。

 





16x16 数独ソルバ

もコーディングしてみました。Version123までは、シフトの数は12まででしたので、16まで拡張する必要があり、GUIとソルバもこれに対応してみました。

シフトの定義です。内部シンボルはA,B,C,,,ラベルは1,2,3...と定義しています。

9x9数独と同様に16x16数独ソルバは、ブランク数独に対して0.2sec/Thread の速度で、別解を出力することができます。この速度に勝る数独専用ソルバはあるでしょうか？


ソルバが出力した解です。10解を出力しています。
 

Excelでソルバの検証、解をExcelに貼り付けて、数独ブロックの和が136になることを確認しています。

内部の変数と式数は、
8014 38709
でした。この規模の数独だと、未だ通常のナーススケジューリング問題の方が数倍規模が大きいです。