Quite a few new
Gecode models has been written to experiment with the new syntax sugar in Gecode version 3.4. Many of the models are Gecode versions of the models presented in
Some 40 new ECLiPSe models, where almost all of these where first done in MiniZinc and then SICStus Prolog before implementing in ECLiPSe. So, now it's time for Gecode versions. It is probably not very surprising that it is much easier to translate from the MiniZinc version to Gecode than from the two Prolog-based versions. I have implemented all but 2 of these "about 40" ECLiPSe models.
As I wrote in ..., the new syntactic sugar for
rel and
expr (substituting the
post in older Gecode versions) is very nice and it now much easier to write many constraints. As you may see in the examples, I also tend to (over)use the new append operator for
IntVarArgs; it is very handy sometimes, e.g. when you don't know - or don't care to calculate - the length of an array with "dynamically" created
IntVar's.
New Gecode models
Here are all the new models, often with comments about the problem or how I implemented them. Almost all of them has also been implemented in some - or all - of these systems:
Optimizing shopping basket
This is a rather straightforward translation of the MiniZinc model
shopping_basket6.mzn where described in
Optimizing shopping baskets: The development of a MiniZinc model and was presented in the StackOverflow question
How to use constraint programming for optimizing shopping baskets?. The object is to minimize the cost of a shopping basket where items are from different shops, and there is a delivery cost ("punishment") if the total from a shop is below a certain limit.
Some comments:
1) Calculating the delivery_cost "punishment"
For calculating the delivery cost for a shop, first a total for the shop is summed. Here we loop over all shops and all items, and the shop's item cost is added if the item is bought from this shop (or else the cost for the item is 0). The implication (
>>) is used. Here is my first attempt, i.e. to explicit state the two different cases:
rel(*this, (x[item] == shop) >> (this_shop_cost[item] == costs_m(shop,item)));
rel(*this, (x[item] != shop) >> (this_shop_cost[item] == 0));
However, there is a better way to state this constraint, better both in terms of modeling and propagation:
rel(*this,
this_shop_cost[item] ==
expr(*this, x[item] == shop)*costs_m(shop,item));
Then, given the total cost for this shop, we see if there is a delivery cost. Again, the implication is used. Note the combined condition that cost must be larger than 0 in order for checking the delivery cost. Here is the first (very explicit) try:
// the cost is larger than 0 but below the limit
rel(*this,
(shop_costs[shop] > 0 && shop_costs[shop] <= delivery_costs_limits[shop])
>>
(punish[shop] == delivery_costs[shop]));
// no punishment: either 0 or larger than the limit
rel(*this,
(shop_costs[shop] == 0 || shop_costs[shop] > delivery_costs_limits[shop])
>>
(punish[shop] == 0));
Again, a better solution was found (or crafted):
rel(*this,
punish[shop]==
expr(*this,
(shop_costs[shop] > 0 &&
shop_costs[shop] <= delivery_costs_limits[shop])
)*delivery_costs[shop]);
Probably this is slightly too influenced by MiniZinc's high-level syntax:
punish[j] =
delivery_costs[j]*bool2int(this_cost > 0 /\
this_cost < delivery_costs_limits[j])
Using the first two attempts cited above, the model first had 30031 failures (and about 11 seconds). With the two improvements the failures decreased to 5012 failures (and about 2 seconds).
The solution is - of course - the same as for the MiniZinc model.
There are two solutions with a minimal total of 42013. To show these two, use the following
command line options
shopping_basket6 -search dfs 42013
The result is below. Note that the the first shops is named 0 in the
x array, whereas in the MiniZinc model it is named 1.
total: 42013
x: {12, 19, 16, 17, 17, 12, 16, 16, 19, 12, 16, 16, 12, 12, 17, 16, 12, 12, 16, 7, 12, 35, 9, 16, 12, 12, 16, 19, 12}
item_costs: {345, 2921, 3074, 1233, 2554, 878, 1715, 3202, 2335, 639, 1644, 1606, 730, 1096, 1132, 1176, 1654, 1908, 2277, 298, 503, 927, 2182, 449, 397, 1246, 2145, 799, 558}
shop_costs: {0, 0, 0, 0, 0, 0, 0, 298, 0, 2182, 0, 0, 9954, 0, 0, 0, 17288, 4919, 0, 6055, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 927, 0}
punish: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 390, 0}
total: 42013
x: {12, 19, 16, 17, 17, 12, 16, 16, 19, 12, 16, 12, 12, 12, 17, 16, 12, 12, 16, 7, 12, 35, 9, 16, 12, 12, 16, 19, 12}
item_costs: {345, 2921, 3074, 1233, 2554, 878, 1715, 3202, 2335, 639, 1644, 1606, 730, 1096, 1132, 1176, 1654, 1908, 2277, 298, 503, 927, 2182, 449, 397, 1246, 2145, 799, 558}
shop_costs: {0, 0, 0, 0, 0, 0, 0, 298, 0, 2182, 0, 0, 11560, 0, 0, 0, 15682, 4919, 0, 6055, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 927, 0}
punish: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 390, 0}
When developing this Gecode model, I wanted to see all the intermediate results, i.e. the item costs, which shop had delivery costs (
punish), etc, and then I kept them in the final model.
Costas Array
Model:
costas_array.cpp
Generating
Costas Arrays (MathWorld, see also
Wikipedia's entry), has been a quite popular example in constraint programming. So here is my take.
This model is a port of my MiniZinc model
costas_array.mzn (which in its turn is based on Barry O'Sullivan's MiniZinc model
CostasArray.mzn).
Two comments:
- Note that the matrix, here defined by
Matrix<IntVarArray> diffs(differences, n, n);
is accessed diffs(column, row). I tend to forget this.
- Upper triangular matrix
The Costas array in this model is calculated by using a helper matrix where the n'th row represents the nth difference of the Costas array. This means that we just have to use the upper triangular matrix (the lower triangular is set to a constant value). For this we use the handy slice method which extracts just the part of the row we need:
for(int i = 0; i < n-1; i++) {
distinct(*this, diffs.slice(i+1,n,i,i+1), opt.icl());
}
Symmetry breaking
This model use one symmetry breaking option (
-symmetry min) which requires that the first element in the
costas array must be the minimum.
if (opt.symmetry() == SYMMETRY_MIN) {
min(*this, costas, costas[0], opt.icl());
}
For an array of 6, with this symmetry breaking there are 19 solutions (without: 119 solutions).
Divisible by 9 through 1 problem
divisible_by_9_through_1.cpp
The problem is from
Solving Combinatory Problems with LINQ:
Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:
1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible by 8.
3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4. And so on, until there's only one digit (which will necessarily be divisible by 1).
The Gecode code for this is (basically):
distinct(*this, digits, opt.icl());
for(int i = 0; i < n; i++) {
int m = base-i-1;
IntVarArray digits_slice(*this, digits.slice(0, 1, m));
to_num(*this, digits_slice, t[i], base, opt.icl());
rel(*this, t[i] % m == 0);
}
branch(*this, digits, INT_VAR_SIZE_MIN, INT_VAL_SPLIT_MAX);
slice for arrays
As I understand it,
slice for arrays is new in Gecode 3.4.0 (there have been a slice for matrices in earlier versions) and is very handy.
The above code could have been written somewhat more compact, by doing the slice part in the call to
to_num, but it don't looks as nice.
to_num(*this,
IntVarArray(*this, digits.slice(0, 1, m)),
t[i],
base,
opt.icl());
A related note: The constraint
to_num which ensures that the array
x contains the digitss (and in correct order) of the number
z in base
base can now be written as follows.
sum(coeffs, x) == z is a multiplication of the array
x with the array
coeffs. In this case, however, it takes slightly more propagations than using the
linear variant.
void to_num(Space & space, IntVarArray x, IntVar z, int base = 10, IntConLevel icl = ICL_BND) {
int len = x.size();
IntArgs coeffs(len);
for(int r = 0; r < len; r++) {
coeffs[r] = pow(base, len-r-1);
}
// linear(space, coeffs, x, IRT_EQ, z, icl); // older version
rel(space, sum(coeffs, x) == z, icl); // alternative version
}
Solutions
Due to integer overflow, this model cannot handle base > 10.
Answer: 381654729
t: {381654729, 38165472, 3816547, 381654, 38165, 3816, 381, 38, 3}
digits: {3, 8, 1, 6, 5, 4, 7, 2, 9} (in base 10)
The array
t is the progression of the truncated number (in base 10), and the array
digits contains the digits used.
For base=8 there are 3 solutions. (Note that the answer is in base 10.)
Answer: 1538257
t: {1538257, 192282, 24035, 3004, 375, 46, 5}
digits: {5, 6, 7, 4, 3, 2, 1} (in base 8)
Answer: 1391089
t: {1391089, 173886, 21735, 2716, 339, 42, 5}
digits: {5, 2, 3, 4, 7, 6, 1} (in base 8)
Answer: 874615
t: {874615, 109326, 13665, 1708, 213, 26, 3}
digits: {3, 2, 5, 4, 1, 6, 7} (in base 8)
Here is all solutions from base 2..10 where the number is
in base 10.
| Base | Solutions, base 10 ([digits in base]) |
| 2 | 1 ([1]) |
| 3 | - |
| 4 | 57 ([3,2,1]), 27 ([1,2,3]) |
| 5 | - |
| 6 | 7465 ([5,4,3,2,1]), 2285 ([1,4,3,2,5]) |
| 7 | - |
| 8 | 1538257 ([5,6,7,4,3,2,1]), 1391089 ([5,2,3,4,7,6,1]), 874615 ([3,2,5,4,1,6,7]) |
| 9 | |
| 10 | 381654729 ([3,8,1,6,5,4,7,2,9]) |
Compare with other implementations in other systems:
Broken weights
Gecode model:
broken_weights.cpp
This problem is from
Math Less Traveled:
Here's a fantastic problem I recently heard. Apparently it was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems published in 1612, and can also be found in Heinrich Dorrie's 100 Great Problems of Elementary Mathematics.
"""
A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds. What were the weights of the pieces?
"""
Note that since this was a 17th-century merchant, he of course used a balance scale to weigh things. So, for example, he could use a 1-pound weight and a 4-pound weight to weigh a 3-pound object, by placing the 3-pound object and 1-pound weight on one side of the scale, and the 4-pound weight on the other side.
It is a rather simple problem, much like the coins problem (
coins3.cpp) where the object is to find a combination of coins (of a certain nomination) to be able to give back changes for all values 1 to 99.
There is one significant difference between these problems, however: in this weights problem, the weights can be on either side of the balance scale, so instead of a simple 0..n representation (how many, is any, of each coin/weights to use), we use {-1,0,+1} where -1 means that a weight is on the left side of the scale and +1 means it is on the right size, and 0 means it is unused.
The main Gecode model is shown below.
weights is the weights to use (of size 4), and
orig_weight is the total weight (the original weight that was broken, here 40).
x (and it's matrix alias
x_m) is the representation of which weights to use ({-1,0,1 }) for each combination (from 1..40). Also, not shown here, we minimize the element last in the sorted
weights array.
// a matrix version of the different combinations of weights to use
Matrix<IntVarArgs> x_m(x, num_weights, orig_weight);
// symmetry breaking: order the weights
rel(*this, weights, IRT_LQ, opt.icl());
// sum of the weights is w
linear(*this, weights, IRT_EQ, orig_weight, opt.icl());
// all different weights from 1..40 must be combined
for(int w = 1; w <= orig_weight; w++) {
IntVarArray tmp(*this, num_weights, -orig_weight, orig_weight);
for(int c = 0; c < num_weights; c++) {
rel(*this, weights[c]*x_m(c,w-1) == tmp[c], opt.icl());
}
rel(*this, sum(tmp) == w, opt.icl());
}
branch(*this, weights, INT_VAR_DEGREE_MAX, INT_VAL_RANGE_MIN);
As noted above, this is a simple problem (and model). Some comments:
- It took me some time to realize that the
tmp array must have a range of -orig_weight..orig_weight.
- branching: We just need to branch on the
weights. One of the first tries, I branched just on x which was a bad idea (or I happened to pick the wrong variable/value selection).
- Note the use of the "alias"
sum for summing the tmp array.
Options
Well, the above solved the specific problem with original weight (
orig_weight) of 40 and 4 pieces (
num_weights). However, the model then developed in a more general and can now handle any (or should I write "any") combination of original weight and number of pieces.
Gecode don't have direct support for this kind of off-standard command lines options (there are a couple standard options, though). There is the much used
size option, which is often used for selecting a specific problem, or a size of some kind. But here we want to have two different options, so a dedicated option class was written:
class BrokenWeightsOptions : public Options {
private:
Driver::UnsignedIntOption _num_weights; // number of weights
Driver::UnsignedIntOption _orig_weight; // original weight
public:
// Initialize options
BrokenWeightsOptions(const char* n)
: Options(n),
_num_weights("-num_weights",
"number of weights",
4),
_orig_weight("-orig_weight",
"original weight",
40) {
add(_num_weights);
add(_orig_weight);
}
// Parse options from arguments argv (number is argc)
void parse(int& argc, char* argv[]) {
Options::parse(argc,argv);
}
unsigned int num_weights(void) const { return _num_weights.value(); }
unsigned int orig_weight(void) const { return _orig_weight.value(); }
};
Now we could test different problem, e.g. if there could be 3 number of pieces instead of 4:
broken_weights -num_weights 3 -orig_weight 40
Answer: no, it could not.
For the problem of original weight of 50 and 5 broken weights, the model came up with this solution (remember, we minimize the largest elements of the weights array):
weights: {1, 3, 9, 18, 19}
Another feature is the
-search option, which by default is
bab (branch & bound). Using
-dfs (depth first search),
all solutions is given instead of the minimal solution (or rather the
progression of minimal solutions).
Compare with the following implementations:
Strimko / Chain Sudoku
In
Strimko - Latin squares puzzle with "streams" (August 2009), I blogged about Strimko (a.k.a. Chain Sudoku) - then a rather new grid puzzle - based on Latin squares. For more about Strimko, see the references in that blog post.
The Gecode model for solving Strimko problems (including 6 instances) is
strimko2.cpp. Some of the constraints are shown below:
- the Latin Square constraint is modeled rather simple with the use of
Matrix alias.
- the new feature of array concatenation of
IntVarArgs. stream << x[i*n+j]; means: for each position in stream that belongs to "this" stream st, push the corresponding element in the decision variable array (matrix) x to the temporary array stream. All the values in stream must then be distinct.
Matrix<IntVarArray> x_m(x, n, n);
// Latin Square
for (int i = 0; i < n; i++) {
distinct(*this, x_m.row(i), opt.icl());
distinct(*this, x_m.col(i), opt.icl());
}
// streams
for(int st = 1; st <= n; st++) {
IntVarArgs stream;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if (streams[i*n+j] == st) {
stream << x[i*n+j];
}
}
}
distinct(*this, stream, opt.icl());
}
The problem also state some fixed hints in the grid, but the code for handling this is not shown.
Compare with the following models:
Futoshiki puzzle
Futoshiki puzzles are another Latin square based puzzles, with the additional twist that there are less-than (and greater-than) hints. Here is an example from Wikipedia:
The Gecode model
futoshiki.cpp is very much like Strimko model (modulo the different type of hints), so I don't show any code here. The program includes includes 3 examples, one is the Wikipedia example shown above.
Compare with the following models:
Latin square card puzzle
This problem is from Mario Livio's book about group theory "The Equation that couldn't be solved", page 22:
... Incidentally, you may get a kick out of solving this
eighteenth century card puzzle: Arrange all the jacks,
queens, kings, and aces from a deck of cards in a square so that
no suit or value would appear twice in any row, column, or the
two main diagonals.
The Gecode model is
latin_square_card_puzzle.cpp contains just a bunch of distinct (all different) constraints for distinct rows, columns, and the two diagonals.
The representation (for n=4) is rather simple: the value is the digit (here 0..3), and the 10's is the suits (0's, 10's, 20's, and 30's) and is access by mod respectively division with 10. So the complete list of valid values are
// values: i mod 10
0, 1, 2, 3, // suite 0: 0 div 10
10,11,12,13, // suite 1: 1 div 10
20,21,22,23, // suite 2: 2 div 10
30,31,32,33 // suite 3: 3 div 10
The initial domain of the grid (
x) is 0..n*10, but it is reduced by these valid values via an
IntSet, and the function
dom.
x(*this, n*n, 0, n*10)
// ...
// create all the valid values
IntArgs cards_a;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cards_a << i+m*j;
}
}
IntSet cards(cards_a); // convert to a IntSet
dom(*this, x, cards); // restrict the domain
Compare with the MiniZinc model
latin_square_card_puzzle.mzn (where the construction of all the
alldifferent's is much easier).
Note: There is a solution of n = 4 and n = 5, but not for n = 6. The n = 6 problem is the same as Euler's
36 officer's problem, which thus is not solvable. Also see
MathWorld
Latin squares
Gecode model:
latin_squares.cpp.
Just a simple decomposition of Latin squares constraint using Gecode's Matrix wrapper of a n*n
IntVarArray
void latin_square(Space& space, Matrix m,
IntConLevel icl = ICL_DOM) {
int n = m.width();
for(int i = 0; i < n; i++) {
distinct(space, m.row(i), icl);
distinct(space, m.col(i), icl);
}
}
It is called by the following:
Matrix m(x, n, n);
latin_square(*this, m, opt.icl());
Tourist site competition
Gecode model:
tourist_site_competition.cpp
This problem is from from Pierre Flener's presentation
Constraint Technology - A Programming Paradigm on the Rise (PDF), pages 5f: problem statement, pages 12f: model, pages 21ff: walktrough of a solution. Here with 7 tourist sites and 7 judges:
Every tourist site is visited by r = 3 judges.
Every judge visits c = 3 tourist sites.
Every pair of sites is visited by lambda = 1 common judge.
There are 151200 solutions to this problem. With the additional symmetry breaking constraint that Ali (judge 0 in the model) should visit Birka, Falun and Lund (sites 0,1,2) there are 4320 solutions.
This problem was also presented as "The Airline-of-the-Year Problem"
in Flener's presentation
Constraint Programming - Programming Paradigm on the Rise, page 4f. The problem is stated as follows for 7 airlines and 7 judges:
Constant jury: Every airline is tested by 3 judges.
Constant load: Every judge tests 3 airlines.
Equity: Every airline pair is tested by 1 common judge.
The model is a quite straight forward translation of the MiniZinc model
tourist_site_competition.mzn.
One note: The code for showing which sites a judge visits, and which judges visits a site is done with the following two
channel constraints:
// declarations
BoolVarArray x;
SetVarArray judges_where; // where are the judges
SetVarArray sites_who; // who visits this sites
Matrix x_m(x, num_judges, num_sites);
// ..
// Where are the judges?
for(int j = 0; j < num_judges; j++) {
channel(*this, x_m.col(j), judges_where[j]);
}
// Which judges visits the sites?
for(int s = 0; s < num_sites; s++) {
channel(*this, x_m.row(s), sites_who[s]);
}
Scheduling speakers
scheduling_speakers.cpp.
This problem is from from Rina Dechter's book "Constraint Processing", page 72 where the object is to schedule 6 speakers to 6 slots.
It is a very simple model, and the only problem was how to convert the list of available slots to set variable. Here is my solution, and maybe there is a better way,
3,4,5,6,
3,4,
2,3,4,5,
2,3,4,
3,4,
1,2,3,4,5,6
After first trying a more general but complicated variant (which is shown in the model), I settled with this simpler one, which works fine for this small example:
IntSetArgs available(n);
available[0] = IntSet( IntArgs() << 3 << 4 << 5 << 6 );
available[1] = IntSet( IntArgs() << 3 << 4 );
available[2] = IntSet( IntArgs() << 2 << 3 << 4 << 5 );
available[3] = IntSet( IntArgs() << 2 << 3 << 4 );
available[4] = IntSet( IntArgs() << 3 << 4 );
available[5] = IntSet( IntArgs() << 1 << 2 << 3 << 4 << 5 << 6 );
Then the constraints can be written
const static int n = 6;
// ...
x(*this, n, 1, n);
// ...
distinct(*this, x, opt.icl());
for(int i = 0; i < n; i++) {
// rel(*this, SetVar(*this, available[i],available[i]), SRT_SUP, x[i]);
rel(*this, singleton(x[i]) <= available[i]);
}
Where the for loop corresponds to this high-level code
forall(i in 1..n) (x[i] in available[i]).
PERT
Gecode model:
pert.cpp.
This is a simple PERT model in Gecode, from Pascal van Hentenryck
Scheduling and Packing In the Constraint Language cc(FD), page 7f.
Compare with the following models:
Lichtenstein coloring problem
Gecode model:
lichtenstein_coloring.cpp.
This problem is from bit-player:
The chromatic number of Liechtenstein
It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south).
...
In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?
Also, see Mikael Johansson's post at Michi's blog
On the chromatic number of Lichtenstein where I got the connections between communes/enclaves of Lichtenstein.
Apart from quite a lot of preparations, in terms of initializing arrays etc, this model was surprisingly easy to convert from the MiniZinc model (
lichtenstein_coloring.mzn).
An example: the symmetry breaking constraint to ensure that we must take the colors in order - i.e. start from color 0, then 1, and so on - we can now (in Gecode 3.4) use the following; it was slightly less writable/readable in earlier versions.
for(int c = 1; c < num_colors; c++) {
rel(*this, (color_used[c]==1) >> (color_used[c-1]== 1));
}
With this and the other symmetry breaking constraint that we assign a particular commune (Balzers) with the color 0, there are 1872 solutions. They are shown when using
-search dfs.
Also, compare with the following models:
Averbach seating problem
Gecode model:
averbach_1.4.cpp.
This is Problem 1.4 from Averbach & Chein "Problem Solving Through Recreational Mathematics":
Messr Baker, Dyer, Farmer, Glover, and Hosier are seated around a circular table, playing poker. Each gentleman is the namesake of the profession of one of the others.
The dyer is seated two places to the left of Mr Hosier.
The baker sits two places to Mr Baker's right.
The farmer is seated to the left of Mr Farmer.
Mr Dyer is on the glover's right.
What is the name of the dyer?
The only tricky part here was the modulo constraints (and these constraints are about all there is). The constraint
The dyer is seated two places to the left of Mr Hosier can be translated into the high-level expression
dyer = (Hosier - 2) mod 5 which is nearly exactly how to express it in Gecode:
rel(*this, baker == (Baker + 2) % 5);
This could also be written by explicit use the
mod constraint:
IntVar c5(*this, 5, 5);
mod(*this, expr(*this, Baker + 2), c5, baker);
As you probably have understood now, I prefer the first, shorter version.
Fill-a-pix
Gecode model:
fill_a_pix.cpp
From Conceptis Puzzles:
Fill-a-Pix rules:
Fill-a-Pix is a Minesweeper-like puzzle based on a grid with a pixilated picture hidden inside. Using logic alone, the solver determines which squares are painted and which should remain empty until the hidden picture is completely exposed.
Given a grid of hints with the number of painted squares around a specific square, the object is to figure out (pun intended) the painted squares.
X refers to an unknown (and is represented with -1 in the model).
X,X,X,X,X,X,X,X,0,X,
X,8,8,X,2,X,0,X,X,X,
5,X,8,X,X,X,X,X,X,X,
X,X,X,X,X,2,X,X,X,2,
1,X,X,X,4,5,6,X,X,X,
X,0,X,X,X,7,9,X,X,6,
X,X,X,6,X,X,9,X,X,6,
X,X,6,6,8,7,8,7,X,5,
X,4,X,6,6,6,X,6,X,4,
X,X,X,X,X,X,3,X,X,X
This problem has just one combined constraint, and again the new syntactic sugar makes it rather easy to state: for each square which is not
X, we require that there are this number of neighbours which are painted (has value 1).
n is the dimension of the grid and
prob is the hints of the problem instance (an array of integers).
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// get the data from the instance
int p = prob[c++];
if (p > X) {
IntVarArgs tmp;
// must be inside the grid
for(int a = -1; a <= 1; a++) {
for(int b = -1; b <= 1; b++) {
if (i+a >= 0 && i+a < n &&
j+b >= 0 && j+b < n) {
tmp << x[(i+a)*n+(j+b)];
}
}
}
rel(*this, p == sum(tmp));
}
}
}
This model was inspired/derived from my MiniZinc model (
fill_a_pix.mzn which in turn was derived from my Minesweeper in MiniZinc (
minesweeper.mzn).
Compare with the following models:
Also, see with the Minesweeper example from the Gecode distribution:
minesweeper.cpp.
Minesweeper 2
Gecode model:
minesweeper2.cpp
Since the Fill-a-pix problem (see above) is quite like the Minesweeper problem, I also implemented a Minesweeper model based on the Fill-a-pix model.
The first 10 problem instances was borrowed from the Minesweeper example from the Gecode distribution (
minesweeper.cpp). I added the 7 instances that was included with the MiniZinc model (see my
MiniZinc page for a list of these instances); some of these are not square matrices.
Here is the main constraint for the Minesweeper model. It is very much the same as for Fill-a-pix, with some exceptions:
- It supports non-square problems
- Two extra constraints are added:
- If a cell has a hint, then it cannot be a bomb
- If a cell contains a bomb then it cannot be numbered.
for(int i = 0; i < rows; i++) {
cout << " ";
for(int j = 0; j < cols; j++) {
int p = prob[c++]; // get data
IntVar pp(*this, p, p);
rel(*this, (pp > XX) >> (x[i*cols+j] == 0));
rel(*this, (x[i*cols+j] == 1) >> (pp == XX));
if (p > X) {
IntVarArgs tmp;
for(int a = -1; a <= 1; a++) {
for(int b = -1; b <= 1; b++) {
if (i+a >= 0 && i+a < rows &&
j+b >= 0 && j+b < cols) {
tmp << x[(i+a)*cols+(j+b)];
}
}
}
rel(*this, p == sum(tmp));
}
}
}
Clock triplets
Gecode model:
clock_triplets.cpp.
Problem formulation from the F1 Compiler
example:
Dean Clark's Problem (Clock Triplets Problem)
The problem was originally posed by Dean Clark and then presented to a larger audience by Martin Gardner.
The problem was discussed in Dr. Dobbs's Journal, May 2004 in an article by Timothy Rolfe. According to the article, in his August 1986 column for Isaac Asimov's Science Fiction Magazine, Martin Gardner presented this problem:
"""
Now for a curious little combinatorial puzzle involving the twelve numbers on the face of a clock. Can you rearrange the numbers (keeping them in a circle) so no triplet of adjacent numbers has a sum higher than 21? This is the smallest value that the highest sum of a triplet can have.
"""
Mr Greenguest fancy dress problem
Gecode model:
fancy.cpp.
Problem formulation and
LPL code:
Mr. Greenfan wants to give a dress party where the male guests
must wear green dresses. The following rules are given:
1 If someone wears a green tie he has to wear a green shirt.
2 A guest may only wear green socks and a green shirt
if he wears a green tie or a green hat.
3 A guest wearing a green shirt or a green hat or who does
not wear green socks must wear a green tie.
4 A guest who is not dressed according to rules 1-3 must
pay a $11 entrance fee.
Mr Greenguest wants to participate but owns only a green shirt
(otherwise he would have to pay one for $9). He could buy
a green tie for $10, a green hat (used) for $2 and green socks
for $12.
What is the cheapest solution for Mr Greenguest to participate?
Jobs puzzle
Gecode model:
jobs_puzzle.cpp.
This is a standard problem in Automatic Reasoning. Problem formulation from Larry Wos'
problem page:
Jobs Puzzle
There are four people: Roberta, Thelma, Steve, and Pete. Among them, they hold eight different jobs. Each holds exactly two jobs. The jobs are chef, guard, nurse, clerk, police officer (gender not implied), teacher, actor, and boxer. The job of nurse is held by a male. The husband of the chef is the clerk. Roberta is not a boxer. Pete has no education past the ninth grade. Roberta, the chef, and the police officer went golfing together.
Question: Who holds which jobs?
Heterosquare
Gecode model:
heterosquare.cpp.
Problem from
Comet's old Wiki:
A heterosquare of order n is a n*n square whose elements are distinct integers from 1 to n^2 such that the sums of the rows, columns and diagonals are all different. Here is an example of heterosquare of order 3
19
1 2 3 6
8 9 4 21
7 6 5 18
16 17 12 15 (Sums)
The constraints are shown below. One can note the expression
sum(m.row(i)) == row_sums[i] (i.e. sum over a row in the matrix); I wasn't sure if it would work. I have also noted that I've been lazy and use the append array operator (
<<) quite much.
Matrix m(x, n, n);
// all the entries in the matrix should be different
distinct(*this, x);
// and all sums should be different
IntVarArgs all_sums;
all_sums << row_sums; // append to the array all_sums
all_sums << col_sums;
all_sums << diag1;
all_sums << diag2;
distinct(*this, all_sums);
// rows/column sums and diagonals
IntVarArgs v_diag1;
IntVarArgs v_diag2;
for(int i = 0; i < n; i++) {
rel(*this, sum(m.row(i)) == row_sums[i]);
rel(*this, sum(m.col(i)) == col_sums[i]);
v_diag1 << m(i,i);
v_diag2 << m(n-i-1,i);
}
rel(*this, sum(v_diag1) == diag1);
rel(*this, sum(v_diag2) == diag2);
Some trivia: Without any symmetry breaking, there are 24960 solution of order 3, i.e. a 3 by 3 matrix. The first one is:
| 14 (diag2)
1 2 3 = 6
4 5 8 = 17
6 9 7 = 22
---------------
11 16 18 | 13 (diag1)
Compare with the following implementations:
Some explorations of ISBN13
Gecode model:
isbn.cpp.
This model is just for exploring
ISBN13.
Put the ISBN (with 12 or 13 digits) to check at the command line:
./isbn 978052112549, and the program will print the check digit (9). If we put a shorter ISBN13, e.g with 11 digits (
97805211254), then the program will print all the ISBN13 that matches, i.e. will calculate the two last digits in the number:
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 7, 1} checkdigit: 1
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 6, 2} checkdigit: 2
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 5, 3} checkdigit: 3
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 4, 4} checkdigit: 4
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 3, 5} checkdigit: 5
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 2, 6} checkdigit: 6
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 1, 7} checkdigit: 7
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 0, 8} checkdigit: 8
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 9} checkdigit: 9
Note: The digit check for ISBN uses two constants 3 and 1 (which I call
mult0 and
mult1 in the model). If we let these two "free" (see below how to do that) then there are 90 different numbers that satisfies the first 12 digits. Some of them are (chosen to have not the same check digit):
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 1} checkdigit: 1
mult0: 1
mult1: 0
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 1} checkdigit: 1
mult0: 1
mult1: 5
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 1} checkdigit: 1
mult0: 3
mult1: 3
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 5} checkdigit: 5
mult0: 9
mult1: 6
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 6} checkdigit: 6
mult0: 0
mult1: 1
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 8} checkdigit: 8
mult0: 8
mult1: 5
ISBN13: {9, 7, 8, 0, 5, 2, 1, 1, 2, 5, 4, 9, 9} checkdigit: 9
mult0: 1
mult1: 3
The mult's can be stated on command line:
./isbn ISBN mult0 mult1
Example:
isbn 978052112549 3 1 for the default multiplicators. The value
11 (or any value larger than 9) is to let one
mult free, e.g.
isbn 978052112549 11 11 for letting both free, where we get the 90 solutions mentioned above.
Compare with the following models:
Covering (OPL)
Gecode model:
covering_opl.cpp.
This problem is from the OPL example
cover.mod, where the object is to find a minimum cover of workers for a set of tasks. See the Comet model
covering_opl.co for a fairly OPL-like model.
I thought it would be easy to model this problem in Gecode. This Comet constraint is about the only constraint in the model (except for the cost calculation), and it ensures that there is at least one qualified worker for each task:
forall(j in Tasks)
m.post(sum( c in Qualified[j] )
Hire[c] >= 1);
However, it took quite a time to get this correct. Here is the different stages of the model.
My first approach was to translate this to the following Gecode snippet.
Qualified is an
IntSetArgs array of the workers qualified for each task,
Hire is an
IntVarArray of values 0..1, indicating that a workers is hired. The code loop through all the tasks and each workers (
w) to sum the qualified and hired workers. We have two boolean arrays here:
is_qualified[w] is
true (i.e. 1) if this worker is qualified for the task, and
is_qualified_and_hired[w] is set if this worker is qualified
and hired.
for(int t = 0; t < num_tasks; t++) {
SetVar s(*this, Qualified[t], Qualified[t]);
BoolVarArray is_qualified(*this, nbWorkers, 0, 1);
BoolVarArray is_qualified_and_hired(*this, nbWorkers, 0, 1);
for(int w = 0; w < nbWorkers; w++) {
// is this worker qualified for this task?
rel(*this, s, SRT_SUP, IntVar(*this, w, w), is_qualified[w]);
// if this worker is qualified _and_ hired
// then it's a count
rel(*this, (is_qualified[w] && Hire[w] == 1) ==
(is_qualified_and_hired[w] == 1));
}
// there must be some worker hired for this task
rel(*this, sum(is_qualified_and_hired) >= 1);
}
We have seen the set operator
SRT_SUP before, in the
Scheduling speakers, and like that problem, some trickery was needed to convert the set of qualified workers to this model (and that is more a C++ issue than a Gecode thing).
After some thought, I changed to this more compact version using the set constraint in an
expr:
for(int t = 0; t < num_tasks; t++) {
SetVar s(*this, Qualified[t], Qualified[t]);
BoolVarArray is_qualified_and_hired(*this, nbWorkers, 0, 1);
for(int w = 0; w < nbWorkers; w++) {
// if this worker qualified _and_ hired then it's a count
rel(*this, (expr(*this, s >= IntSet(w,w)) && Hire[w] == 1) ==
(is_qualified_and_hired[w] == 1));
}
// must be some worker hired for this task
rel(*this, sum(is_qualified_and_hired) >= 1);
}
I would rather like to loop over just the qualified workers in the
Qualified[t] set, but I didn't know how to do that yet.
Ah. Some minutes later I figured it out (by reading the documentation about
IntSet in more detail). This is definitely more like it:
for(int t = 0; t < num_tasks; t++) {
IntSet tt(_QualifiedSet[t]);
BoolVarArgs bb;
for(int w = 0; w < nbWorkers; w++) {
// is this worker qualified?
if (tt.in(w)) {
// then: is he/she hired?
bb << expr(*this, Hire[w] == 1);
}
}
// at least one worker must hired for this task
rel(*this, sum(bb) >= 1);
}
Pi Day Sudoku 2009
Gecode model:
sudoku_pi.cpp.
Problem from
Brain Freeze Puzzles/a>, and 360 Pi Day Sudoku 2009:
Each row, column, and region contains the digits 1-9 exactly once plus three Pi symbols.
I wrote about this problem in
Pi Day Sudoku 2009 - the models (MiniZinc and Comet), and the two models in MiniZinc (
sudoku_pi.mzn) and Comet (
sudoku_pi.co).
The Gecode model was surprisingly easy to do, maybe except for changing from 1-based to 0-based indexing for the hints and using an array based representation instead of a matrix proper. The constraints is just a lot of global cardinality constraint (
count in Gecode); we cannot use the alldifferent constraints (
distinct in Gecode) since there are (exactly) three occurrences of Π (this symbol should be a fancy Pi) in each row/column/region.
Set partition
Gecode model:
set_partition.cpp.
Set partition problem. From
Koalog:
Given the set S = {1, 2, ..., n}, it consists in finding two sets A and B such that:
* A union B = S
* |A| = |B|
* sum(A) = sum(B)
* sum_squares(A) = sum_squares(B)
This model uses set variables and set operations for union, cardinality etc. The sums and squared sums are calculated by using the set variable method
weights.
In the Gecode distribution there is also a model of this problem. However it use integer variables and a lot of redundant/efficiency constraints.
Mr Smith problem
Gecode model:
mr_smith.cpp.
Logic problem from an
IF Prolog example:
The Smith family and their three children want to pay a visit but they do not all have the time to do so. Following are few hints who will go and who will not:
o If Mr Smith comes, his wife will come too.
o At least one of their two sons Matt and John will come.
o Either Mrs Smith or Tim will come, but not both.
o Either Tim and John will come, or neither will come.
o If Matt comes, then John and his father will also come.
Here the new boolean operators in Gecode shines. In earlier version this would be much harder to write (and read):
BoolVar
Mr_Smith(L[0]),
Mrs_Smith(L[1]),
Matt(L[2]),
John(L[3]),
Tim(L[4]);
// If Mr Smith comes, his wife will come too.
rel(*this, Mr_Smith >> Mrs_Smith);
// At least one of their two sons Matt and John will come.
rel(*this, Matt || John);
// Either Mrs Smith or Tim will come, but not both.
rel(*this, Mrs_Smith + Tim == 1);
// Either Tim and John will come, or neither will come.
rel(*this, Tim == John);
// If Matt comes, then John and his father will also come.
rel(*this, Matt >> (John && Mr_Smith));
Talisman square
Gecode model:
talisman_square.cpp.
From MathWorld
Talisman Square:
An n x n array of the integers from 1 to n^2 such that the difference between any one integer and its neighbor (horizontally, vertically, or diagonally, without wrapping around) is greater than or equal to some value k is called a (n,k)-talisman square.
Since this problem used two parameters (
n and
k) I wrote a special option class (using the standard
SizeOption just gives the possibility of one optional parameter).
class TalismanSquareOptions : public Options {
private:
Driver::UnsignedIntOption _n_option;
Driver::UnsignedIntOption _k_option;
public:
TalismanSquareOptions(const char* n)
: Options(n),
_n_option("-n",
"n value",
5),
_k_option("-k",
"k value",
4)
{
add(_n_option);
add(_k_option);
}
void parse(int& argc, char* argv[]) {
Options::parse(argc,argv);
}
unsigned int k(void) const { return _k_option.value(); }
unsigned int n(void) const { return _n_option.value(); }
};
And then, the program can be called with the following parameters
./talisman_square -k 3 -n 10
Curious numbers
Gecode model:
cur_num.cpp.
Problem: Curious Numbers (#114) from Dudeney "Amusements in Mathematics".
Curious set of integers
Gecode model:
curious_set_of_integers.cpp.
From Martin Gardner:
The integers 1,3,8, and 120 form a set with a remarkable property: the product of any two integers is one less than a perfect square. Find a fifth number that can be added to the set without destroying this property.
Bin packing problems
Gecode model:
bin_packing.cpp.
This is a rather simple, or at least straightforward, model of bin packing. It includes the same 9 problem as the SICStus Prolog model (
bin_packing.pl).
There is an extra option (
-symmetry sort) which sorts the entries (the
stuff array) before trying to pack, and it is - to no surprise - quite faster.
Exodus (Dell Logic Puzzles)
Gecode model:
exodus.cpp.
One new addition of rel-expressions is
element which is used in this model. Instead of the following with temporary
IntVar:s and
element constraints:
IntVar Age_Yemen(*this, dom_ages);
element(*this, Age, Yemen, Age_Yemen);
IntVar Age_Ethiopia(*this, dom_ages);
element(*this, Age, Ethiopia, Age_Ethiopia);
We can now simply write:
rel(*this, element(Age,Yemen) < element(Age,Ethiopia));
However, the following is still
not possible to write since
Yemen and
Ethiopia is IntVar:
rel(*this, Age[Yemen] < Age[Ethiopia]);
Maybe this will come is later version?
Note: As I noted this use of
element expression rather late, not all models use it. Also, sometimes it is better to use the temporary version and
element constraint, for example where the domain of the (temporary) variable should be tweaked in some way.
Scheduling problem I
Gecode model:
schedule1.cpp.
Scheduling problem from
SICStus Prolog.
This model use the new scheduling constraint
cumultive which is a simpler version of the existing constraint
cumulatives. (See
Scheduling with the cumulatives constraint in Gecode for more about
cumulatives.)
Set covering problem II
Gecode model:
set_covering2.cpp.
Set covering problem from Taha: "Operations Research - An Introduction". Example 9.1-2: Minimize the number of security telephones in street corners on a campus.
Set covering problem III
Gecode model:
set_covering3.cpp.
Set covering problem from Murty: "Optimization Models for Decision Making", page 302f.
Set partition/set covering problem
Gecode model:
set_covering4.cpp.
Problem from Lundgren, Rönnqvist, Värbrand "Optimeringslära", page 408: minimize the cost of the alternatives which covers all the objects. This model has also an option for solving it either as set partition problem (parameter
0) or as a set covering problem (parameter
1).
Set covering (Skiena)
Gecode model:
set_covering_skiena.cpp.
From Steven Skiena: The Stony Brook Algorithm Repository.
Set cover.
Combinatorial auction
Gecode model:
combinatorial_auction.cpp.
This example is from the Wikipedia article
Combinatorial_auction. It is here implemented as a set partition problem.
Just forgotten problem (Enigma 1517)
Gecode model:
just_forgotten.cpp.
Huey, Dewey and Louie problem
Gecode model:
huey_dewey_louie.cpp.
K4P2 Graceful Graph
Gecode model:
K4P2GracefulGraph2.cpp.
3 jugs problem
Gecode model:
3_jugs2.cpp.
The famous 3 jugs problem with a constraint programming bent (or MIP bent if you like it).
Knapsack investments problem
Gecode model:
knapsack_investments.cpp.
Decide which projects should be investment in, with some extra requirements.
Decomposition of global constraint all_differ_from_at_least_k_pos
Gecode model:
all_differ_from_at_least_k_pos.cpp.
Decomposition of global constraint all_equal
Gecode model:
all_equal.cpp.
Decomposition of global constraint all_min_dist
Gecode model:
all_min_dist.cpp.
Decomposition of global constraint alldifferent_cst
Gecode model:
alldifferent_cst.cpp.
Decomposition of global constraint alldifferent_modulo
Gecode model:
alldifferent_modulo.cpp.
Decomposition of global constraint alldifferent_on_intersection
Gecode model:
alldifferent_on_intersection_modulo.cpp.
Decomposition of global constraint among
Gecode model:
among.cpp.
Decomposition of global constraint among_seq
Gecode model:
among_seq.cpp.
Decomposition of global constraint bin_packing
Gecode model:
bin_packing2.cpp.
Decomposition of global constraint distribute
Gecode model:
distribute.cpp.
Decomposition of global constraint inverse
Gecode model:
inverse.cpp.
Averbach seating problem 1.2
Gecode model:
averbach_1.2.cpp.
This is another seating problem from Averbach & Chein, problem 1.2.
Averbach seating problem 1.3
Gecode model:
averbach_1.3.cpp.
A logical puzzle (men, wifes and ponies) from Averbach & Chein, problem 1.3.
Hamming distance
Gecode model:
hamming_distance.cpp.
Hanging weights puzzle
Gecode model:
hanging_weights.cpp.
Problem from
Using LINQ to solve puzzles.
Magic hexagon puzzle (CSPLib problem 23)
Gecode model:
magic_hexagon.cpp.
This is problem 23 from
CSPLib. Also, see the model (and comments) in
ESSENCE.
Bales of Hay problem
Gecode model:
bales_of_hay.cpp.
Problem from The Math Less Traveled:
The haybaler.
Warehouse location problem
Gecode model:
warehouse.cpp.
From OPL model warehouse.mod. Note: There is a
warehouses model in the
Gecode distribution that solves the same problem, and that is also used as
case study example in the excellent "Modeling and Programming with Gecode"
(which I read some month ago).
However, my Gecode model was translated rather directly from the Comet model
warehouse.co and without
looking at the distributed model.
Marathon puzzle
Gecode model:
marathon2.cpp.
The problem is from an example of
Xpress, but I cannot find the page.
Dominique, Ignace, Naren, Olivier, Philippe, and Pascal have arrived as the first six at the Paris marathon. Reconstruct their arrival order from the following information:
a) Olivier has not arrived last
b) Dominique, Pascal and Ignace have arrived before Naren and Olivier
c) Dominique who was third last year has improved this year.
d) Philippe is among the first four.
e) Ignace has arrived neither in second nor third position.
f) Pascal has beaten Naren by three positions.
g) Neither Ignace nor Dominique are on the fourth position.
Olympic puzzle
Gecode model:
olympic.cpp.
This is a Prolog benchmark problem.
Seesaw problem
Gecode model:
stuckey_seesaw.cpp.
From Marriott & Stuckey "Programming with Constraints", page 257: Balancing on a seesaw.
Fractions problem
Gecode model:
olympic.cpp.
This is another Prolog benchmark problem.
Killer Sudoku
Gecode model:
killer_sudoku.cpp.
Killer Sudoku is yet another grid puzzle. This model solve the example shown at the Wikipedia page.
Kakuro
Gecode model:
kakuro.cpp.
Kakuro is yet another grid puzzle. This model solve the example shown at the Wikipedia page.
KenKen
Gecode model:
kenken2.cpp.
KenKen is yet another grid puzzle. This model solve the example shown at the Wikipedia page.
A Round of Golf (Dell Logic Puzzles)
Gecode model:
a_round_of_golf.cpp.
Abbot's Puzzle
Gecode model:
abbots_puzzle.cpp.
Abbot's puzzle ("Amusements in Mathematics, Dudeney", number 110)
Added Corner
Gecode model:
added_corner.cpp.
Arch Friends (Dell Logic Puzzles)
Gecode model:
arch_friends.cpp.
Babysitting (Dell Logic Puzzles)
Gecode model:
babysittning.cpp.
Breaking News (Dell Logic Puzzles)
Gecode model:
breaking_news.cpp.
Four Islands (Dell Logic Puzzles)
Gecode model:
four_islands.cpp.
Lecture Series (Dell Logic Puzzles)
Gecode model:
lecture_series.cpp.
Tunapalooza (Dell Logic Puzzles)
Gecode model:
tunapalooza.cpp.
Five brigands problem
Gecode model:
five_brigands.cpp.
The Five Brigands problem from Dudeney: "Amusements in Mathematics" (number 133)
Circling Squares
Gecode model:
circling_squares.cpp.
From Dudeney: "Amusements in Mathematics".
Mama's Age
Gecode model:
circling_squares.cpp.
From Dudeney: "Amusements in Mathematics", number 40.
Mrs Timpkin's Age
Gecode model:
timpkin.cpp.
From Dudeney: "Amusements in Mathematics", number 43.
Torn Number
Gecode model:
torn_number.cpp.
From Dudeney: "Amusements in Mathematics", number 113.
Twin letters problem
Gecode model:
twin_letters.cpp.
Monks and doors problem
Gecode model:
monks_and_doors.cpp.
Contracting Costs
Gecode model:
contracting_costs.cpp.
From "Mathematical Puzzles of Sam Loyd, Volume 2", number 20.
General Store
Gecode model:
general_store.cpp.
From "Mathematical Puzzles of Sam Loyd, Volume 2", number 30.
Crypta (cryptarithmetic puzzle)
Gecode model:
curious_set_of_integers.cpp.
Prolog benchmark problem.
All interval
Gecode model:
all_interval.cpp.
Note: This is a fairly true port from the MiniZinc model
all_interval.mzn, and it's not very fast. A faster implementation is in the Gecode distribution:
all-interval.
Devil's Word
Gecode model:
devils_word.cpp.
Translate each character in a word to ASCII value and then try to sum its values (either positive or negative) to a total. Compare with my CGI program
Devil's Word
Dinner problem
Gecode model:
dinner.cpp.
A very simple dinner problem.
Music Men
Gecode model:
music_men.cpp.
Yet another logical puzzle.
Number of days problem
Gecode model:
number_of_days.cpp.
Problem from Nathan Brixius' blog post
Solving a Knapsack problem with Solver Foundation and LINQ.
Pigeon hole problem
Gecode model:
pigeon_hole.cpp.
Pandigital numbers
Gecode model:
pandigital_numbers.cpp.
Seven-11 problem
Gecode model:
seven11.cpp.
Ski assignment problem
Gecode model:
ski_assignment.cpp.
Smuggler's knapsack problem
Gecode model:
smuggler_knapsack.cpp.
Smuggler's knapsack problem from Marriott & Stuckey "Programming with constraints", page 101f, 115f
Square root of WONDERFUL
Gecode model:
square_root_of_wonderful.cpp.
From Martin Gardner.
Place number puzzle
Gecode model:
place_number_puzzle.cpp.
Post office problem
Gecode model:
post_office_problem2.cpp.
Problem from Wayne Winston's "Operations Research: Applications and Algorithms": minimizing the number of workers at a post office.
Pythagoras
Gecode model:
pythagoras.cpp.
Generating solutions of A^2 + B^2 = C^2 for A,B,C
0..Int::Limits::max.
Rabbits problem
Gecode model:
rabbits.cpp.
A very simple linear problem from Pascal Van Hentenryck: "The OPL Optimization Programming Language", page 9.
Remainders problem
Gecode model:
remainders.cpp.
From Kordemsky.
Safe cracking problem
Gecode model:
safe_cracking.cpp.
Miss Manners' seating problem
Gecode model:
miss_manners.cpp.
Problem formulation from
CP-standards:
The "Miss Manners" problem is a notorious benchmark for rule engines. The problem is to find an acceptable seating arrangement for guests at a dinner party. It should match people with the same hobbies (at least one), and to seat everyone next to a member of the opposite sex.
I'm somewhat reluctant to publish this model: Although the solution is shown after just a second, it takes "forever" to prove that it is the best. Well, maybe it just a question of correct labeling, but I have found none efficient.