Debian Codegraph @

tests/spec/unit/regression/subsets_100.mzn

raw
1 /***
2 !Test
3 solvers: [gecode, chuffed]
4 expected:
5 - !Result
6 status: SATISFIED
7 solution: !Solution
8 s: !Range 1..9
9 t: !!set {45}
10 s_total: 45
11 t_total: 45
12 - !Result
13 status: SATISFIED
14 solution: !Solution
15 s: !!set {100}
16 t: !!set {49, 51}
17 s_total: 100
18 t_total: 100
19 - !Result
20 status: SATISFIED
21 solution: !Solution
22 s: !!set {1, 2, 40, 56, 94}
23 t: !!set {3, 93, 97}
24 s_total: 193
25 t_total: 193
26 ***/
27
28 % Regression test for a bug in mzn2fzn 1.2. The optimisation pass was leaving
29 % dangling references to variables it had "eliminated". The symptom was the
30 % following error from the FlatZinc interpreter:
31 %
32 % subsets_100.fzn:413:
33 % symbol error: `INT____407' undeclared
34 %
35 % (This model is from the original bug report.)
36
37 % Subsets 100 puzzle in MiniZinc.
38 %
39 % From rec.puzzle FAQ
40 % http://brainyplanet.com/index.php/Subsets?PHPSESSID=051ae1e2b6df794a5a08fc7b5ecf8028
41 % """
42 % Out of the set of integers 1,...,100 you are given ten different integers.
43 % From this set, A, of ten integers you can always find two disjoint non-empty
44 % subsets, S & T, such that the sum of elements in S equals the sum of elements
45 % in T. Note: S union T need not be all ten elements of A. Prove this.
46 % """
47
48 %
49 % This MiniZinc model was created by Hakan Kjellerstrand, [email protected]
50 % See also my MiniZinc page: http://www.hakank.org/minizinc
51 %
52
53 % Note that this model is not run using CBC
54 % This is because the solutions listed are not exhaustive, so we would usually check against another solver
55 % However we cannot do this because when giving values for s or t then sum_set does not work
56 % As the ub for the set will simply be the set itself, summing the wrong numbers
57
58 include "globals.mzn";
59 int: n = 100;
60 int: m = 10;
61 var set of 1..n: s;
62 var set of 1..n: t;
63 var int: s_total;
64 var int: t_total;
65
66 %
67 % sums the integer in set ss
68 %
69 predicate sum_set(var set of int: ss, var int: total) =
70 let {
71 int: m = card(ub(ss)), % NOTE: This prevents checking of solutions since when fixing ss then card(ub(ss))=card(ss) so numbers are not summed correctly when checking
72 array[1..m] of var 0..1: tmp
73 }
74 in
75 forall(i in 1..m) (
76 i in ss <-> tmp[i] = 1
77 )
78 /\
79 total = sum(i in 1..m) (i*tmp[i])
80 ;
81
82
83 solve :: set_search([s,t],
84 input_order, indomain_min, complete) satisfy;
85
86 constraint
87 card(s union t) <= m
88 /\
89 card(s union t) > 0
90 /\
91 disjoint(s, t)
92 /\
93 sum_set(s, s_total)
94 /\
95 sum_set(t, t_total)
96 /\
97 s_total = t_total
98 % /\
99 % t_total = n
100 ;