/* 

  Arrow problem in Picat.

  From the Swedish blog post "Pilen" (Arrow)
  http://mattebloggen.com/2012/03/4459/
  (translated):
  "The digits 1 to nine is filling the matrix as seen in the
  left picture. You can walk on the cells on the grid but
  never go back to a visited cell. You must always go to a 
  neighboring cell.

    1 8 4            
    6 3 9
    5 7 2

  Katarina walked along the arrow shown on the right picture.
  She wrote down the digits in order and got the number 84937561. 
  Your assignment is to draw another way which give a larger number,
  the larger the better.
  """

  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 ?=>
  N = 3,
  X = new_list(N*N),
  X :: 1..N*N,
  Num :: 123456789..987654321,

  Data =  [
     [1, 8, 4],
     [6, 3, 9],
     [5, 7, 2]
    ],

  all_different(X),
  to_num(X, 10, Num),

  foreach(K in 1..N*N-1)
     I :: 1..N,
     J :: 1..N,
     A :: -1..1,
     B :: -1..1,
     
     % find this number
     % X[K] #= Data[I,J], % not allowed in Picat
     matrix_element(Data,I,J,X[K]),

     % find the possible offsets for the next number
     IA #= I+A,
     JB #= J+B,     
     IA :: 1..N,
     JB :: 1..N,
     A #= 0 #\/ B #= 0,
     % and connect to the next number
     % X[K+1] #= Data[I+A, J+B], % not allowed in Picat
     matrix_element(Data,IA,JB,X[K+1])
  end,

  Num #> 84937561, % Larger than Katarina's number

  solve($[max(Num)],X),
  println(x=X),
  println(num=Num),
  nl,
  fail,
  
  nl.

go => true.


%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
   Len = length(List),
   Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).