Javaによる制約解消系 Cream

Java

さまざまな制約(Constraint)を満たす解を求める枠組みを制約解消系(Constraint Solver)と呼ぶ．たとえば，Prologなんかは言語でもあるけれど，制約解消エンジンが組み込まれているとも言える．

制約解消は，いろんな問題に使えるが，身近なところだとパズルがある．どんなパズルでも簡単に制約解消問題に落ちるわけではないが，例えば数独なんかはとても簡単に制約解消問題として記述できる．

Javaの制約解消系としてCreamがある．これは，神戸大学の田村研究室で開発されたシステムで，Javaのオブジェクトとして制約を記述し，解くことができる．

Cream のダウンロードと実行

バージョン番号が不思議なことになっていて，1.0, ..., 1.4 と順調に来ていたのに，次が 1.05, 1.06となっている．ちょっと不思議だ．ともあれ，最新版は1.06．上記ページからダウンロードできる．

zip ファイルをそのまま展開するとディレクトリをつくらず，src, classes, docs, buildというディレクトリができてしまうので，ディレクトリを作ってから展開した方がいい．

> mkdir cream
> cd cream
> unzip ../cream106.zip

build の中に cream106.jarとexample.jarがあるので，そのままサンプルを実行することができる．

まさに数独のサンプルexamples.Sudokuが入っているので実行してみよう．

$ java -cp build/cream106.jar:build/examples.jar \
examples.Sudoku 3
***** Problem 3
3 1 2 7 4 9 5 8 6 
9 6 5 1 3 8 7 2 4 
8 4 7 2 5 6 9 1 3 
6 7 1 4 2 3 8 5 9 
2 9 4 8 1 5 3 6 7 
5 3 8 6 9 7 2 4 1 
7 5 6 9 8 1 4 3 2 
4 8 9 3 6 2 1 7 5 
1 2 3 5 7 4 6 9 8

このサンプルは，ソースコード内にサンプルデータをいくつか持っている．引数の「3」は，サンプルデータの番号を指定したものである．ご覧の通り結果が出ている．プログラム中の3番の問題表現は次のようになっている．0が空欄を表している．

// 3
{{0,0,2,7,0,0,0,0,6},
 {9,0,0,0,0,0,7,2,4},
 {8,4,0,0,5,6,0,0,0},
 {0,0,1,0,0,0,0,5,9},
 {2,0,4,8,0,0,0,0,0},
 {0,0,0,6,9,7,2,0,0},
 {7,5,0,0,8,0,0,3,0},
 {0,8,0,3,0,0,1,0,0},
 {0,0,0,0,0,0,6,9,0}},

App Engine?

で，これをApp Engineで使ってみようと思ったのだけど，Creamは内部的にThreadを使っていて，App Engineのサンドボックス制約にひっかかって動かない．．．むう．意外に厳しい制約だな．まいった．