| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
Num: [1, 25, 2, 16, 3, 22, 4, 13, 19, 5, 17, 26, 6, 14, 23, 10, 20, 18, 7, 15, 11, 27, 8, 24, 21, 12, 9] |
| 7 |
Pos: [1, 3, 5, 7, 10, 13, 19, 23, 27, 16, 21, 26, 8, 14, 20, 4, 11, 18, 9, 17, 25, 6, 15, 24, 2, 12, 22] |
| 8 |
- !Result |
| 9 |
solution: !Solution |
| 10 |
Num: [19, 13, 7, 22, 16, 25, 8, 14, 20, 10, 9, 17, 23, 15, 11, 26, 21, 4, 18, 12, 5, 24, 1, 6, 2, 27, 3] |
| 11 |
Pos: [23, 25, 27, 18, 21, 24, 3, 7, 11, 10, 15, 20, 2, 8, 14, 5, 12, 19, 1, 9, 17, 4, 13, 22, 6, 16, 26] |
| 12 |
- !Result |
| 13 |
solution: !Solution |
| 14 |
Num: [1, 25, 2, 4, 3, 22, 5, 10, 16, 6, 19, 26, 11, 13, 23, 17, 7, 12, 20, 14, 8, 27, 18, 24, 9, 15, 21] |
| 15 |
Pos: [1, 3, 5, 4, 7, 10, 17, 21, 25, 8, 13, 18, 14, 20, 26, 9, 16, 23, 11, 19, 27, 6, 15, 24, 2, 12, 22] |
| 16 |
- !Result |
| 17 |
solution: !Solution |
| 18 |
Num: [1, 22, 2, 25, 3, 13, 4, 16, 19, 5, 23, 14, 6, 26, 17, 10, 20, 15, 7, 24, 11, 18, 8, 27, 21, 12, 9] |
| 19 |
Pos: [1, 3, 5, 7, 10, 13, 19, 23, 27, 16, 21, 26, 6, 12, 18, 8, 15, 22, 9, 17, 25, 2, 11, 20, 4, 14, 24] |
| 20 |
- !Result |
| 21 |
solution: !Solution |
| 22 |
Num: [7, 10, 19, 22, 8, 25, 11, 13, 9, 16, 20, 12, 23, 14, 4, 26, 17, 5, 21, 15, 6, 24, 1, 18, 2, 27, 3] |
| 23 |
Pos: [23, 25, 27, 15, 18, 21, 1, 5, 9, 2, 7, 12, 8, 14, 20, 10, 17, 24, 3, 11, 19, 4, 13, 22, 6, 16, 26] |
| 24 |
- !Result |
| 25 |
solution: !Solution |
| 26 |
Num: [7, 10, 19, 25, 8, 16, 11, 22, 9, 13, 20, 12, 17, 26, 4, 14, 23, 5, 21, 18, 6, 15, 1, 27, 2, 24, 3] |
| 27 |
Pos: [23, 25, 27, 15, 18, 21, 1, 5, 9, 2, 7, 12, 10, 16, 22, 6, 13, 20, 3, 11, 19, 8, 17, 26, 4, 14, 24] |
| 28 |
***/ |
| 29 |
|
| 30 |
%-----------------------------------------------------------------------------% |
| 31 |
% Langford's Problem (CSPlib problem 24) |
| 32 |
% |
| 33 |
% June 2006; Sebastian Brand |
| 34 |
% |
| 35 |
% Instance L(k,n): |
| 36 |
% Arrange k sets of numbers 1 to n so that each appearance of the number m is m |
| 37 |
% numbers on from the last. For example, the L(3,9) problem is to arrange 3 |
| 38 |
% sets of the numbers 1 to 9 so that the first two 1's and the second two 1's |
| 39 |
% appear one number apart, the first two 2's and the second two 2's appear two |
| 40 |
% numbers apart, etc. |
| 41 |
%-----------------------------------------------------------------------------% |
| 42 |
% MiniZinc version |
| 43 |
% Peter Stuckey September 30 |
| 44 |
|
| 45 |
include "globals.mzn"; |
| 46 |
|
| 47 |
%-----------------------------------------------------------------------------% |
| 48 |
% Instance |
| 49 |
%-----------------------------------------------------------------------------% |
| 50 |
|
| 51 |
% int: n = 10; % numbers 1..n |
| 52 |
% int: k = 2; % sets 1..k |
| 53 |
int: n = 9; |
| 54 |
int: k = 3; |
| 55 |
|
| 56 |
%-----------------------------------------------------------------------------% |
| 57 |
% Input |
| 58 |
%-----------------------------------------------------------------------------% |
| 59 |
|
| 60 |
set of int: numbers = 1..n; % numbers |
| 61 |
set of int: sets = 1..k; % sets of numbers |
| 62 |
set of int: num_set = 1..n*k; |
| 63 |
|
| 64 |
set of int: positions = 1..n*k; % positions of (number, set) pairs |
| 65 |
|
| 66 |
%-----------------------------------------------------------------------------% |
| 67 |
% Primal model |
| 68 |
%-----------------------------------------------------------------------------% |
| 69 |
|
| 70 |
array[num_set] of var positions: Pos; |
| 71 |
% Pos[ns]: position of (number, set) |
| 72 |
% pair in the sought sequence |
| 73 |
constraint |
| 74 |
forall(i in 1..n, j in 1..k-1) ( |
| 75 |
Pos[k*(i-1) + j+1] - Pos[k*(i-1) + j] = i+1 |
| 76 |
); |
| 77 |
|
| 78 |
constraint |
| 79 |
alldifferent(Pos); |
| 80 |
|
| 81 |
%-----------------------------------------------------------------------------% |
| 82 |
% Dual model (partial) |
| 83 |
%-----------------------------------------------------------------------------% |
| 84 |
|
| 85 |
array[positions] of var num_set: Num; % Num[p]: (number, set) pair at |
| 86 |
% position p in the sought sequence |
| 87 |
constraint |
| 88 |
alldifferent(Num); |
| 89 |
|
| 90 |
%-----------------------------------------------------------------------------% |
| 91 |
% Channelling between primal model and dual model |
| 92 |
%-----------------------------------------------------------------------------% |
| 93 |
|
| 94 |
constraint |
| 95 |
forall(i in numbers, j in sets, p in positions) ( |
| 96 |
(Pos[k*(i-1) + j] = p) <-> (Num[p] = k*(i-1) + j) |
| 97 |
); |
| 98 |
|
| 99 |
%-----------------------------------------------------------------------------% |
| 100 |
|
| 101 |
% Without specifying a sensible search order this problem takes |
| 102 |
% forever to solve. |
| 103 |
% |
| 104 |
solve :: int_search(Pos, first_fail, indomain_split, complete) |
| 105 |
satisfy; |
| 106 |
|
| 107 |
output |
| 108 |
[ if j = 1 then "\n" ++ show(i) ++ "s at " else ", " endif ++ |
| 109 |
show(Pos[k*(i-1) + j]) |
| 110 |
| i in 1..n, j in 1..k |
| 111 |
] ++ |
| 112 |
[ "\n" ]; |