2015年12月25日金曜日

言語による制約記述のチュートリアル

ここに書いています。

数独を題材にして、制約プログラミングの仕方について述べています。途中なので、ソフトは未だリリースできませんが、来年早々にソフトはリリースします。

制約プログラムというのは、答えを求めるアルゴリズムを記述することではありません。制約を課すことで、答えは自動的に求まります。ですから、その記述は、一通りではありません。が、出来れば、直感的に分かりやすく、なおかつ短い記述が求められます。

今回、そのための言語を設計したのですが、なるべく短い行数で、狙った仕様が記述できるように心がけました。 その結果ですが、かなり短く書けているのではないかと思います。数独のプログラミングは、他のサイトで散見されますが、その中でもかなり短い方ではないかと思います。

以下は、数独の全記述(34行)です。

//数独列制約
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);
  }
 }
}
dayは、本当は”日”にしたかったのですが、そうすると 日曜が、日として使われていたのでエラーとなってしまいます。

なお、WEB版でも制約言語は動作しますが、Javascriptのセキュリティ上、テキストファイルを呼び出すという風にはできないので、TEXTBOXに貼り付けになってしまいます。(デバッグについては、PC版の方が便利そうです。)