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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | /* Magic sequence in Comet. From CSPLib problem 19: http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob019/spec.html """ A magic sequence of length n is a sequence of integers x0 . . xn-1 between 0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since 0 occurs 6 times in it, 1 occurs twice, ... """ This model is not very unlike the OPL models magic1.mod, magic2.mod, and magic3.mod in Pascal Van Hentenryck "The OPL Optimization Programming Language", page 39ff. The problem n = 50 is solved in about 1 second, n = 500 is solved in about 18 seconds. This Comet model was created by Hakan Kjellerstrand (hakank@gmail.com) Also, see my Comet page: http://www.hakank.org/comet */ // Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ import cotfd; int t0 = System.getCPUTime(); int n = 50; range Range = 0..n-1; range Domain = 0..n; int value[i in Range] = i; Solver<CP> m(); var<CP>{int} s[Range](m, Domain); Integer num_solutions(0); // // distribute // // Imitates the OPL constraint distribute. // class distribute extends UserConstraint<CP> { var<CP>{int}[] _occurrence; int[] _value; var<CP>{int}[] _element; int _n; distribute(var<CP>{int}[] occurrence, int[] value, var<CP>{int}[] element) : UserConstraint<CP>() { _occurrence = occurrence; _value = value; _element = element; _n = _occurrence.getSize(); } Outcome<CP> post(Consistency<CP> cl) { Solver<CP> cp = _occurrence[1].getSolver(); range Range = _occurrence.getRange(); forall(i in Range) cp.post(sum(j in Range) (_occurrence[j] == _value[i]) == _element[i]); return Suspend; } Outcome<CP> propagate() { return Suspend; } } explore<m> { /* // original constraint forall(i in Range) m.post(s[i] == sum(j in Range) (s[j] == i)); */ // added in the OPL model magic2.mod m.post( sum (i in Range ) s[i] == n); m.post( sum (i in Range ) s[i]*i == n); // added in the OPL model magic3.mod m.post(distribute(s, value, s)); } using { labelFF(m); num_solutions++; cout << s << endl; } cout << "\nnum_solutions: " << num_solutions << endl; int t1 = System.getCPUTime(); cout << "time: " << (t1-t0) << endl; cout << "#choices = " << m.getNChoice() << endl; cout << "#fail = " << m.getNFail() << endl; cout << "#propag = " << m.getNPropag() << endl; |