langford.mzn
2.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
%-----------------------------------------------------------------------------%
% Langford's Problem (CSPlib problem 24)
%
% June 2006; Sebastian Brand
%
% Instance L(k,n):
% Arrange k sets of numbers 1 to n so that each appearance of the number m is m
% numbers on from the last. For example, the L(3,9) problem is to arrange 3
% sets of the numbers 1 to 9 so that the first two 1's and the second two 1's
% appear one number apart, the first two 2's and the second two 2's appear two
% numbers apart, etc.
%-----------------------------------------------------------------------------%
% MiniZinc version
% Peter Stuckey September 30
include "globals.mzn";
%-----------------------------------------------------------------------------%
% Instance
%-----------------------------------------------------------------------------%
int: n; % numbers 1..n
int: k; % sets 1..k
%-----------------------------------------------------------------------------%
% Input
%-----------------------------------------------------------------------------%
set of int: numbers = 1..n; % numbers
set of int: sets = 1..k; % sets of numbers
set of int: num_set = 1..n*k;
set of int: positions = 1..n*k; % positions of (number, set) pairs
%-----------------------------------------------------------------------------%
% Primal model
%-----------------------------------------------------------------------------%
array[num_set] of var positions: Pos;
% Pos[ns]: position of (number, set)
% pair in the sought sequence
constraint
forall(i in 1..n, j in 1..k-1) (
Pos[k*(i-1) + j+1] - Pos[k*(i-1) + j] = i + 1
);
constraint alldifferent(Pos);
%-----------------------------------------------------------------------------%
% Dual model (partial)
%-----------------------------------------------------------------------------%
array[positions] of var num_set: Num; % Num[p]: (number, set) pair at
% position p in the sought sequence
constraint alldifferent(Num);
%-----------------------------------------------------------------------------%
% Channelling between primal model and dual model
%-----------------------------------------------------------------------------%
constraint
forall(i in numbers, j in sets, p in positions) (
(Pos[k*(i-1) + j] = p) <-> (Num[p] = k*(i-1) + j)
);
%-----------------------------------------------------------------------------%
% Without specifying a sensible search order this problem takes
% forever to solve.
%
solve :: int_search(Pos, input_order, indomain_min, complete)
satisfy;
%-----------------------------------------------------------------------------%
output [show(Pos)];
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%