| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
j: 4 |
| 7 |
k: 10 |
| 8 |
objective: 4 |
| 9 |
s: [7, 5, 4, 3, 1, 0, 0, 0, 0, 0, 0] |
| 10 |
***/ |
| 11 |
|
| 12 |
% perfsq.mzn |
| 13 |
% vim: ft=zinc ts=4 sw=4 et |
| 14 |
% Ralph Becket |
| 15 |
% Thu May 31 11:44:33 EST 2007 |
| 16 |
% |
| 17 |
% Perfect squares: find a set of integers the sum of whose squares is |
| 18 |
% itself a square. |
| 19 |
|
| 20 |
int: z = 10; |
| 21 |
|
| 22 |
array [0..z] of 0..z*z: sq = array1d(0..z, [x*x | x in 0..z]); |
| 23 |
|
| 24 |
array [0..z] of var 0..z: s; % Decreasing indices into sq. |
| 25 |
|
| 26 |
var 0..z: k; % We are summing to sq[k]; |
| 27 |
|
| 28 |
var 1..z: j; % We want this many sub-squares. |
| 29 |
|
| 30 |
|
| 31 |
|
| 32 |
% Symmetry breaking: s is an array of indices into sq. The indices are |
| 33 |
% strictly decreasing until they reach zero, whereupon the remainder are |
| 34 |
% also zero. |
| 35 |
% |
| 36 |
constraint forall ( i in 1..z ) ( s[i] > 0 -> s[i - 1] > s[i] ); |
| 37 |
|
| 38 |
% sq[k], sq[k + 1], ... can't appear in the solution. |
| 39 |
% |
| 40 |
constraint s[0] < k; |
| 41 |
|
| 42 |
% We want the sum of the squares to be square. |
| 43 |
% |
| 44 |
constraint sum ( i in 0..z ) ( sq[s[i]] ) = sq[k]; |
| 45 |
|
| 46 |
% We want the longest such sequence. |
| 47 |
% |
| 48 |
constraint s[j] > 0; |
| 49 |
|
| 50 |
solve maximize j; |
| 51 |
|
| 52 |
output [ |
| 53 |
"perfsq\n", |
| 54 |
show(k), "^2 = ", |
| 55 |
show(s[0]), "^2 + ", |
| 56 |
show(s[1]), "^2 + ", |
| 57 |
show(s[2]), "^2 + ", |
| 58 |
show(s[3]), "^2 + ", |
| 59 |
show(s[4]), "^2 + ", |
| 60 |
show(s[5]), "^2 + ", |
| 61 |
show(s[6]), "^2 + ", |
| 62 |
show(s[7]), "^2 + ", |
| 63 |
show(s[8]), "^2 + ", |
| 64 |
show(s[9]), "^2 + ", |
| 65 |
show(s[10]), "^2\n", |
| 66 |
]; |