Debian Codegraph @

tests/spec/examples/knights.mzn

raw
1 /***
2 !Test
3 solvers: [gecode, chuffed] # Too slow on cbc
4 expected:
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
18 include "globals.mzn";
19
20 % n is the length of side of the chessboard.
21 %
22 int: n = 6;
23
24 % The ith square (r, c) on the path is given by p[i] = (r - 1) * n + c.
25 %
26 int: nn = n * n;
27 set of int: sq = 1..nn;
28 array [sq] of var sq: p;
29
30 set of int: row = 1..n;
31 set of int: col = 1..n;
32
33 % Break some symmetry by specifying the first and last moves.
34 %
35 constraint p[1] = 1;
36 constraint p[2] = n + 3;
37 constraint p[nn] = 2 * n + 2;
38
39 % All points along the path must be unique.
40 %
41 constraint alldifferent(p);
42
43 array [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
54 constraint forall (i in sq where i > 1) (p[i] in neighbours[p[i - 1]]);
55
56 solve
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
68 output ["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