16x16 数独ソルバ

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

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

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


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

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

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

プリセプタ、プリセプティ - ソフト制約を使いこなす

プリセプタ、プリセプティの制約は、禁止に比べると厳しいです。組み合わせ禁止は、その人以外を選択しなければよいので、選択の余地は大きいのですが、その人以外駄目になると選択の自由度がありません。そのために全夜勤を満たすのはとても難しいのです。でも、

１）できるだけ、プリセプタ、プリセプティの関係を満たしたい
２）何が何でも、プリセプタ、プリセプティの関係を満たしたい

１）は、ソフト制約にすれば実現できます。
２）２）は、予定制約をソフト制約とし、プリセプタプリセプティの制約レベルをそれより高くするか、あるいは、ハード制約とすれば実現できます。

あるICUからデータをお借りして、実際にやってみます。(スタッフ名は匿名です。）

最初に予定入力の画面です。かなり予定が入っていますね。果たして解はあるでしょうか？





プリセプタプリセプティは、問題になることが予想されるので、ソフト制約にしてあります。

下のようにソフト制約レベル４を設定しています。



　

下の状態で、求解してみます。

 

 

やはり、解はありませんでした。行制約４で、問題があると言っています。



ソフト制約４は、プリセプタプリセプティです。

一人あたりの許容エラーを下のように１から２に増やして再トライしてみます。

今度は解がありました。やはりプリセプタプリセプティがネックだったのですね。

数の下のペインで○がプリセプタプリセプティが成功したところ、ｘが３箇所ありますが失敗したところです。

この３箇所は、予定入力を全て満足する最小の数です。つまり、予定入力を満足するためには、プリセプタプリセプティエラーは、最小３個必要となり、２個以下では、予定は満足しないということです。この場合、async_timeがでていないので、解は厳密解で、物理的に入らないということです。逆に言うと、入らない中でもスケジュールナースは、頑張って詰めこんで、３個のエラーで済ますことができた、ということなのです。

上記１）の命題である、「できるだけプリセプタプリセプティの関係を満足させる」は、以上で実現できました。

 

次に、何がなんでもプリセプタプリセプティの関係を満足させる方法の説明です。

上で見たように、プリセプタプリセプティと、予定とを全て満足させる方法はありません。（物理的に入らない）

そこで、予定入力のソフト制約レベル５よりも、プリセプタプリセプティの制約レベルを高くします。

下のように、ソフト制約レベルを６にします。



このようにすれば、予定入力よりも制約レベルが高くなるので、満足するでしょう。

下はこのときの求解条件です。

行ソフト制約６がプリセプタプリセプティのソフト制約です。何が何でも実現なので、許容エラーは０に設定します。
下がこの条件下での解です。プリセプタプリセプティは、全て○になりました。代わりに予定の変更箇所が３箇所出ています。３箇所は、画像反転しています。この３箇所は、プリセプタプリセプティを満足する、最小の値でこれより小さい値は存在しません。（物理的にはいらない）。また、求解数は、１０回に設定していますが、2解しかでていません。これは、求解条件で、同じ予定変更の組み合わせを禁止設定しているからです。（ただし、最初の2解は同じことがあります。）つまり、プリセプタプリセプティを満足する予定変更の個数は、最小3個で、その組み合わせは、提示してあるものが全てになります

 上の二つの解を出すのに、要した時間は、2分くらいです。

 

この二つの結果を見てどちらを選ぶか、あるいは、さらに条件を振ってみるかは、評価者たる人間でしか行えないことです。

この事例は、ソフト制約を使いこなす高度な例ではありますが、いずれにしても求解条件とソフト制約レベルをいじっているだけなので、慣れれば使いこなせるようになると思います。「守りの勤務シフト表から攻めの勤務シフト表へ」　パラダイムシフトしてみませんか？

数独とシフト勤務表の等価性

下は、サンプルフォルダに入っている数独プロジェクトです。（実際に難問が入っていて解く様子が見られます。）この問題は、フィンランドの数学者が３ヶ月かかって作った世界一難しい問題といわれているその世界では、有名な問題です。数独の名人でも、数日かかるとされているこの問題をスケジュールナースは、１秒もかからずに解く事ができます。
勤務表を解くアルゴリズムでも説明していますが、勤務表の込み入った拘束条件を満たす解の解法というのは、方程式を解くようなものではなく、基本的には探索によるものです。その意味で数独のパズルとナーススケジューリングというのは、同じ種類の問題なのです。ただ、皆さんの抱えているナーススケジューリング問題というのは、実はこの数独を解く難しさからすると2桁から3桁程度難しいです。

ここで難しいという定義は、制約を式に置き換えたときの規模を言います。下記は、スケジュールナースのソルバが示す内部の状況です。

                                    変数　式の数
数独　　　　　　　　　   　738 　　 3249
池上２ShiftData 　　 25542 　114302
池上３ShiftData1.1　67512 　325062


必ずしも、解く時間と上記の規模は比例関係に有る訳ではないのですが、ある程度の相関関係が
知られており、問題の規模でいうと、２桁程度違うことが分かります。皆さんが普段やられている規模は、池上ShiftData2-3位の規模です。ですから、数独より2桁難しいパズルを毎月解いているというのは、あながち間違っていません。

数独は、全部ブランクのときの値です。それは、世界一難しい問題ではないだろう？という疑問があるかもしれませんが、全部ブランクが、一番難しいのです。というのは、論理的には、解けなくて仮定を置かないと解けなくなるからです。数独専用のソルバでやってみると、この事が実感できる筈です。（やった事はありません。）

スケジュールナースでは、このくらいの小さい規模ではマルチスレッドをオフにしているのですが、ブランク数独を0.2sec/個（Core　i5　３GHｚ)位で解き続けられます。はたして、スケジュールナースに勝てる専用ソルバはあるでしょうか？

難しいナーススケジューリング問題に対して、まだ、紙と鉛筆、あるいはExcelで立ち向かおうとする人には、名人の数日と一秒の探索能力の差を思い起こして欲しいな、と思います。

世界一難しい数独を解いてみる

勤務表ソフト　スケジュールナースで解いてみました。

動画はこちら


Version123のプロジェクトサンプルフォルダに入っているので、遊んでみてください。

勤務シフトソフトのスタンダード化

スケジュールナースは、日本の勤務シフト自動配置ソフト、defact standard を目指しています。



今週から、マニュアル・プレゼン動画・雑誌投稿原稿を作っていこうと思います。その前に勤務シフトソフトのあるべき姿を下記にまとめてみました。

１． 物理限界まで探索する能力
２．一つの勤務表から、複数の勤務シフト表案へ
３．配置できない箇所を指摘するのではなく、どうしたら配置できるかを提示する
いずれも、スケジュールナースのユニークなところです。

つづく

特許出願手続き

出願には、出願手数料を支払う必要があります。支払い手続きは、

１）出願ソフトを起動
２）補助タブで、納付番号取得（オンライン）
３）２）で得た納付番号をPayEasyで納める（オンライン）　特許出願は15000円です。
４）２）で得た納付番号を出願書類の電子現金納付の箇所に書く


１．出願

 これをオンラインで特許庁に送ります。送るのは、出願ソフトで、出願タブー＞送信ファイル
簡単願書作成ソフトで作成したHTMLファイルを選ぶと、送信形式のファイルにしてくるようです。
この際、モノクロに変換されます。白黒だけで作成していても、形式が256色になっているとWarningがでます。注意するのは、簡単願書作成で問題なかった図も、送信形式の図をチェックすると解像度が大分落ちていることです。(今時、無理して圧縮をかける必要は無いはずですが...)
しかも、プリンタに印刷してみないと実際の図の具合がどうなっているか分からないので、プリンタによるチェックは必須です。

無事にオンラインで送ると出願番号が割り振られるので、その出願番号で、

 ２.早期審査に関する事情説明書
 ３.出願審査請求書

を書きます。特許明細書本体と上記は、いずれも、簡単願書作成ソフトで作成します。

これらは、同じ出願ソフトの出願タブで同じように行います。

それとは、別に以下を送りました。

オフライン（特許庁に郵送）

1. 審査料金減免申請書
2. 非課税証明書

 以上です。

特許２

現在、2通目の特許申請を書いています。

前回の特許は、ソルバの高速化に関するものでしたが、今回は、本質的に勤務表作成に関するものです。

ところで、本特許の申請前に製品にその機能を実装し、マニュアルに書くことはできません。というのは、一旦世の中にでてしまうと「公知の技術」になってしまって、特許性が認められなくなってしまうのです。それが、自分の書いたものであるならよいのではないか？というのは通りません。一部例外はありますが、特許に関するものは、申請前にWebに載せることは禁物です。

そういう訳で、現在、Tutorial、中途半端になっているのはそういう事情からです。申し訳ありません。