/* 

  Number Cross Puzzle in Picat.

  "A programming challenge. Number Cross Puzzle"
  http://codegolf.stackexchange.com/questions/8571/a-programming-challenge-number-cross-puzzle
  """
  This is from a programming challenge website.

  The cross problem states that you can place the numbers 1 through N inside the cross 
  such that no two adjacent cells in any direction (up, down, left or right, or diagonal) 
  contain adjacent numbers (+ or - 1).

  Given the shape of an 8 sized cross below where the numbers represent the cell index:

    1 4
  0 2 5 7
    3 6

  there are only 4 solutions for an 8 sized cross. In the above structure, cell 2 is 
  adjacent to cells 0, 1, 3, 4, 5 and 6 while cell 1 is adjacent to cell 0, 2, 4 and 5. 
  Here is one of the 4 solutions:

    5 3
  2 8 1 7
    6 4

  How many solutions are there on a 12 sized cross given the indexes below?

    2 6
  0 3 7 10
  1 4 8 11
    5 9

  I solved it via simple brute force where I used recursion to fill the cross. It took 
  me around 5-10 mins though. I wonder whether there is an efficient algorithm for it, 
  or maybe a mathematical way. I really liked this challenge and that is why I am wondering 
  about an efficient solution.
  """

  Compare with another approach (for problem #1):
  http://hakank.org/picat/place_number_puzzle.pi


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

*/


import cp.


main => go.

%
% 12 sized instance
% There are 262288 different solutions (1.3s, 0 backtracks)
%
go => 
  problem(2,Rows,Cols,Mat), 
  Count = count_all(puzzle(Rows,Cols,Mat, _X)),
  println(count=Count),
  nl.


% Problem 2, find all solutions
go2 ?=>
  problem(2,Rows,Cols,Mat), % 12 sized
  puzzle(Rows,Cols,Mat, X),
  println(X),
  fail,
  nl.

go2 => true.



% Problem 1 (8 sized)
% 4 solutions
go3 => 
  problem(1,Rows,Cols,Mat), % 8 sized
  All = find_all(X,puzzle(Rows,Cols,Mat, X)),
  println(All),
  println(len=All.len),
  nl.



go4 =>
  foreach(P in 1..4)
    println(p=P),
    problem(P,Rows,Cols,Mat),
    puzzle(Rows,Cols,Mat, X),
    println(X),
    nl
  end,
    
  nl.


puzzle(Rows,Cols,Mat, X) =>

  N = sum([1 : I in 1..Rows, J in 1..Cols, Mat[I,J] > 0]),

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

  all_different(X),

  % constrain all the neighbours for each cell
  V = {-1,0,1},
  foreach(I in 1..Rows, J in 1..Cols, Mat[I,J] > 0) 
     foreach(A in V,B in V,
            member(I+A,1..Rows), member(J+B,1..Cols),
            not(A == 0, B == 0), Mat[I+A,J+B] > 0)
              abs(X[Mat[I,J]] - X[Mat[I+A,J+B]]) #> 1 
     end
  end,
  solve([ffd,split],X).


% Problem 1: 8 sized
problem(1,Rows,Cols,Mat) => 
  Rows = 3,
  Cols = 4,

  % 0 means empty cell
  Mat = 
[
 [0, 2,  5, 0],
 [1, 3,  6, 8],
 [0, 4,  7, 0]
].


% Problem 2: 12 sized
problem(2,Rows,Cols,Mat) => 
  Rows = 4,
  Cols = 4,

  % 0 means empty cell
  Mat = 
[
 [0, 3,  7,  0],
 [1, 4,  8, 11],
 [2, 5,  9, 12],
 [0, 6, 10,  0]
].

problem(3,Rows,Cols,Mat) =>
  Rows = 5,
  Cols = 5,

  % 0 means empty cell
  Mat =
  [
  [0, 4, 9,14, 0],
  [1, 5,10,15,19],
  [2, 6,11,16,20],
  [3, 7,12,17,21],
  [0, 8,13,18, 0]].


problem(4,Rows,Cols,Mat) =>
  Rows = 5,
  Cols = 5,

  % 0 means empty cell
  Mat =
  [
  [0, 0, 5, 0, 0],
  [0, 2, 6,10, 0],
  [1, 3, 7,11,13],
  [0, 4, 8,12, 0],
  [0, 0, 9, 0, 0]
  ].