Download
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
%
% Steiner triplets in MiniZinc.
%
% The ternary Steiner problem of order n is to find n(n-1)/6 sets of elements in {1,2,...,n}
% such that each set contains three elements and any two sets have at most one element in common.
% For example, the following shows a solution for size n=7:
%
%      {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}
%
% Problem taken from:
%  C. Gervet: Interval Propagation to Reason about Sets: Definition and Implementation of a Practical
%  Language,  Constraints, An International Journal, vol.1, pp.191-246, 1997.
%
%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@gmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%
 
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
% include "globals.mzn";
 
 
include "globals.mzn";
 
int: N = 7;
int: NB = N *(N-1) div 6;
array[1..NB] of var set of 1..N: Sets;
 
% solve satisfy;
solve::set_search(Sets, first_fail, indomain_min, complete) satisfy;
 
 
 
constraint
   forall(i in index_set(Sets)) (
      card(Sets[i]) = 3
   )
   /\
   forall(i,j in index_set(Sets) where i < j) (
      card( Sets[i] intersect Sets[j]) <= 1
   )
   /\ % symmetry breaking
   decreasing(Sets)
 
;
 
output [
       "N: ", show(N), " NB: ", show(NB), "\n",
       "Sets: ", show(Sets)
];