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