言語による制約記述  
   -技術情報

GUIの設定では、思うように記述できない場合があります。具体的には、行と列間で相互に係わりがある場合です。
そのような場合に、言語による制約記述の出番になります。 言語を用いる最大の利点は、記述の自由度にあります。 

この章は、ナーススケジューリングに限定しません。一般企業の人的リソースの最適化・人員配置計画、生産性の最適化・スケジューリング・配置の改善・効率化を扱う技術者向けに書かれています。

1. GUI と ソルバの関係


制約を満たす解を見つけるのは、制約ソルバ(求解エンジン)の仕事です。制約ソルバの出力は、制約を満たす解です。 制約ソルバへの入力は、制約記述です。制約記述は、GUI上での設定を変換することによって生成されます。制約記述は、スケジュールナースの内部仕様によります。

要するに、ソルバは、テキストを入力として、解としてテキストを出力します。



2. 言語化の必要性

では、テキストをそのまま入力出来るようにすれば、よいかというと、実はそれも手間がかかりすぎるのです。

下は、GUIでの設定をコンパイルして、制約ソルバへ入力するファイルの一部を抜き出したものです。

ハード制約の内部表現例

一つの制約は、一つの行で制約されます。例えば、上の例は、準夜ー日勤の禁止といったルールを各個人、各日について展開している部分の抜粋を示したものです。一般のナーススケジューリング問題では、ハード制約行数が数万行は普通で、ときに数十万行に及ぶことがあります。(9x9の数独パズルが数百行であることを考慮すると、一般のナーススケジューリング問題の方が遥かに大規模なパズルであることが分かります。)

ソフト制約の内部表現例

上は、一つのレベルのソフト制約を示したものです。行数的には、1行なのですが、ご覧の通り、かなり大規模な記述になります。

言語化する上での問題は、上の記述を一行一行を書くのは、作業量と時間の関係から現実的ではないことです。そこで、効率的に制約を記述する”言語”が必要になります。

具体的には、下のように、外部ファイルで記述した、言語記述部が、上記から追加されます。外部ファイルは、JAVASCRIPTに似た独自の言語により記述しますが、、最終的には、翻訳されて元の上の形態(テキスト)にマージされます。ソルバから見て、制約入力形式の違いはなく、ソルバの変更は、必要ありません。 

3.外部制約ファイルを呼び出す


下の求解条件で、言語制約をチェックすると、外部ファイルに記述された制約を適用する、という意味になります。



外部ファイルは、文字コードUTF-8 で制約を記述する必要があります。(SHIFT−JISではエラーになります。)
外部ファイル名は、プロジェクト名に同じ ドット txt  (拡張子txt) にしてください。ファイルが存在しない場合は、エラーが発生しますが、GUIで記述した部分の側のコンパイルは実行継続されます。

4.言語チュートリアル

内部表現

 3次元配列でシフトを表現します。 例えば、菅原のスケジュール開始日のシフトSは、

X[菅原][スケジュール開始日][S]

という風に表現します。次元は常に3次元です。(3次元以外はエラーとなります。) 


制約は、

$And(X[菅原][スケジュール開始日][S]);


    

といった風に記述します。(セミコロンで終端してください。セミコロンで終端した文を以下ステートメントと呼びます。) 制約ソルバは、全制約行がTrueとなるような組み合わせを探索します。すべての制約行をTrueにできたとき、それが解になります。上の行がTrueになるためには、$And内が、全てTrueである必要があります。
言い換えると、上の制約は、Trueであるためには、菅原のスケジュール開始日は、シフトSである必要があります。これは、菅原のスケジュール開始日のシフトは、Sである、と指定していることと同じですね。 

 反対に、菅原のスケジュール開始日のシフトは、Sであってはならない、という風に制約したいときは、


$Inv(X[菅原][スケジュール開始日][S]);


 

とします。上記文が、Trueであるためには、X[菅原][スケジュール開始日][S]がTrueであってはなりません。($Inv()は、論理否定を演算します。)つまり、菅原のスケジュール開始日のシフトSは、禁止されることになります。このようにして、True/Falseの2値を使って制約を記述していくことになります。

シフトは、ワンホット

シフトは、内部で常にワンホットであるようにしています。つまり、どれだけ多くのシフトを定義したとしても、常にどれか一つだけのシフトがアクティブになるようになっています。ユーザは、このことについて無頓着で構いません。ただし、指定しない限り、何がアサインされるかは、不明であることに注意してください。指定しない場合、何がアサインされるかは、私も含め誰にも予想できません。明示的にアサインされる確率を制御する手段もありません。強いて言うなら、ハード制約もしくは、ソフト制約のみが、制御可能な手段ということになります。

 それでは、制約言語の記述の仕方について、少しづつ見ていきましょう。

サンプルフォルダ 「言語による制約フォルダ」に、数独のサンプル 9x9数独X があります。これを開いてみます。

このサンプルは、シフト9個、スタッフ9人を下のように定義していあるだけで、数独の規則を制約として設定はしていません。


シフトの定義


全スタッフの定義

求解して解を求めると、下のように、出鱈目な数字が並びます。
これは、制約が何も記述されていないためです。




これから、言語による制約を 少しづつ追加して数独のルールを完成させて行きましょう。

制約を一つ定義してみる。

プロジェクトファイル名.txt ファイルを作り以下のように*記述しました。
これは、菅原のスケジュール開始日のシフトがB(ラベルは2)
であることを制約するものです。

*プロジェクトファイルと同じフォルダで、同じファイル名で、拡張子をtxtにします。
 必ずUTF-8で、保存してください


この外部ファイルを参照するように設定するには、求解条件の青部をチェックします。


すると、確かに、菅原の1日目のシフトがB(ラベル2)になりました。


同じ菅原で、他の日も同じシフトB(ラベル2)にしてみます。

$And(X[菅原][スケジュール開始日][B]);
$And(X[菅原][スケジュール開始日+1][B]);
$And(X[菅原][スケジュール開始日+2][B]);
$And(X[菅原][スケジュール開始日+3][B]);
$And(X[菅原][スケジュール開始日+4][B]);
$And(X[菅原][スケジュール開始日+5][B]);
$And(X[菅原][スケジュール開始日+6][B]);
$And(X[菅原][スケジュール開始日+7][B]);
$And(X[菅原][スケジュール開始日+8][B]);



*Note: [数字+スケジュール開始日]は、文法エラーです。必ず、[スケジュール開始日+数字] という風に記述します。

この結果は、X2プロジェクトになり、
下のように、菅原のシフトがすべてB(ラベル2)になりました。


単文と複文の関係

この記述は、以下のように書いても、結果は同じです。$AndがTrueであるためには、$And()内の要素が全てTrueである必要があります。
一つ、一つの行は、Andで結びついています。すなわち、全行の制約が満たされるようにソルバは、解を探索します。

$And(X[菅原][スケジュール開始日][B],
	X[菅原][スケジュール開始日+1][B],
	X[菅原][スケジュール開始日+2][B],
	X[菅原][スケジュール開始日+3][B],
	X[菅原][スケジュール開始日+4][B],
	X[菅原][スケジュール開始日+5][B],
	X[菅原][スケジュール開始日+6][B],
	X[菅原][スケジュール開始日+7][B],
	X[菅原][スケジュール開始日+8][B]);





ANDとORの違い

上の$Andを$Orにしてみました。


$Or(X[菅原][スケジュール開始日][B],
	X[菅原][スケジュール開始日+1][B],
	X[菅原][スケジュール開始日+2][B],
	X[菅原][スケジュール開始日+3][B],
	X[菅原][スケジュール開始日+4][B],
	X[菅原][スケジュール開始日+5][B],
	X[菅原][スケジュール開始日+6][B],
	X[菅原][スケジュール開始日+7][B],
	X[菅原][スケジュール開始日+8][B]);


この結果は、X3プロジェクトになり、下のようになります。

ANDでは、定義した全日がシフトB(ラベル2)になったのに対して、ORでは、第2日に一個あるだけです。
たった一個でも、上の$Or自体は、成立することに注意してください。すなわち、少なくとも1個がTrueであることは保証されますが、一個以上、どのような結果になるかは、(誰にも)予想できません。



for 文 

for 文は、3種類あるのですが、まずは一番簡単記述です。

上では、$And文を9回使いました。for文を使うと、
次のようにfor 文を使って、短く記述することも出来ます。

書式は、
[ declarations ]
for  ( 変数 in  集合 ) { statemtens }

*[ ]jは、オプションです。とりあえず、今は無視してください。

です。部は、予約語を示しています。変数は、自由に名前をつけることができますが、予約語と一致しないような名前にしなければいけません。
その変数は、集合の要素を順番に割り振られ、その度に、statementsが実行されます。

集合は、GUI上で定義した集合です。集合の種類としては、曜日集合、スタッフプロパティ、シフト集合です。集合名には、予約語を含んではいけません。

*半角の −マイナス、カンマ、ドット等は名前には、使用しないでください。
for (day in 全日){
	$And(X[菅原][day][B]);
}



さて、この結果は、次のように、前に記述した結果と同じく、指定部、菅原の全日のシフトがB(ラベル2)になっています。




通常の、プログラミング言語と同様に、for 文はネストすることが出来ます。ネストする際は、変数名が同じにならないようにしてください。
次の、X5プロジェクトでは、全スタッフのシフトをB(ラベル2)に制約しています。

for (day in 全日){
	for (person in 全スタッフ){
		$And(X[person][day][B]);
	}
}


全スタッフの定義は、こちら
全日の定義は、下図の通りです。

全日=月 | 火| 水|木 |金 |土 |日;

このように、GUI中使った集合の定義をそのまま呼び出しています。





vector宣言


for文に先立って、vector というコンテナ(入れ物)を宣言できます。

下の例で、 vector vA ;というのがコンテナの宣言です。
コンテナは、入れ物です。push_back というメソッドで、入れ物に入れることが出来ます。(push_backされた時点では、制約として認識はされません。
入れ物に詰めただけの状態です。$And 文等のステートメントで使われたときに、初めて制約として認識されます。)

これが、for 文と組み合わせると、欲しい要素を、まとまった集合として集めることができます。
下の例では、$Andという関数には、ある日の全スタッフのシフトBという集合が集められます。その結果、その日の全スタッフのシフトは、B(ラベル2)
になります。
for loopがもう一度周ると、また vector vA;という入れ物が宣言されているところに来ます。このとき、vAコンテナは、何も入っていないクリーンな状態に戻ります。
後は、上の動作を繰り返します。

vector は、必ずfor 文と組になって宣言することが出来ます。単独では宣言できません。
for (day in 全日){
	vector vA;
	for (person in 全スタッフ){
		vA.push_back(X[person][day][B]);
	}
	$And(vA);
}


この例だと、あまりその便利さが実感できないと思いますので、もう一つ例を挙げましょう。

$SeqLE関数



$SeqLEは、Activeになる要素の最小と、最大値を制約する関数です。下の場合、vAで集めた要素に対して、最小1以上、最大1以下を指定しています。VAには、9個のシフトAシフトの値(true/false)が入っているのですが、9個のAシフトのうち、Activeになるのは、一個だけあるという制約です。結果は、下のように、各日とも、1が一個だけ含まれていることが分かります。

もし、vectorを使わなかったとすると $SeqLE(1,1,X[菅原][.....);と延々と記述しなければいけないことに注意してください。





同様にしてシフトBについても記述を追加することができます。
for (day in 全日){
	vector vA,vB;
	for (person in 全スタッフ){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);

	}
	$SeqLE(1,1,vA);
	$SeqLE(1,1,vB);

}






そうなると、全シフトについて記述してみたくなります。
数独の縦のルールそのものになります。列でみると、どのシフトも一つしかありません。
//数独列制約
for (day in 全日){
	vector vA,vB,vC,vD,vE,vF,vG,vH,vI;
	for (person in 全スタッフ){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);
		vC.push_back(X[person][day][C]);
		vD.push_back(X[person][day][D]);
		vE.push_back(X[person][day][E]);
		vF.push_back(X[person][day][F]);
		vG.push_back(X[person][day][G]);
		vH.push_back(X[person][day][H]);
		vI.push_back(X[person][day][I]);

	}
	$SeqLE(1,1,vA);
	$SeqLE(1,1,vB);
	$SeqLE(1,1,vC);
	$SeqLE(1,1,vD);
	$SeqLE(1,1,vE);
	$SeqLE(1,1,vF);
	$SeqLE(1,1,vG);
	$SeqLE(1,1,vH);
	$SeqLE(1,1,vI);

}



さらに、短く書くことも可能です。
//数独列制約
for (day in 全日){
	for (shift in 全シフト){
		vector V;
		for (person in 全スタッフ){
			V.push_back(X[person][day][shift]);
		}
		$SeqLE(1,1,V);
	}
}




全シフトの定義は以下です。



$Onlyone関数

$Onlyone=$SeqLE(1,1,..) です。 機能は、同じです。1以上1以下に特化した関数です。その目的に最適化されています。通常の数独、9x9程度では、性能差はありません。
上は、次のように書き換えることが出来ます。

//数独列制約
for (day in 全日){
	for (シフト in 全シフト){
		vector V;
		for (人 in 全スタッフ){
			V.push_back(X[人][day][シフト]);
		}
		$Onlyone(V);
	}
}

シフトや人 のように日本語変数でも問題ありません。ただし、半角スペースや半角ハイフン(マイナス)全角スペースがあると構文エラーになってしまうので注意してください。dayが日になっていないのは、日を日曜として曜日定義でそのプロジェクトファイルが使っているからです。

数独を行と列の制約として解く


//数独列制約
for (day in 全日){
	for (シフト in 全シフト){
		vector V;
		for (人 in 全スタッフ){
			V.push_back(X[人][day][シフト]);
		}
		$Onlyone(V);
	}
}
//数独行制約
for (人 in 全スタッフ){
	for (シフト in 全シフト){
		vector V;
		for (day in 全日){
			V.push_back(X[人][day][シフト]);
		}
		$Onlyone(V);
	}
}

こうすると、行と列について各行各列共1個のシフトが割り当てられているのが分かります。

数独のブロックを解く if文の使用

縦横の制約は済んだので、残るは、小ブロックの制約です。3x3の小ブロックが9個あります。各々のブロック内でやはり、$Onlyoneを適用すれば良いのです。 最初に私が書いた制約は、次です。この制約は、行列小ブロック、数独全体の記述になります。


小ブロック部の制約は、if文を用いて、person と dayの範囲を限定することによって、各小ブロック部の制約を記述しています。
ここで、
&& は、論理積演算 (〜かつ) 
|| は、論理和演算 (〜または)

この結果、多数のVectorの記述(81個)が必要になっています。

//行制約

vector v1A,v1B,v1C,v1D,v1E,v1F,v1G,v1H,v1I;
vector v2A,v2B,v2C,v2D,v2E,v2F,v2G,v2H,v2I;
vector v3A,v3B,v3C,v3D,v3E,v3F,v3G,v3H,v3I;
vector v4A,v4B,v4C,v4D,v4E,v4F,v4G,v4H,v4I;
vector v5A,v5B,v5C,v5D,v5E,v5F,v5G,v5H,v5I;
vector v6A,v6B,v6C,v6D,v6E,v6F,v6G,v6H,v6I;
vector v7A,v7B,v7C,v7D,v7E,v7F,v7G,v7H,v7I;
vector v8A,v8B,v8C,v8D,v8E,v8F,v8G,v8H,v8I;
vector v9A,v9B,v9C,v9D,v9E,v9F,v9G,v9H,v9I;
for (person in 全スタッフ){
	vector vA,vB,vC,vD,vE,vF,vG,vH,vI;
	for (day in 全日){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);
		vC.push_back(X[person][day][C]);
		vD.push_back(X[person][day][D]);
		vE.push_back(X[person][day][E]);
		vF.push_back(X[person][day][F]);
		vG.push_back(X[person][day][G]);
		vH.push_back(X[person][day][H]);
		vI.push_back(X[person][day][I]);

		if (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v1A.push_back(X[person][day][A]);
			v1B.push_back(X[person][day][B]);
			v1C.push_back(X[person][day][C]);
			v1D.push_back(X[person][day][D]);
			v1E.push_back(X[person][day][E]);
			v1F.push_back(X[person][day][F]);
			v1G.push_back(X[person][day][G]);
			v1H.push_back(X[person][day][H]);
			v1I.push_back(X[person][day][I]);
		}
		if (person>=大政 && person<=高梨 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v2A.push_back(X[person][day][A]);
			v2B.push_back(X[person][day][B]);
			v2C.push_back(X[person][day][C]);
			v2D.push_back(X[person][day][D]);
			v2E.push_back(X[person][day][E]);
			v2F.push_back(X[person][day][F]);
			v2G.push_back(X[person][day][G]);
			v2H.push_back(X[person][day][H]);
			v2I.push_back(X[person][day][I]);

		}		
		if (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v3A.push_back(X[person][day][A]);
			v3B.push_back(X[person][day][B]);
			v3C.push_back(X[person][day][C]);
			v3D.push_back(X[person][day][D]);
			v3E.push_back(X[person][day][E]);
			v3F.push_back(X[person][day][F]);
			v3G.push_back(X[person][day][G]);
			v3H.push_back(X[person][day][H]);
			v3I.push_back(X[person][day][I]);

		}
		if (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v4A.push_back(X[person][day][A]);
			v4B.push_back(X[person][day][B]);
			v4C.push_back(X[person][day][C]);
			v4D.push_back(X[person][day][D]);
			v4E.push_back(X[person][day][E]);
			v4F.push_back(X[person][day][F]);
			v4G.push_back(X[person][day][G]);
			v4H.push_back(X[person][day][H]);
			v4I.push_back(X[person][day][I]);
		}
		if (person>=大政 && person<=高梨 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v5A.push_back(X[person][day][A]);
			v5B.push_back(X[person][day][B]);
			v5C.push_back(X[person][day][C]);
			v5D.push_back(X[person][day][D]);
			v5E.push_back(X[person][day][E]);
			v5F.push_back(X[person][day][F]);
			v5G.push_back(X[person][day][G]);
			v5H.push_back(X[person][day][H]);
			v5I.push_back(X[person][day][I]);

		}		
		if (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v6A.push_back(X[person][day][A]);
			v6B.push_back(X[person][day][B]);
			v6C.push_back(X[person][day][C]);
			v6D.push_back(X[person][day][D]);
			v6E.push_back(X[person][day][E]);
			v6F.push_back(X[person][day][F]);
			v6G.push_back(X[person][day][G]);
			v6H.push_back(X[person][day][H]);
			v6I.push_back(X[person][day][I]);

		}
		if (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v7A.push_back(X[person][day][A]);
			v7B.push_back(X[person][day][B]);
			v7C.push_back(X[person][day][C]);
			v7D.push_back(X[person][day][D]);
			v7E.push_back(X[person][day][E]);
			v7F.push_back(X[person][day][F]);
			v7G.push_back(X[person][day][G]);
			v7H.push_back(X[person][day][H]);
			v7I.push_back(X[person][day][I]);

		}
		if (person>=大政 && person<=高梨 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v8A.push_back(X[person][day][A]);
			v8B.push_back(X[person][day][B]);
			v8C.push_back(X[person][day][C]);
			v8D.push_back(X[person][day][D]);
			v8E.push_back(X[person][day][E]);
			v8F.push_back(X[person][day][F]);
			v8G.push_back(X[person][day][G]);
			v8H.push_back(X[person][day][H]);
			v8I.push_back(X[person][day][I]);

		}		
		if (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v9A.push_back(X[person][day][A]);
			v9B.push_back(X[person][day][B]);
			v9C.push_back(X[person][day][C]);
			v9D.push_back(X[person][day][D]);
			v9E.push_back(X[person][day][E]);
			v9F.push_back(X[person][day][F]);
			v9G.push_back(X[person][day][G]);
			v9H.push_back(X[person][day][H]);
			v9I.push_back(X[person][day][I]);

		}
	}
	$Onlyone(vA);
	$Onlyone(vB);
	$Onlyone(vC);
	$Onlyone(vD);
	$Onlyone(vE);
	$Onlyone(vF);
	$Onlyone(vG);
	$Onlyone(vH);
	$Onlyone(vI);
}
//列制約
for (day in 全日){
	vector vA,vB,vC,vD,vE,vF,vG,vH,vI;
	for (person in 全スタッフ){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);
		vC.push_back(X[person][day][C]);
		vD.push_back(X[person][day][D]);
		vE.push_back(X[person][day][E]);
		vF.push_back(X[person][day][F]);
		vG.push_back(X[person][day][G]);
		vH.push_back(X[person][day][H]);
		vI.push_back(X[person][day][I]);

		
	}
	$Onlyone(vA);
	$Onlyone(vB);
	$Onlyone(vC);
	$Onlyone(vD);
	$Onlyone(vE);
	$Onlyone(vF);
	$Onlyone(vG);
	$Onlyone(vH);
	$Onlyone(vI);
}
$Onlyone(v1A);
$Onlyone(v2A);
$Onlyone(v3A);
$Onlyone(v4A);
$Onlyone(v5A);
$Onlyone(v6A);
$Onlyone(v7A);
$Onlyone(v8A);
$Onlyone(v9A);

$Onlyone(v1B);
$Onlyone(v2B);
$Onlyone(v3B);
$Onlyone(v4B);
$Onlyone(v5B);
$Onlyone(v6B);
$Onlyone(v7B);
$Onlyone(v8B);
$Onlyone(v9B);

$Onlyone(v1C);
$Onlyone(v2C);
$Onlyone(v3C);
$Onlyone(v4C);
$Onlyone(v5C);
$Onlyone(v6C);
$Onlyone(v7C);
$Onlyone(v8C);
$Onlyone(v9C);

$Onlyone(v1D);
$Onlyone(v2D);
$Onlyone(v3D);
$Onlyone(v4D);
$Onlyone(v5D);
$Onlyone(v6D);
$Onlyone(v7D);
$Onlyone(v8D);
$Onlyone(v9D);

$Onlyone(v1E);
$Onlyone(v2E);
$Onlyone(v3E);
$Onlyone(v4E);
$Onlyone(v5E);
$Onlyone(v6E);
$Onlyone(v7E);
$Onlyone(v8E);
$Onlyone(v9E);

$Onlyone(v1F);
$Onlyone(v2F);
$Onlyone(v3F);
$Onlyone(v4F);
$Onlyone(v5F);
$Onlyone(v6F);
$Onlyone(v7F);
$Onlyone(v8F);
$Onlyone(v9F);

$Onlyone(v1G);
$Onlyone(v2G);
$Onlyone(v3G);
$Onlyone(v4G);
$Onlyone(v5G);
$Onlyone(v6G);
$Onlyone(v7G);
$Onlyone(v8G);
$Onlyone(v9G);

$Onlyone(v1H);
$Onlyone(v2H);
$Onlyone(v3H);
$Onlyone(v4H);
$Onlyone(v5H);
$Onlyone(v6H);
$Onlyone(v7H);
$Onlyone(v8H);
$Onlyone(v9H);

$Onlyone(v1I);
$Onlyone(v2I);
$Onlyone(v3I);
$Onlyone(v4I);
$Onlyone(v5I);
$Onlyone(v6I);
$Onlyone(v7I);
$Onlyone(v8I);
$Onlyone(v9I);

$Onlyone(v1B);
$Onlyone(v2B);
$Onlyone(v3B);
$Onlyone(v4B);
$Onlyone(v5B);
$Onlyone(v6B);
$Onlyone(v7B);
$Onlyone(v8B);
$Onlyone(v9B);



数独のブロックを解く if elsif else文の使用

上の記述で、if 文以下は、各一回しか実行されないので(小ブロック範囲は互いに独立なので)、次のように書いても、同じ動作になります。



//行制約

vector v1A,v1B,v1C,v1D,v1E,v1F,v1G,v1H,v1I;
vector v2A,v2B,v2C,v2D,v2E,v2F,v2G,v2H,v2I;
vector v3A,v3B,v3C,v3D,v3E,v3F,v3G,v3H,v3I;
vector v4A,v4B,v4C,v4D,v4E,v4F,v4G,v4H,v4I;
vector v5A,v5B,v5C,v5D,v5E,v5F,v5G,v5H,v5I;
vector v6A,v6B,v6C,v6D,v6E,v6F,v6G,v6H,v6I;
vector v7A,v7B,v7C,v7D,v7E,v7F,v7G,v7H,v7I;
vector v8A,v8B,v8C,v8D,v8E,v8F,v8G,v8H,v8I;
vector v9A,v9B,v9C,v9D,v9E,v9F,v9G,v9H,v9I;
for (person in 全スタッフ){
	vector vA,vB,vC,vD,vE,vF,vG,vH,vI;
	for (day in 全日){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);
		vC.push_back(X[person][day][C]);
		vD.push_back(X[person][day][D]);
		vE.push_back(X[person][day][E]);
		vF.push_back(X[person][day][F]);
		vG.push_back(X[person][day][G]);
		vH.push_back(X[person][day][H]);
		vI.push_back(X[person][day][I]);

		if (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v1A.push_back(X[person][day][A]);
			v1B.push_back(X[person][day][B]);
			v1C.push_back(X[person][day][C]);
			v1D.push_back(X[person][day][D]);
			v1E.push_back(X[person][day][E]);
			v1F.push_back(X[person][day][F]);
			v1G.push_back(X[person][day][G]);
			v1H.push_back(X[person][day][H]);
			v1I.push_back(X[person][day][I]);
		}elsif (person>=大政 && person<=高梨 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v2A.push_back(X[person][day][A]);
			v2B.push_back(X[person][day][B]);
			v2C.push_back(X[person][day][C]);
			v2D.push_back(X[person][day][D]);
			v2E.push_back(X[person][day][E]);
			v2F.push_back(X[person][day][F]);
			v2G.push_back(X[person][day][G]);
			v2H.push_back(X[person][day][H]);
			v2I.push_back(X[person][day][I]);

		}elsif (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日 && day <=スケジュール開始日+2){
			v3A.push_back(X[person][day][A]);
			v3B.push_back(X[person][day][B]);
			v3C.push_back(X[person][day][C]);
			v3D.push_back(X[person][day][D]);
			v3E.push_back(X[person][day][E]);
			v3F.push_back(X[person][day][F]);
			v3G.push_back(X[person][day][G]);
			v3H.push_back(X[person][day][H]);
			v3I.push_back(X[person][day][I]);

		}elsif (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v4A.push_back(X[person][day][A]);
			v4B.push_back(X[person][day][B]);
			v4C.push_back(X[person][day][C]);
			v4D.push_back(X[person][day][D]);
			v4E.push_back(X[person][day][E]);
			v4F.push_back(X[person][day][F]);
			v4G.push_back(X[person][day][G]);
			v4H.push_back(X[person][day][H]);
			v4I.push_back(X[person][day][I]);
		}elsif (person>=大政 && person<=高梨 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v5A.push_back(X[person][day][A]);
			v5B.push_back(X[person][day][B]);
			v5C.push_back(X[person][day][C]);
			v5D.push_back(X[person][day][D]);
			v5E.push_back(X[person][day][E]);
			v5F.push_back(X[person][day][F]);
			v5G.push_back(X[person][day][G]);
			v5H.push_back(X[person][day][H]);
			v5I.push_back(X[person][day][I]);

		}elsif (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日+3 && day <=スケジュール開始日+5){
			v6A.push_back(X[person][day][A]);
			v6B.push_back(X[person][day][B]);
			v6C.push_back(X[person][day][C]);
			v6D.push_back(X[person][day][D]);
			v6E.push_back(X[person][day][E]);
			v6F.push_back(X[person][day][F]);
			v6G.push_back(X[person][day][G]);
			v6H.push_back(X[person][day][H]);
			v6I.push_back(X[person][day][I]);

		}elsif (person>=菅原 && person<=綾瀬 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v7A.push_back(X[person][day][A]);
			v7B.push_back(X[person][day][B]);
			v7C.push_back(X[person][day][C]);
			v7D.push_back(X[person][day][D]);
			v7E.push_back(X[person][day][E]);
			v7F.push_back(X[person][day][F]);
			v7G.push_back(X[person][day][G]);
			v7H.push_back(X[person][day][H]);
			v7I.push_back(X[person][day][I]);

		}elsif (person>=大政 && person<=高梨 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v8A.push_back(X[person][day][A]);
			v8B.push_back(X[person][day][B]);
			v8C.push_back(X[person][day][C]);
			v8D.push_back(X[person][day][D]);
			v8E.push_back(X[person][day][E]);
			v8F.push_back(X[person][day][F]);
			v8G.push_back(X[person][day][G]);
			v8H.push_back(X[person][day][H]);
			v8I.push_back(X[person][day][I]);

		}else {		
		//	if (person>=遠藤 && person<=菜穂 && day>=スケジュール開始日+6 && day <=スケジュール開始日+8){
			v9A.push_back(X[person][day][A]);
			v9B.push_back(X[person][day][B]);
			v9C.push_back(X[person][day][C]);
			v9D.push_back(X[person][day][D]);
			v9E.push_back(X[person][day][E]);
			v9F.push_back(X[person][day][F]);
			v9G.push_back(X[person][day][G]);
			v9H.push_back(X[person][day][H]);
			v9I.push_back(X[person][day][I]);

		}
	}
	$Onlyone(vA);
	$Onlyone(vB);
	$Onlyone(vC);
	$Onlyone(vD);
	$Onlyone(vE);
	$Onlyone(vF);
	$Onlyone(vG);
	$Onlyone(vH);
	$Onlyone(vI);
}
//列制約
for (day in 全日){
	vector vA,vB,vC,vD,vE,vF,vG,vH,vI;
	for (person in 全スタッフ){
		vA.push_back(X[person][day][A]);
		vB.push_back(X[person][day][B]);
		vC.push_back(X[person][day][C]);
		vD.push_back(X[person][day][D]);
		vE.push_back(X[person][day][E]);
		vF.push_back(X[person][day][F]);
		vG.push_back(X[person][day][G]);
		vH.push_back(X[person][day][H]);
		vI.push_back(X[person][day][I]);

		
	}
	$Onlyone(vA);
	$Onlyone(vB);
	$Onlyone(vC);
	$Onlyone(vD);
	$Onlyone(vE);
	$Onlyone(vF);
	$Onlyone(vG);
	$Onlyone(vH);
	$Onlyone(vI);
}
$Onlyone(v1A);
$Onlyone(v2A);
$Onlyone(v3A);
$Onlyone(v4A);
$Onlyone(v5A);
$Onlyone(v6A);
$Onlyone(v7A);
$Onlyone(v8A);
$Onlyone(v9A);

$Onlyone(v1B);
$Onlyone(v2B);
$Onlyone(v3B);
$Onlyone(v4B);
$Onlyone(v5B);
$Onlyone(v6B);
$Onlyone(v7B);
$Onlyone(v8B);
$Onlyone(v9B);

$Onlyone(v1C);
$Onlyone(v2C);
$Onlyone(v3C);
$Onlyone(v4C);
$Onlyone(v5C);
$Onlyone(v6C);
$Onlyone(v7C);
$Onlyone(v8C);
$Onlyone(v9C);

$Onlyone(v1D);
$Onlyone(v2D);
$Onlyone(v3D);
$Onlyone(v4D);
$Onlyone(v5D);
$Onlyone(v6D);
$Onlyone(v7D);
$Onlyone(v8D);
$Onlyone(v9D);

$Onlyone(v1E);
$Onlyone(v2E);
$Onlyone(v3E);
$Onlyone(v4E);
$Onlyone(v5E);
$Onlyone(v6E);
$Onlyone(v7E);
$Onlyone(v8E);
$Onlyone(v9E);

$Onlyone(v1F);
$Onlyone(v2F);
$Onlyone(v3F);
$Onlyone(v4F);
$Onlyone(v5F);
$Onlyone(v6F);
$Onlyone(v7F);
$Onlyone(v8F);
$Onlyone(v9F);

$Onlyone(v1G);
$Onlyone(v2G);
$Onlyone(v3G);
$Onlyone(v4G);
$Onlyone(v5G);
$Onlyone(v6G);
$Onlyone(v7G);
$Onlyone(v8G);
$Onlyone(v9G);

$Onlyone(v1H);
$Onlyone(v2H);
$Onlyone(v3H);
$Onlyone(v4H);
$Onlyone(v5H);
$Onlyone(v6H);
$Onlyone(v7H);
$Onlyone(v8H);
$Onlyone(v9H);

$Onlyone(v1I);
$Onlyone(v2I);
$Onlyone(v3I);
$Onlyone(v4I);
$Onlyone(v5I);
$Onlyone(v6I);
$Onlyone(v7I);
$Onlyone(v8I);
$Onlyone(v9I);

$Onlyone(v1B);
$Onlyone(v2B);
$Onlyone(v3B);
$Onlyone(v4B);
$Onlyone(v5B);
$Onlyone(v6B);
$Onlyone(v7B);
$Onlyone(v8B);
$Onlyone(v9B);



労力を厭わなければ、この記述でも全く問題ありません。行列は、上で延べた方法でまとめられましたが、小ブロックについてもうまくまとめる方法はないでしょうか?

数独のブロックを解く 共通処理に着目

ブロックの左隅上をトップとして、それを基点としてアクセスすると、どの小ブロックも同じアクセスでよいことになります。
この性質を利用してまとめたのが次の形です。僅か34行で全数独のソルバーが完成しました。

ソース行数が多くても、求解速度には、殆ど影響はありません。というのは、結局展開すると、制約としては、本質的に同じだからです。時間がかかるのは、制約を満たす解を発見するソルバー部の処理です。ソルバへの入力が、結局は同じなので、処理時間には殆ど影響ありません。ですから、メンテナンスのしやすさ、後々見たときの理解の容易性を重視して記述スタイルを決めればよいと思います。

メンテナンスの容易性とは、例えば、パラメータを変更したときにも、それほど、大きく記述を変更する必要がないときに、メンテナンス性が良い記述であると考えられます。例えば、通常の9x9数独を、16x16、あるいは25x25.... に拡張しようとしたときに、上と下では、記述量が全然違いますね。(下の記述では、2という数字を置換するだけでよい。) しかし、将来に渡って9x9から変わることがない、ということであれば、上の記述でもOKです。


//数独列制約
for (day in 全日){
        for (シフト in 全シフト){
                vector V;
                for (人 in 全スタッフ){
                        V.push_back(X[人][day][シフト]);
                }
                $Onlyone(V);
        }
}
//数独行制約
for (人 in 全スタッフ){
        for (シフト in 全シフト){
                vector V;
                for (day in 全日){
                        V.push_back(X[人][day][シフト]);
                }
                $Onlyone(V);
        }
}
//ブロック制約
for (人 in スタッフブロックトップ){
        for (シフト in 全シフト){
                for (day in ブロックトップ日集合){
                        vector V;
                        for (i=0 to 2){
                                for (j=0 to 2){
                                        V.push_back(X[人+i][day+j][シフト]);
                                }
                        }
                        $Onlyone(V);
                }
        }
}


[Index] [Home]