Cream + App Engine
Cream はThreadを用いて書かれている．これは，所与の制約条件を満たす解が複数ある場合，すべての解を求めると時間がかかりすぎたり，メモリ消費量が大きすぎることがあるので，1つの解ごとにユーザのプログラムに制御を移すためである．もちろんオブジェクトの中に状態を持っておけば，Iteratorのような感じで1つずつ解を返すことができるはずなのだけど，おそらくは，スタックの中に状態を保持しているために，そのような方法がとれなかったのだろう．Pythonであれば，generatorを使ってきれいに書けるんだけど．
ところが，App Engine ではスレッドを作らせてくれない．結構不便なので，なんとかしてほしいところだけど，今のところどうにもならない．なので，Creamのほうをちょっと改変?してしのぐことにする．
CreamのSolver
CreamのSolverの典型的な使い方はこんな感じ．
Solver solver = new DefaultSolver(net);
for (solver.start(); solver.waitNext(); solver.resume()) {
Solution solution = solver.getSolution();
...
}start() すると裏でソルバのスレッドが動きだし，waitNext()で次の解を待ってブロックする．Solverの中では，ひとつの解が見つかるたびに，successというメソッドが呼び出されていて，waitNext()に制御を移すようになっている．したがってsuccessをオーバライドしてやれば挙動を変えることができそうだ．
もちろん，Creamの本来の挙動である，ひとつ解が見つかるごとにユーザに制御を移すということはできなくなるが，解の上限数と，タイムアウト時間を指定できればとりあえずいいだろう．
で，書いてみたのが下のクラス．DefaultSolverのサブクラスとして書いてある．successメソッドはDefaultSolverのスーパクラスであるSolverのsuccessをオーバライドしている．というか，前半はSolverのsuccessからパチってきている．ロジックの中身は全然理解していないが，とりあえずそのまま残してある．ミソはsuccessメソッドの最後で，solutions.add(solution)しているところ．
public class SingleThreadSolver extends DefaultSolver {
public SingleThreadSolver(Network network) {
super(network);
}
protected synchronized void success() {
if (debug) {
System.out.println(name + " success");
}
if (isAborted())
return;
count++;
Thread.yield();
boolean better = updateBest();
if (isOption(BETTER)) {
if (getMonitor() != null) {
int value = solution.getObjectiveIntValue();
getMonitor().addData(this, value);
}
if (!better)
return;
} else {
if (getMonitor() != null) {
int value = solution.getObjectiveIntValue();
getMonitor().addData(this, value);
}
}
// solutions にsolutionを追加
solutions.add(solution);
if (maxSolutions <= solutions.size() ||
System.currentTimeMillis() > deadline)
stop();
}
protected List<Solution> solutions = null;
protected long deadline = 0;
protected int maxSolutions = 0;
public List<Solution> getSolutions(int maxSolutions,
long timeout) {
solutions = new ArrayList<Solution>();
this.maxSolutions = maxSolutions;
this.deadline = System.currentTimeMillis() + timeout;
run();
return solutions;
}
}使い方は，こんな感じ．
SingleThreadSolver solver = new SingleThreadSolver(net);
List<Solution> solutions = solver.getSolutions(10, 10 * 1000);
for (Solution solution: solutions) {
...
}
Sudoku on App Engine
で，これを使ってSudokuをとくアプリを作ってみる．まずはSudoku クラス．これは本質的にCreamのサンプルとして付いていたもので，
- 入出力のルーチンを追加
- SingleThreadSolverを使用するように改変
しただけである．
public class Sudoku {
public static int[][] parse(InputStream is) throws IOException {
LineNumberReader lnr = new LineNumberReader(new InputStreamReader(is));
int [][] result = new int[9][9];
for (int i = 0; i < 9; i++) {
String s = lnr.readLine();
int counter = 0;
for (int j = 0; j < s.length(); j++){
char c = s.charAt(j);
if (c <= '9' && c >= '0')
result[i][counter++] = (c - '0');
}
if (counter != 9)
throw new IOException("Parse Error: " + s);
}
return result;
}
public static List<int[][]> sudoku(int[][] v0) {
Network net = new Network();
int n = 9;
IntVariable[][] v = new IntVariable[n][n];
IntVariable[] vs = new IntVariable[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (v0[i][j] == 0)
v[i][j] = new IntVariable(net, 1, n);
else
v[i][j] = new IntVariable(net, v0[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
vs[j] = v[i][j];
new NotEquals(net, vs);
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++)
vs[i] = v[i][j];
new NotEquals(net, vs);
}
for (int i0 = 0; i0 < n; i0 += 3) {
for (int j0 = 0; j0 < n; j0 += 3) {
int k = 0;
for (int i = i0; i < i0+3; i++)
for (int j = j0; j < j0+3; j++)
vs[k++] = v[i][j];
new NotEquals(net, vs);
}
}
SingleThreadSolver solver = new SingleThreadSolver(net);
List<Solution> solutions = solver.getSolutions(10, 3*1000);
List<int[][]> result = new ArrayList<int[][]>();
for (Solution solution: solutions) {
int[][] oneSolution = new int[9][9];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
oneSolution[i][j] = solution.getIntValue(v[i][j]);
result.add(oneSolution);
}
return result;
}
public static String toStringOne(int[][] one){
StringBuffer sb = new StringBuffer();
for (int [] row: one) {
for (int col: row)
sb.append(col + " ");
sb.append("\n");
}
return sb.toString();
}
}これを使うサーブレットはこんな感じだ．
public class SudokuSolverServlet extends HttpServlet {
private static final Logger log =
Logger.getLogger(SudokuSolverServlet.class.getName());
public void doPost(HttpServletRequest req,
HttpServletResponse resp)
throws IOException {
UserService userService =
UserServiceFactory.getUserService();
User user = userService.getCurrentUser();
String input = req.getParameter("input");
List<int[][]> result = \
Sudoku.sudoku(Sudoku.parse(new ByteArrayInputStream(input.getBytes())));
resp.setContentType("text/html");
resp.setCharacterEncoding("utf-8");
resp.getWriter().println("<h1> Sudoku Results /h1>");
resp.getWriter().println("found " + result.size() + " answer(s).");
for (int[][] one: result)
resp.getWriter().println(
"<pre>\n"+
Sudoku.toStringOne(one) +
"</pre>\n<hr/>\n");
resp.getWriter().println(
"<a href=\"/sudoku.html\">Next Problem</a>");
}
}
