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