/* 

  Four knights puzzle (planning) in Picat.

  Swap the four knights in position 1..4 
     1 _ 2
     _ _ _
     3 _ 4

  so they are placed as

     4 _ 3
     _ _ _
     2 _ 1

  See for example: 
  Mind Your Decisions: "Four Knights"
  http://mindyourdecisions.com/blog/2014/03/17/monday-puzzle-four-knights/
  """
  The goal is to get each knight into the opposite corner (that is, swap 
  the knights on a1 and c3 as well as a3 and c1).

  Can it be done using legal chess moves, and if so, what’s the minimum 
  number of moves?

  (A knight can move to an unoccupied space according to an L-shape movement: 
  it must move two spaces horizontally and one vertically, or two spaces 
  vertically and one horizontally.)
  """



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

*/


% import util.
% import cp.
import planner.

main => go.


go =>
   initial_state(Init),
   println('init '=Init),
   final(Final),
   println(final=Final),
   time(best_plan(Init,Plan)),
   writeln(Plan),
   writeln(len=Plan.length),

   % Nicer output
   State = Init,
   println(init),
   print_state(State),
   foreach([F,From,To] in Plan)
     printf("Move knight %d from pos %d to pos %d\n", F,From,To),
     State := swap(State,From,To),
     print_state(State)
   end,
   nl.


print_state(State) =>
  foreach(I in 1..State.length) 
    S = State[I],
    printf("%w ", cond(S>0, S, "_")),
    if I mod 3 == 0 then
       nl
    end
  end,
  nl.


initial_state(State) =>
   State = [
             1,0,2,
             0,0,0,
             3,0,4
           ].


final(State) =>
   State = [
             4,0,3,
             0,0,0,
             2,0,1
           ].

%
% The valid knight moves
%
%  1,2,3,
%  4,5,6,
%  7,8,9
%
% knight_move(FromPos,ToPos).
%
index(-,-)
knight_move(1,6).
knight_move(1,8).
knight_move(2,7).
knight_move(2,9).
knight_move(3,4).
knight_move(3,8).
knight_move(4,3).
knight_move(4,9).
knight_move(6,1).
knight_move(6,7).
knight_move(7,2).
knight_move(7,6).
knight_move(8,1).
knight_move(8,3).
knight_move(9,2).
knight_move(9,4).


action(From,To,Move,Cost) =>
   Cost = 1,
   knight_move(F,T),           % pick a move
   VFrom = From[F], VFrom > 0, % pick a position for one knights
   VTo = From[T],   VTo = 0,   % pick an unoccupied position
   % To=swap(From,F,T),          % swap these positions
   To = copy_term(From),
   To[F] := From[T],
   To[T] := From[F],
   Move=[VFrom,F,T].
 
swap(L,I,J) = L2, list(L) =>
  L2 = copy_term(L),
  L2[I] := L2[J],
  L2[J] := L[I].