/* 

  Adjacent numbers sums to primes in Picat.

  From Chris Smith's Math Newsletter Issue 723 (2025-06-09)
  """
  I’d like you to arrange each of the
  integers 0 to 13 into these boxes so
  that any pair of adjacent numbers
  adds up to a prime number:
    [ ... ]
  If that’s too easy, see whether you can
  extend this beyond 13 (or prove why that’s
  not possible)
  """

  There is a lot of solutions for 0..13:
  * 307632 solutions without symmetry breaking
  * 146184 with symmetry breaking

  Here are some of the solutions for the 0..13 problem (with symmetry breaking)
  (the numbers and the primes):
  [7,4,13,6,11,0,3,2,5,12,1,10,9,8] = [11,17,19,17,11,3,5,7,17,13,11,19]
  [1,4,7,12,11,0,3,8,5,6,13,10,9,2] = [5,11,19,23,11,3,11,13,11,19,23,19]
  [3,4,7,6,5,0,13,10,1,12,11,2,9,8] = [7,11,13,11,5,13,23,11,13,23,13,11]
  [9,4,1,2,0,13,6,11,8,5,12,7,10,3] = [13,5,3,2,13,19,17,19,13,17,19,17]


  See below (go2/0 and go3/0) for other sizes.

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

*/

import util.
import cp.

main => go.

go ?=>
  nolog,
  N = 13,
  adj(N,X),
  println(X=[X[I]+X[I+1] : I in 1..N-1]),
  fail,
  nl.
go => true.

/*
  Solutions for sizes between 2..10.
  Note that the model has a symmetry breaking constraint X[1] < X[N]

  n = 2
  [0,2,1] = [2]
  [1,2,0] = [3]

  n = 3
  [0,3,2,1] = [3,5]
  [1,2,3,0] = [3,5]

  n = 4
  [0,2,1,4,3] = [2,3,5]
  [0,2,3,4,1] = [2,5,7]
  [0,3,2,1,4] = [3,5,3]
  [0,3,4,1,2] = [3,7,5]
  [1,2,0,3,4] = [3,2,3]
  [1,4,3,2,0] = [5,7,5]
  [2,0,3,4,1] = [2,3,7]
  [2,1,4,3,0] = [3,5,7]

  n = 5
  [0,3,4,1,2,5] = [3,7,5,3]
  [0,5,2,1,4,3] = [5,7,3,5]
  [0,5,2,3,4,1] = [5,7,5,7]
  [1,2,5,0,3,4] = [3,7,5,3]
  [1,4,3,0,2,5] = [5,7,3,2]
  [1,4,3,0,5,2] = [5,7,3,5]
  [1,4,3,2,5,0] = [5,7,5,7]
  [2,5,0,3,4,1] = [7,5,3,7]
  [3,4,1,2,5,0] = [7,5,3,7]

  n = 6
  [0,2,3,4,1,6,5] = [2,5,7,5,7]
  [0,2,5,6,1,4,3] = [2,7,11,7,5]
  [0,3,2,5,6,1,4] = [3,5,7,11,7]
  [0,3,4,1,2,5,6] = [3,7,5,3,7]
  [0,3,4,1,6,5,2] = [3,7,5,7,11]
  [0,5,2,3,4,1,6] = [5,7,5,7,5]
  [0,5,6,1,2,3,4] = [5,11,7,3,5]
  [0,5,6,1,4,3,2] = [5,11,7,5,7]
  [1,4,3,0,2,5,6] = [5,7,3,2,7]
  [1,4,3,2,0,5,6] = [5,7,5,2,5]
  [1,6,5,0,2,3,4] = [7,11,5,2,5]
  [1,6,5,2,0,3,4] = [7,11,7,2,3]
  [2,0,3,4,1,6,5] = [2,3,7,5,7]
  [2,0,5,6,1,4,3] = [2,5,11,7,5]
  [2,1,4,3,0,5,6] = [3,5,7,3,5]
  [2,1,6,5,0,3,4] = [3,7,11,5,3]
  [2,3,4,1,6,5,0] = [5,7,5,7,11]
  [2,5,6,1,4,3,0] = [7,11,7,5,7]
  [3,4,1,2,0,5,6] = [7,5,3,2,5]
  [4,1,2,3,0,5,6] = [5,3,5,3,5]
  [4,3,0,2,1,6,5] = [7,3,2,3,7]
  [4,3,0,2,5,6,1] = [7,3,2,7,11]
  [4,3,2,0,5,6,1] = [7,5,2,5,11]
  [4,3,2,1,6,5,0] = [7,5,3,7,11]

*/
go2 ?=>
  nolog,
  member(N,2..10),
  nl,
  println(n=N),
  adj(N,X),
  println(X=[X[I]+X[I+1] : I in 1..N-1]),  
  
  fail,
  nl.
go2 => true.

/*
  Number of solutions (without symmetry breaking) for N in 2..15:

  2 = 2
  3 = 4
  4 = 14
  5 = 22
  6 = 52
  7 = 196
  8 = 268
  9 = 930
  10 = 4332
  11 = 21048
  12 = 68192
  13 = 307632
  14 = 457584
  15 = 2358024

  Number of solutions (with symmetry breaking) for N in 2..15:
  2 = 2
  3 = 2
  4 = 8
  5 = 9
  6 = 24
  7 = 96
  8 = 118
  9 = 476
  10 = 2108
  11 = 10272
  12 = 32928
  13 = 146184
  14 = 195380
  15 = 1106138

*/
go3 ?=>
  nolog,
  garbage_collect(300_000_000),
  foreach(N in 2..15)
    Sols = count_all(adj(N,_X)),
    println(N=Sols)
  end,
  nl.
go3 => true.


adj(N, X) =>
  Primes = primes(2*N),
  X = new_list(N+1),
  X :: 0..N,
  all_different(X),

  X[1] #< X[N], % symmetry breaking

  foreach(I in 1..N)
    V #= X[I] + X[I+1],
    V :: Primes
  end,
  solve(X).