/* 

  Tile swapping puzzle in Picat.

  From the Picat Book, page 107, Exercise 4
  """
  4. Write a program to solve the tile-swapping puzzle. 1 The puzzle is a 3× 3 board
  consisting of numbers from 1 to 9. Given an initial state, the objective of the
  puzzle is to swap the tiles until the goal state is reached. The following gives an
  initial state and the goal state:
     732      123
     415      456
     689      789
  Two adjacent tiles can be swapped if their sum is a prime number. Two tiles are
  considered adjacent if they have a common edge.
  """

  Solution:
  plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[1,1] = 4,and,[2,1] = 1],[swap,[2,2] = 6,and,[2,3] = 5]]
  [7,3,2]
  [4,1,5]
  [6,8,9]

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

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

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

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

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

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

  cost = 6

  There are 768 plans with cost 6, using best_cost_nondet/4.
  Here are some of these:

    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[1,1] = 4,and,[2,1] = 1],[swap,[2,3] = 5,and,[2,2] = 6]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,1] = 1,and,[1,1] = 4],[swap,[2,2] = 6,and,[2,3] = 5]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,1] = 1,and,[1,1] = 4],[swap,[2,3] = 5,and,[2,2] = 6]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,2] = 6,and,[2,3] = 5],[swap,[1,1] = 4,and,[2,1] = 1]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,2] = 6,and,[2,3] = 5],[swap,[2,1] = 1,and,[1,1] = 4]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,3] = 5,and,[2,2] = 6],[swap,[1,1] = 4,and,[2,1] = 1]]
    plan = [[swap,[1,1] = 7,and,[2,1] = 4],[swap,[1,2] = 3,and,[1,3] = 2],[swap,[2,1] = 7,and,[3,1] = 6],[swap,[2,1] = 6,and,[2,2] = 1],[swap,[2,3] = 5,and,[2,2] = 6],[swap,[2,1] = 1,and,[1,1] = 4]]


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

*/

import util.
import planner.

main => go.

go =>
  Init = [[7,3,2],
          [4,1,5],
          [6,8,9]],
  solve_problem(Init,best_plan_bin),
  nl.

%
% Show all optimal solutions
% 
go2 =>
  Init = [[7,3,2],
          [4,1,5],
          [6,8,9]],
  solve_problem(Init,best_plan_nondet), % Showing all solutions
  fail,
  nl.

%
% Random grid of size NxN.
%
go3 =>
  N = 4,
  _ = random2(),
  Grid = (1..(N*N)).chunks_of(N),
  Init = generate_instance(Grid, 40),
  println(init=Init),
  solve_problem(Init,best_plan_bin),
  %% For showing all optimal solutions:
  % solve_problem(Init,best_plan_nondet),
  % fail,
  nl.
  

final([S|_]) => final_state(S).


solve_problem(Init) =>
  solve_problem(Init,best_plan).
  
solve_problem(Init,Planner) => 
  Rows = Init.len,
  Cols = Init[1].len,
  Final = (1..Rows*Cols).chunks_of(Rows),

  cl_facts($[final_state(Final)]),
  
  % best_plan([Init,Rows,Cols],Plan,Cost),
  call(Planner,[Init,Rows,Cols],Plan,Cost),
  
  T = copy_term(Init),
  println(plan=Plan),
  println(cost=Cost),
  nl,
  println("Init:"),
  print_matrix(T),
  foreach([swap,[I1,J1] = V1,and,[I2,J2] = V2] in Plan)
    println([swap,[I1,J1] = V1,and,[I2,J2] = V2]),
    T[I1,J1] := V2,
    T[I2,J2] := V1,
    print_matrix(T)
  end,
  println(cost=Cost),
  nl.  

%
% Get all valid swap candidates in the grid
% 
neibs(Grid,Rows,Cols) = Neibs =>
  Neibs = [],
  foreach(I in 1..Rows, J in 1..Cols)
    V = Grid[I,J],
    Ns = [[I+A,J+B] : A in -1..1, B in -1..1,
                   I+A >= 1, I+A <= Rows, J+B >= 1, J+B <= Cols, abs(A)+abs(B) == 1,
                   prime(Grid[I+A,J+B]+V) ],
    foreach([NewI,NewJ] in Ns)
      Neibs := Neibs ++ [[I,J,NewI,NewJ]]
    end
  end.

table
action([Grid,Rows,Cols],To,Move,Cost) =>
  Valid = neibs(Grid,Rows,Cols),
  member([I1,J1,I2,J2],Valid),
  Grid2 = copy_term(Grid),
  Grid2[I2,J2] := Grid[I1,J1],
  Grid2[I1,J1] := Grid[I2,J2],
  To = [Grid2,Rows,Cols],
  Move = [swap,[I1,J1]=Grid[I1,J1],and,[I2,J2]=Grid[I2,J2]],
  Cost = 1.

% heuristic. This is not correct. Yields a longer plan!
% heuristic([Grid,Rows,Cols]) = S =>
%   S = 0,
%   final_state(Final),
%   foreach(I in 1..Rows, J in 1..Cols)
%     S := S + abs(Grid[I,J]-Final[I,J])
%   end.

%
% Generate N swaps of the grid
%
generate_instance(Grid,N) = Grid2 =>
  Grid2 = copy_term(Grid),
  Rows = Grid.len,
  Cols = Grid[1].len,
  foreach(_ in 1..N)
    Grid2 := random_move(Grid2,Rows,Cols)
  end.

random_move(Grid,Rows,Cols) = Grid2 =>
  Valid = neibs(Grid,Rows,Cols),
  R = random(1,Valid.len),
  [I1,J1,I2,J2] = Valid[R], 
  Grid2 = copy_term(Grid),
  Grid2[I2,J2] := Grid[I1,J1],
  Grid2[I1,J1] := Grid[I2,J2].

print_matrix(M) =>
  Rows = M.len,
  Cols = M[1].len,
  Max = (M.flatten.max.to_string.len+2).to_string,
  Format = "%"++Max++"d",
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      printf(Format,M[I,J])
    end,
    nl
  end,
  nl.