/* 

  Sticks to form a square in Picat.

  From Chris Smith Newsletter #725 (2025-06-23)
  """
  Using sticks               7
  of lengths              1     3
  1,2,3,4,5,6,7           6     4
  we can form               5 2
  a square like
  this:
  Your job is to show how to
  do this with sticks of lengths
  1-8 and then 1-n (where n is
  the next smallest stick
  which allows a square to be
  formed).
  """

  Here are the solutions for 7 and 8 (with symmetry breaking, X[1]<=1,X[2]<=2).

  n = 7
  7 = [1,2,4,4,2,1,3]
  top = [1,6]
  left = [2,5]
  right = [7]
  bottom = [3,4]

  7 = [1,2,3,3,2,1,4]
  top = [1,6]
  left = [2,5]
  right = [3,4]
  bottom = [7]


  n = 8
  8 = [1,2,3,4,4,3,2,1]
  top = [1,8]
  left = [2,7]
  right = [3,6]
  bottom = [4,5]

  8 = [1,2,4,3,3,4,2,1]
  top = [1,8]
  left = [2,7]
  right = [4,5]
  bottom = [3,6]


  And the next is valid is for 15 (see go3/0):

  n = 9
  n = 10
  n = 11
  n = 12
  n = 13
  n = 14
  n = 15
  [1,2,1,4,4,4,4,4,3,3,3,1,2,1,2]
  top = [1,3,12,14]
  left = [2,13,15]
  right = [9,10,11]
  bottom = [4,5,6,7,8]


  With symmetry breaking, X[1]<=1,X[2]<=2,X[3]<=3):

  n = 7
  7 = [1,2,3,3,2,1,4]
  top = [1,6]
  left = [2,5]
  right = [3,4]
  bottom = [7]


  n = 8
  8 = [1,2,3,4,4,3,2,1]
  top = [1,8]
  left = [2,7]
  right = [3,6]
  bottom = [4,5]

  and then (go3)

  n = 10
  n = 11
  n = 12
  n = 13
  n = 14
  n = 15
  [1,2,1,1,4,4,3,1,4,4,3,3,2,1,2]
  top = [1,3,4,8,14]
  left = [2,13,15]
  right = [7,11,12]
  bottom = [5,6,9,10]



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

*/

import cp.
% import sat.

main => go.

go ?=>
  nolog,
  member(N,7..8),
  nl,
  println(n=N),
  stick_square(N, X),
  println(N=X),
  println(top=[I : I in 1..N, X[I] == 1]),
  println(left=[I : I in 1..N, X[I] == 2]),
  println(right=[I : I in 1..N, X[I] == 3]),
  println(bottom=[I : I in 1..N, X[I] == 4]),
  nl,
  fail,

  nl.
go => true.

/*
  Number of solutions:

  2 = 0
  3 = 0
  4 = 0
  5 = 0
  6 = 0
  7 = 24
  8 = 24
  9 = 0
  10 = 0
  11 = 0
  12 = 0
  13 = 0
  14 = 0
  15 = 20904
  16 = 63600
  17 = 0
  18 = 0
  19 = 0
  20 = 0
  21 = 0
  22 = 0


  With symmetry breaking X[1] #= 1, X[2] #<= 2
  2 = 0
  3 = 0
  4 = 0
  5 = 0
  6 = 0
  7 = 2
  8 = 2
  9 = 0
  10 = 0
  11 = 0
  12 = 0
  13 = 0
  14 = 0
  15 = 2566
  16 = 8024
  17 = 0
  18 = 0
  19 = 0
  20 = 0
  21 = 0
  22 = 0
  23 = 28425268
  24 = ?

  With symmetry breaking X[1] #= 1, X[2] #<=2, X[3] #<= 3
  2 = 0
  3 = 0
  4 = 0
  5 = 0
  6 = 0
  7 = 1
  8 = 1
  9 = 0
  10 = 0
  11 = 0
  12 = 0
  13 = 0
  14 = 0
  15 = 1866
  16 = 5966
  17 = 0
  18 = 0
  19 = 0
  20 = 0
  21 = 0
  22 = 0
  23 = 21287319
  24 = 71114820
  25 = 0
  26 = 0
  27 = 0
  28 = 0
  29 = 0
  30 = 0
  CPU time 5103.58 seconds. Backtracks: 727078674

*/
go2 ?=>
  nolog,
  foreach(N in 2..30)
    if sum(1..N) mod 4 == 0 then
      Count = count_all(stick_square(N, _X)),
      println(N=Count)
    else
      println(N=0)
    end
  end,
  nl.
go2 => true.

/*
  The next is 15

  n = 9
  n = 10
  n = 11
  n = 12
  n = 13
  n = 14
  n = 15
  [4,3,3,2,1,4,2,2,4,3,2,1,1,4,3]
  top = [5,12,13]
  left = [4,7,8,11]
  right = [2,3,10,15]
  bottom = [1,6,9,14]

*/
go3 ?=>
  nolog,
  member(N, 9..1000),
  println(n=N),
  stick_square(N, X),
  println(X),
  println(top=[I : I in 1..N, X[I] == 1]),
  println(left=[I : I in 1..N, X[I] == 2]),
  println(right=[I : I in 1..N, X[I] == 3]),
  println(bottom=[I : I in 1..N, X[I] == 4]),
  nl,
  nl.
go3 => true.

/*
  sum(1..N) mod 4 == 0 is a necessary (and sufficient?) condition for a solution.

  2 = 3 = 3
  3 = 6 = 2
  4 = 10 = 2
  5 = 15 = 3
  6 = 21 = 1
  7 = 28 = 0
  8 = 36 = 0
  9 = 45 = 1
  10 = 55 = 3
  11 = 66 = 2
  12 = 78 = 2
  13 = 91 = 3
  14 = 105 = 1
  15 = 120 = 0
  16 = 136 = 0
  17 = 153 = 1
  18 = 171 = 3
  19 = 190 = 2
  20 = 210 = 2
  21 = 231 = 3
  22 = 253 = 1
  23 = 276 = 0
  24 = 300 = 0
  25 = 325 = 1
  26 = 351 = 3
  27 = 378 = 2
  28 = 406 = 2
  29 = 435 = 3
  30 = 465 = 1
  [7,8,15,16,23,24]

*/
go4 =>
  Ns = [],
  foreach(N in 2..30)
    S= sum(1..N),
    println(N=S=(S mod 4)=(S div 4)),
    if S mod 4 == 0 then
      Ns := Ns ++ [N]
    end
  end,
  println(Ns),
  nl.
go4 => true.


stick_square(N, X) =>
  X = new_list(N),
  X :: 1..4, % which side does this number belong to

  % Each side must have the same sum
  SideSum = sum(1..N) div 4,

  foreach(S in 1..4)
    sum([I*(X[I]#=S) : I in 1..N ]) #= SideSum
  end,
  
  % Symmetry breaking:
  X[1] #= 1,
  X[2] #<= 2,
  X[3] #<= 3,  

  solve($[degree,updown],X).