« JaCoP: Features request for version 2.4 | Main | Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more »

Comet: New models, e.g. Einstein puzzle, KenKen, Kakuro, Killer Sudoku, Stigler's Diet problem, translations of OPL models

Here are some of the new Comet models written the last week.

Findings this week

Representing KenKen, Kakuro, and Killer Sudoku

One important thing in modelling a problem is how to representing the data in the problem. For grid puzzles such as KenKen, Kakuro, and Killer Sudoku, where one of the objects is to operate (add, multiply, etc) on an array of unknown length, I found one representation which work quite well (at least on the simple problem I tested).

Let's take the KenKen problem from Wikipedia.

The first version kenken.co was quite large, and stated explicitly all the operations (addition, subtraction, multiplication, or division). This was slightly generalized in the same model, though.

After that I relaxed the requirement to state exactly which operation to do things actually got simpler to model. In the Comet model kenken2.co we represent an cell with a tuple (struct) as two integers 

tuple cell {

  int r;

  int c;

}

The cage of numbers to add (or multiply etc) is represented by another tuple, a set of cells, and the result (integer): 

tuple P {

  set{cell} c;

  int res;

}

Now, it is only to state the problem using this structure:

int num_p = 15; // number of cages/segments
P problem[1..num_p] = 
  [
   P({cell(1,1), cell(2,1)}, 11),
   P({cell(1,2), cell(1,3)}, 2),
   P({cell(1,4), cell(2,4)}, 20),
   P({cell(1,5), cell(1,6), cell(2,6), cell(3,6)}, 6),
   P({cell(2,2), cell(2,3)}, 3),
   P({cell(2,5), cell(3,5)}, 3),
   P({cell(3,1), cell(3,2), cell(4,1), cell(4,2)}, 240),
   P({cell(3,3), cell(3,4)}, 6),  
   P({cell(4,3), cell(5,3)}, 6),
   P({cell(4,4), cell(5,4), cell(5,5)}, 7),
   P({cell(4,5), cell(4,6)}, 30),  
   P({cell(5,1), cell(5,2)}, 6),
   P({cell(5,6), cell(6,6)}, 9),
   P({cell(6,1), cell(6,2), cell(6,3)}, 8),
   P({cell(6,4), cell(6,5)}, 2)
   ];

This representation makes it possible to reading a problem from a file etc (which has not been done, though).

The single function that calculates the values in the segment given the result is as follows. Note: Here I assume that division and subtraction will only be done for two sized sets.

function void calc(Solver m, set{cell} cc, var{int}[,] x, int res) {

  if (cc.getSize() == 2) {

    var{int} a(m, x.getRange(0));

    var{int} b(m, x.getRange(0));

    m.post(a == x[cc.atRank(0).r,cc.atRank(0).c]);

    m.post(b == x[cc.atRank(1).r,cc.atRank(1).c]);

    m.post((a + b == res) || (a * b == res) || 

           (a * res == b) || (b * res == a) || 

           (a - b == res) || (b - a == res));

  } else {

    m.post(sum(i in cc) x[i.r, i.c] == res || prod(i in cc) x[i.r, i.c] == res);

  }

}


In the exploreall we state the following constraints: 

// all rows and columns must be unique

  forall(i in R)

      m.post(alldifferent(all(j in R) x[i,j]));

  forall(j in R)

    m.post(alldifferent(all(i in R) x[i,j]));

  // the specific problem

  forall(i in 1..num_p) {

    calc(m, problem[i].c, x, problem[i].res);

  }

Now, the other two grid puzzles in Comet, Killer Sudoku, and Kakuro, is represented is the same way, using just slight modifications in the calc function and added or altered constraints.

For more about these three grid puzzles see Wikipedia's entries:
* KenKen
* Killer Sudoku
* Kakuro


Different solvers in one model: Sudoku generator


Speaking of grid puzzles, here is a (proof-of-concept) generator of Sudoko puzzles: sudoku_generate.co. It uses a simple and brute force approach:

* Generate a problem matrix with the proper number of unknowns
* Try to solve the problem. If there are exactly one solution, then all is fine, else generate another problem.

It also use two limits to ensure that one generation/solution is not
to costy (which may miss some good problems):
* timeout
* number of failures

The thing to note here is the way two different functions works together: first one constraint solver (model) to generate a Sudoku matrix, then another constraint solver (model) to really solve the Sudoko problem.


User defined constraints


Earlier I wrote how to define function in Comet, e.g. in Some Comet constraint programming (CP) models .

This week I wanted to state my own functions in the same way as the built in functions, e.g. as m.post(myConstraint(...));.

The following function implements the (global) constraint increasing, which then can be stated as m.post(increasing(x));. Please note that this is just a "modelling" constraint, and it will use the underlying solver propagation etc.

class increasing extends UserConstraint {

  var{int}[] _x;

  int _n;

  increasing(var{int}[] x) : UserConstraint() {

    _x = x;

    _n = _x.getSize();      

  }

  Outcome post(Consistency cl) {

    Solver cp = _x[1].getSolver();

    forall(i in 2.._n) {

      cp.post(_x[i-1] <= _x[i], cl);

    }

    return Suspend;

  }

  Outcome propagate() { 

     return Suspend;

  }  

}

The Comet model constraint_test.co implements the following constraints:

  • alldifferent_except_0
  • increasing
  • decreasing
  • toNum
  • correspondence

Translating OPL models

I've started to read Pascal Van Hentenryck's great book about OPL, "The OPL Optimization Programming Language", (ISBN: 9780262720304, unfortunately out of print), and it is quite clear the Comet "is not very unlike OPL". Which is not a big surprise since Van Hentenryck is the designer of both languages.

There are differences between Comet and OPL, sometimes quite big, but often they are easy to circumvent. Maybe later findings will discuss more about this.

The following Comet models are translations of OPL models, some of these are from the examples from ILOG's OPL Models.

  • building_a_house.co: Scheduling building a house (OPL). Comet use a different way of stating scheduling constraints than OPL.
  • covering_opl.co: Set covering problem. Also note the labeling (in the uses section), which solves the problem faster than with the default label, or labelFF.
  • einstein_opl.co: Einstein puzzle, translation of the OPL model from Daniel Selman's Einstein's Puzzle - Or, 'The Right Tool for the Job'. The presentation in the Comet model is different than the OPL model (which is shown commented) but it is quite close.
  • fixed_charge.co: Fixed-charge problem. One big difference here: In Comet it is not allowed to have an array in a tuple, so the use data must be a separate matrix.
  • number_square.co: From page 32 of Van Hentenryck's OPL book: Finding a eight digit square which remains a square when 1 is concatenated in from of it. This simple problem translates very well to Comet.
  • p_median_opl.co: P-median problem. This also translates very well to Comet.
  • production2.co: Production planning problem. Same difference as in the fixed charge model, where arrays in a tuple is not allowed.
  • warehouse.co: Warehouse location problem.


Models


Here are the new Comet models. As usual more information about the problem/model is in the header of the model.

Posted by hakank on February 21, 2009 09:47 AM |