A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1%------------------------------------------------------------------------------%
2% Placing 'Hearts' on Corners in Equilateral Triangular Grids
3%
4% The problem is to find, for an equilateral triangular grid of
5% side N, the maximum number of grid nodes that can have a 'heart' placed
6% on them without any placed heart lying on the corners of an equilateral
7% triangle of any size or orientation.
8%
9% (Taken from Daily Telegraph and Sunday Times)
10%------------------------------------------------------------------------------%
11% Parameters
12
13int: n; % Number of sides of the grid
14set of int: N = 1..n;
15
16%------------------------------------------------------------------------------%
17% Variables
18
19array [N, N] of var 0..1: heart; % Grid of equilateral triangulars
20
21var 1..n*n: objective; % Number of 'hearts' in the grid
22
23constraint objective = sum(i in N, j in 1..i)(heart[i, j]);
24
25%------------------------------------------------------------------------------%
26% Constraints
27
28 % 'Hearts' constraints
29 %
30constraint
31 forall(i in 1..n, j in 1..i, k in 1..n-i, m in 0..k-1)(
32 heart[i+m, j] + heart[i+k, j+m] + heart[i+k-m, j+k-m] <= 2
33 );
34
35constraint
36 forall(i in 1..n, j in (i+1)..n)(
37 heart[i, j] = 0
38 );
39
40%------------------------------------------------------------------------------%
41% Search and Objective
42
43solve
44 :: search
45 maximize objective;
46
47ann: search =
48 int_search(
49 [heart[i, j] | i in N, j in 1..i], input_order, indomain_max, complete
50 );
51
52%------------------------------------------------------------------------------%
53% Output
54
55output [
56 "objective = ", show(objective), ";\n",
57 "heart = array2d(", show(N), ", ", show(N), ", [\n"
58] ++ [
59 show(heart[i, j])
60 ++ if j = n /\ i = n then "" else ", " endif
61 ++ if j = n then "\n" else "" endif
62| i in N, j in 1..n
63] ++ [
64 "]);\n"
65] ++ [
66 if j = 1 then "%% " else "" endif
67 ++ show(heart[i, j]) ++ " "
68 ++ if j == i then "\n" else "" endif
69| i in N, j in 1..i ];
70
71
72%------------------------------------------------------------------------------%