| 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 |
|