/*
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 1..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],
solve([inout,updown], X),
writeln(x=X),
writeln(tmp=Tmp),
nl.