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>");
  }
}

デプロイ

デプロイの際にちょっと面倒なことが起きた.よくわからないのだが,MacではJDK1.5がデフォルトになっているのだが,これを1.6にすると,AppEngineでデプロイできない.JDOのenhancerが1.6のクラスファイルに対応していないように見えるがそんなことあるだろうか.

ともあれ,Creamのjarは1.6でコンパイルされているので,1.5では動かない.が,ソースに1.6固有の点がある訳ではないので,リビルドすればOK.

で,ここにデプロイしてみた.

問題のパーザはずさんに書かれているので,0-9以外の文字はすべてデリミタとみなす.デリミタなしでもOK.