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) ]; |