% 
% Cube sum problem in MiniZinc.
% 
% From Krzysztof R. Apt & Mark G. Wallace 
% "Constraint Logic Programming using ECLiPSe", page 253
% """
% Problem: Given m check whether it can be written as a sum of at least two
% different cubes. If yes, produce the smallest solution in the number of
% cubes.
% """
%

% 
% Note: The ECLiPSe solution for m = 1000000 give the following result:
%  [16, 68, 88]
% i.e. an array with just 3 elements.
%
% MiniZinc has static arrays so the solution for m = 1000000 is
% [0, 0, 0, 0, 0, 0, 0, 16, 68, 88]
%

% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

include "globals.mzn"; 

int: m = 1000000;
% int: m = 1000; % no solution
int: n = 10; % the maximum number of cubes
array[1..n] of var int: x; % the cubes
var 0..n: z = sum(i in 1..n) (bool2int(x[i] > 0)); % number of cubes > 0

%
% all elements must be either different or 0.
%
predicate all_different_except_0(array[int] of var int: x) =
   let {
      int: n = length(x)
   }
   in
   forall(i,j in 1..n where i != j) (
        (x[i] > 0 /\ x[j] > 0) -> x[i] != x[j]
      
   )
;


% solve satisfy;
% solve minimize z;
solve :: int_search(x ++ [z], first_fail, indomain, complete) minimize z;

constraint
  all_different_except_0(x)
  /\
  increasing(x) % symmetry breaking
  /\ % sanity
  forall(i in 1..n) (
    x[i] >= 0 /\ x[i] <= m
  )
  /\
  m = sum(i in 1..n) (
    x[i]*x[i]*x[i] 
  )
  /\
  z >= 2 % at least two numbers
;


output [
  "x: ", show(x), "\n",
  "z: ", show(z), "\n",

];