this repo has no description
dekker.one
1/***
2!Test
3solvers: [gecode, chuffed] # Too slow on cbc
4expected:
5- !Result
6 solution: !Solution
7 p: [1, 9, 5, 16, 3, 7, 15, 2, 10, 6, 17, 30, 34, 26, 13, 21, 32, 19, 8, 4, 12, 23, 36, 28, 20, 31, 27, 35, 24, 11, 22, 18, 29, 33, 25, 14]
8***/
9
10% knights.mzn
11% Ralph Becket
12% vim: ft=zinc ts=4 sw=4 et
13% Tue Aug 26 14:24:28 EST 2008
14%
15% Find a closed knight's tour of a chessboard (every square is visited exactly
16% once, the tour forms a loop).
17
18include "globals.mzn";
19
20 % n is the length of side of the chessboard.
21 %
22int: n = 6;
23
24 % The ith square (r, c) on the path is given by p[i] = (r - 1) * n + c.
25 %
26int: nn = n * n;
27set of int: sq = 1..nn;
28array [sq] of var sq: p;
29
30set of int: row = 1..n;
31set of int: col = 1..n;
32
33 % Break some symmetry by specifying the first and last moves.
34 %
35constraint p[1] = 1;
36constraint p[2] = n + 3;
37constraint p[nn] = 2 * n + 2;
38
39 % All points along the path must be unique.
40 %
41constraint alldifferent(p);
42
43array [sq] of set of sq: neighbours =
44 [ { n * (R - 1) + C
45 |
46 i in 1..8,
47 R in {R0 + [-1, -2, -2, -1, 1, 2, 2, 1][i]},
48 C in {C0 + [-2, -1, 1, 2, 2, 1, -1, -2][i]}
49 where R in row /\ C in col
50 }
51 | R0 in row, C0 in col
52 ];
53
54constraint forall (i in sq where i > 1) (p[i] in neighbours[p[i - 1]]);
55
56solve
57 :: int_search(
58 p,
59 input_order,
60 indomain_min,
61 complete
62 )
63 satisfy;
64% It has been observed that Warnsdorf's heuristic of choosing the next
65% square as the one with the fewest remaining neighbours leads almost
66% directly to a solution. How might we express this in MiniZinc?
67
68output ["p = " ++ show(p) ++ ";\n"];
69
70% Invert the path to show the tour.
71%
72% array [sq] of var sq: q;
73%
74% constraint forall (i in sq) (q[p[i]] = i);
75%
76% output [ show(q[i]) ++ if i mod n = 0 then "\n" else " " endif
77% | i in sq
78% ] ++
79% [ "\n"
80% ];
81