/* 

  Czech Logical Labyrinth (Pickover) in Picat.

  From http://www.f1compiler.com/samples/Czech%20Logical%20Labyrinth.f1.html
  """
  Another puzzle as described in Clifford A. Pickover's book 
  "Keys to Infinity" :

  The following is a problem posted at the 2nd World Puzzle Championship in Brno, 
  Czech Republic. The logical labyrinth (below) was just one of many puzzles the
  participants had to solve.


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


  The goal is to find a path from the 1 (upper left) to the 25 (lower right)
  such that the path contains exactly 25 squares. The allowable moves are up,
  down, left and right, and the path may not repeat any numbers.
  """

  Unique solution:

  nums = [1,10,15,4,22,11,7,14,24,3,20,21,9,16,5,19,13,6,18,8,12,2,23,17,25]
  Path:
  1: [1,1]  1
  2: [2,1] 10
  3: [3,1] 15
  4: [3,2]  4
  5: [3,3] 22
  6: [4,3] 11
  7: [5,3]  7
  8: [5,4] 14
  9: [4,4] 24
 10: [4,5]  3
 11: [3,5] 20
 12: [2,5] 21
 13: [2,4]  9
 14: [1,4] 16
 15: [1,5]  5
 16: [1,6] 19
 17: [2,6] 13
 18: [2,7]  6
 19: [3,7] 18
 20: [4,7]  8
 21: [5,7] 12
 22: [6,7]  2
 23: [6,8] 23
 24: [7,8] 17
 25: [8,8] 25


  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.


go ?=>

  matrix(Matrix),
  N = Matrix.len,

  PathLen = 25, 
  Path = new_array(PathLen,2),
  Path :: 1..N,
  
  Nums = new_list(PathLen),
  Nums :: 1..max(Matrix.flatten()),

  all_distinct(Nums),

  % init
  Nums[1] #= Matrix[1,1],
  Nums[PathLen] #= Matrix[N,N],
  Path[1,1] #= 1,
  Path[1,2] #= 1,
  Path[PathLen,1] #= N,
  Path[PathLen,2] #= N,

  foreach(P in 2..PathLen)

    % pick the previous square  
    I #= Path[P-1,1], J #= Path[P-1,2],

    % get the next square
    A :: [-1,0,1], B :: [-1,0,1],

    % enforce up,down,left,right movements
    AI :: 1..N,  BJ :: 1..N,
    AI #= A+I, BJ #= B+J,
    abs(A) + abs(B) #= 1,

    Path[P,1] #= AI,
    Path[P,2] #= BJ,

    % Nums[P] #= Matrix[Path[P,1],Path[P,2]]
    matrix_element(Matrix,Path[P,1],Path[P,2],Nums[P])

  end,

  Vars = Path.vars() ++ Nums,
  solve([ff,split],Vars),

  println(nums=Nums),
  println("Path:"),
  foreach(I in 1..PathLen)
    printf("%2d: [%d,%d] %2d\n",I,Path[I,1],Path[I,2],Nums[I])
  end,
  nl,

  fail,

  nl.

go => true.

matrix(Matrix) =>
Matrix = 
[
[ 1, 2, 7,16, 5,19, 7, 8],
[10,17,23, 9,21,13, 6,23],
[15, 4,22,17,20, 4,18,22],
[19,17,11,24, 3,17, 8,19],
[12, 9, 7,14,23,18,12, 6],
[ 6, 5,23,14,10, 5, 2,23],
[ 8,20,10,11,19,18, 1,17],
[ 2,24,15,22,13, 4, 4,25]
].