Debian Codegraph @

tests/spec/examples/steiner-triples.mzn

raw
1 /***
2 !Test
3 solvers: [] # Remove once set ordering has been fixed
4 expected:
5 - !Result
6 solution: !Solution
7 sets:
8 - !Range 5..7
9 - !!set {3, 4, 7}
10 - !!set {2, 4, 6}
11 - !!set {2, 3, 5}
12 - !!set {1, 4, 5}
13 - !!set {1, 3, 6}
14 - !!set {1, 2, 7}
15 - !Result
16 solution: !Solution
17 sets:
18 - !Range 4..6
19 - !!set {3, 6, 7}
20 - !!set {2, 4, 7}
21 - !!set {2, 3, 5}
22 - !!set {1, 5, 7}
23 - !!set {1, 3, 4}
24 - !!set {1, 2, 6}
25 - !Result
26 solution: !Solution
27 sets:
28 - !!set {4, 6, 7}
29 - !!set {3, 5, 7}
30 - !!set {2, 5, 6}
31 - !Range '2..4'
32 - !!set {1, 4, 5}
33 - !!set {1, 3, 6}
34 - !!set {1, 2, 7}
35 - !Result
36 solution: !Solution
37 sets:
38 - !!set {4, 6, 7}
39 - !Range 3..5
40 - !!set {2, 5, 6}
41 - !!set {2, 3, 7}
42 - !!set {1, 5, 7}
43 - !!set {1, 3, 6}
44 - !!set {1, 2, 4}
45 ***/
46
47 %-----------------------------------------------------------------------------%
48 % Steiner Triples (CSPlib problem 44)
49 %
50 % March 2008; Mark Wallace, based on the Eclipse version by Joachim Schimpf
51 %
52 % The following program computes so-called Steiner triplets. These are
53 % triplets of numbers from 1 to n such that any two triplets have at most one
54 % element in common.
55 %
56 % One possible solution for n=7 is
57 % { {1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6},
58 % {2, 5, 7}, {3, 4, 7}, {3, 5, 6} }.
59 %-----------------------------------------------------------------------------%
60
61 n = 7;
62
63 %-----------------------------------------------------------------------------%
64
65 int: n;
66
67 int: nb = n * (n-1) div 6 ;
68
69 array[1..nb] of var set of 1..n: sets;
70
71 constraint forall(i in 1..nb) ( card(sets[i]) = 3 );
72
73 constraint
74 forall(i in 1..nb, j in i+1..nb) ( card(sets[i] intersect sets[j]) <= 1 );
75
76 % Symmetry breaking:
77 constraint forall(i in 1..nb-1) ( sets[i] >= sets[i+1] );
78
79 solve :: set_search(sets, input_order, indomain_min, complete) satisfy;
80
81 output [ " " ++ show(sets[i]) | i in 1..nb ] ++ ["\n"];
82
83 %-----------------------------------------------------------------------------%
84 %-----------------------------------------------------------------------------%