/*

  Hidato puzzle in Picat.

  http://www.shockwave.com/gamelanding/hidato.jsp
  http://www.hidato.com/
 
  """
  Puzzles start semi-filled with numbered tiles.
  The first and last numbers are circled.
  Connect the numbers together to win. Consecutive
  number must touch horizontally, vertically, or
  diagonally.
  """

  This version use another approach compared to hidato.pl:
  instead of the "matrix_element" it use member/2 (or
  between/3) to simulate the exists construct found
  in MiniZinc, ESSENCE', and AMPL.

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

*/

import util.
import cp.

main => go.

go =>
   time2($solveit(6)).

go1 => 
   time2($solveit(1)).

go2 =>
   % NumProblems = 8,
   foreach(P in [1,2,3,4,5,6,8]) time2($solveit(P)) end.

go3 => 
   time2($solveit(7)).

solveit(Problem) =>
   printf("\nProblem %d\n", Problem),
   problem(Problem,X),
   hidato(X).


hidato(X) =>

   N = X.length,
   XList = array_matrix_to_list(X),
   X :: 1..N*N,

   % Valid connections, used by the table constraint below
   Connections = [{I1,J1,I2,J2} :
                  I1 in 1..N, J1 in 1..N, 
                  I2 in 1..N, J2 in 1..N,
                  abs(I1-I2) =< 1,
                  abs(J1-J2) =< 1,
                  (I1 !=I2; J1 != J2)],

   % place all integers from 1..r*c
   all_distinct(XList),

   NN1 = (N*N)-1,

   Connect = [],
   foreach(K in 1..NN1)

       % Note: This set of member/2 simulates the exists 
       % in MiniZinc, Essence' etc.

       % define temporary variables for finding
       % the index of this and the next number (K)
       /*
       member(I,1..N),
       member(J,1..N),
       member(A,-1..1),
       member(B,-1..1),
       */
       between(1,N,I),
       between(1,N,J),
       between(-1,1,A),
       between(-1,1,B),

       abs(A)+abs(B) >= 1, % both A and B cannot be 0, i.e. it must be a move
       I + A >= 1,
       I + A =< N,
       J + B >= 1,
       J + B =< N,

       % 1. First: fix this k, i.e.
       X[I,J] #= K,

       % 2. Then, find the position of the next value, i.e.
       K+1 #= X[I+A,J+B]
       , Connect := Connect ++ [{I,J,I+A,J+B}]

   end,

   % table constraint
   table_in(Connect,Connections),

   % search
   Vars = XList ++ Connect,
   % solve([inout,down],Vars),
   solve([ffc,split],Vars), % faster


   pretty_print(X).


pretty_print(X) =>
   N = X.length,
   foreach(I in 1..N)
      foreach(J in 1..N)
          printf("%3d ", X[I,J])
      end,
      nl
   end, 
   nl.   



%
% Problems
%


% Simple problem
%
% solution:
%   6 7 9
%   5 2 8
%   1 4 3
% 
problem(1, P) => 
    P = {{6,_,9},
         {_,2,8},
         {1,_,_}}.



problem(2, P) => 
    P = {{ _,44,41, _, _, _, _},
         { _,43, _,28,29, _, _},
         { _, 1, _, _, _,33, _},
         { _, 2,25, 4,34, _,36},
         {49,16, _,23, _, _, _},
         { _,19, _, _,12, 7, _},
         { _, _, _,14, _, _, _}}. 



% Problems from the book:
% Gyora Bededek: "Hidato: 2000 Pure Logic Puzzles"

% problem 1 (Practice}
problem(3, P) => 
    P = {{_, _,20, _, _},
         {_, _, _,16,18},
         {22, _,15, _, _},
         {23, _, 1,14,11},
         {_,25, _, _,12}}.
         


% problem 2 (Practice}
problem(4, P) => 
    P = {{_, _, _, _,14},
         {_,18,12, _, _},
         {_, _,17, 4, 5},
         {_, _, 7, _, _},
         {9, 8,25, 1, _}}.


% problem 3 (Beginner}
problem(5, P) => 
    P = {{ _,26, _, _, _,18},
         { _, _,27, _, _,19},
         {31,23, _, _,14, _},
         { _,33, 8, _,15, 1},
         { _, _, _, 5, _, _},
         {35,36, _,10, _, _}}.



% Problem 15 (Intermediate}
problem(6,P) => 
   P = {{64, _, _, _, _, _, _, _},
        { 1,63, _,59,15,57,53, _},
        { _, 4, _,14, _, _, _, _},
        { 3, _,11, _,20,19, _,50},
        { _, _, _, _,22, _,48,40},
        { 9, _, _,32,23, _, _,41},
        {27, _, _, _,36, _,46, _},
        {28,30, _,35, _, _, _, _}}.


% Problem 156 (Master}
% (This is harder to solve than the 12x12 prolem 188 below...%}
problem(7, P) => 
    P = {{88, _, _,100, _, _,37,_, _,34},
         { _,86, _,96,41, _, _,36, _, _},
         { _,93,95,83, _, _, _,31,47, _},
         { _,91, _, _, _, _, _,29, _, _},
         {11, _, _, _, _, _, _,45,51, _},
         { _, 9, 5, 3, 1, _, _, _, _, _},
         { _,13, 4, _, _, _, _, _, _, _},
         {15, _, _,25, _, _,54,67, _, _},
         { _,17, _,23, _,60,59, _,69, _},
         {19, _,21,62,63, _, _, _, _, _}}.


% Problem 188 (Genius}
problem(8, P) => 
    P = {{  _,  _,134,  2,  4,  _,  _,  _,  _,  _,  _,  _},
         {136,  _,  _,  1,  _,  5,  6, 10,115,106,  _,  _},
         {139,  _,  _,124,  _,122,117,  _,  _,107,  _,  _},
         {  _,131,126,  _,123,  _,  _, 12,  _,  _,  _,103},
         {  _,  _,144,  _,  _,  _,  _,  _, 14,  _, 99,101},
         {  _,  _,129,  _, 23, 21,  _, 16, 65, 97, 96,  _},
         { 30, 29, 25,  _,  _, 19,  _,  _,  _, 66, 94,  _},
         { 32,  _,  _, 27, 57, 59, 60,  _,  _,  _,  _, 92},
         {  _, 40, 42,  _, 56, 58,  _,  _, 72,  _,  _,  _},
         {  _, 39,  _,  _,  _,  _, 78, 73, 71, 85, 69,  _},
         { 35,  _,  _, 46, 53,  _,  _,  _, 80, 84,  _,  _},
         { 36,  _, 45,  _,  _, 52, 51,  _,  _,  _,  _, 88}}.



% Variable selection
selection(Selection) => 
  Selection = [backward,constr,degree,ff,ffc,forward,inout,leftmost,max,min].

% Value selection
choice(Choice) => Choice = [down,updown,split,reverse_split].