/*

  Perfect square sequence in Picat.

  From "Fun with num3ers"
  "Sequence"
  http://benvitale-funwithnum3ers.blogspot.com/2010/11/sequence.html
  """
  If we take the numbers from 1 to 15 
      (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) 
  and rearrange them in such an order that any two consecutive 
  numbers in the sequence add up to a perfect square, we get,
  
  8     1     15     10     6     3     13     12      4      5     11     14        2      7      9
      9    16    25     16     9     16     25     16     9     16     25     16       9     16
1  
  
  I ask the readers the following:
  
  Can you take the numbers from 1 to 25 to produce such an arrangement?
  How about the numbers from 1 to 100?
  """
  
  Via http://wildaboutmath.com/2010/11/26/wild-about-math-bloggers-111910


  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.

main => time(go).


go =>
   foreach(N in 2..50)
       writeln(n=N),
       time2(perfect_square_sequence(N))
   end,
   nl.

perfect_square_sequence(N) =>    

   Squares = [(I*I) : I in 1..ceiling(sqrt(N*N))],

   % decision variables
   X = new_list(N),
   X :: 1..N,

   Tmp = new_list(N-1),
   Tmp :: Squares,

   % constraints
   all_different(X),
   
   foreach(I in 2..N) 
     Tmp[I-1] #= (X[I-1]+X[I])
     % Tmp #= (X[I-1]+X[I]),
     % Tmp :: Squares
   end,

   % symmetry breaking
   X[1] #< X[N],
   
   Vars = X ++ Tmp,
   solve([constr,updown], Vars),

   writeln(x=X),
   writeln(tmp=Tmp),
   nl.