/* 

  Nine squares puzzle in Picat.

  From Adrian Groza "Modelling Puzzles in First Order Logic"
  """
  Puzzle 87. Nine squares

  Is it possible to have the numbers 1 to 9 positioned in a 9 square grid in a formation so
  that the numbers are placed so no adjacent number is next to it horizontally, vertically
  or diagonally?
  """

  There is no such solution.

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

*/

import cp.

main => go.

go =>
  N = 3,

  p(N,X),
  foreach(Row in X)
    println(Row.to_list)
  end,
  nl,
  fail,
  nl.

/*
  However, there are many solutions for 
  N >= 4. Here are some of them:

n = 4
 1  3  5  2 
 6  8 10  7 
 4 13 16 12 
15 11  9 14 

n = 5
 1  3  5  2  4 
 6  8 10  7  9 
11 13 15 12 14 
16 18 20 17 19 
21 23 25 22 24 

n = 6
 1  3  5  2  4  6 
 7  9 11  8 10 12 
13 15 17 14 16 18 
19 21 23 20 22 24 
25 27 29 26 28 30 
31 33 35 32 34 36 

n = 7
 1  3  5  2  4  6  8 
 7  9 11 13 10 12 14 
15 17 19 16 18 20 22 
21 23 25 27 24 26 28 
29 31 33 30 32 34 36 
35 37 39 41 38 40 42 
43 45 47 44 48 46 49 


*/
go2 =>
  member(N,2..30),
  println(n=N),
  if once(p(N,X)) then
    foreach(I in 1..N)
      foreach(J in 1..N)
        printf("%2d ",X[I,J])
      end,
      nl
    end,
    nl
  else
    println("No solution!")
  end,
  fail.

/*
  Counting solutions
*/
go3 =>
  member(N,2..10),
  C = count_all(p(N,_X)),
  println(N=C),
  fail,
  nl.


p(N,X) =>
  X = new_array(N,N),
  X :: 1..N*N,

  all_different(X.vars),

  foreach(I in 1..N, J in 1..N)
    Ns = [X[I+A,J+B] : A in -1..1, B in -1..1, not(A == 0, B == 0),
                       I + A >= 1, I + A <= N, J+B >= 1, J+B <=N],
    foreach(T in Ns)
      abs(X[I,J]-T) #> 1
    end
  end,

  solve(X.vars).