domains
  file     = in
  value    = integer
  mast     = char
  color    = red; black
  card     = card (value, mast)
  cards    = card*
  position = cards*
  liststr  = string*
  freePole = freePole (card, card, card, card)
  endPole  = endPole (cards, cards, cards, cards)
  allPole  = allPole (position, freePole, endPole)
  pole     = freePole (integer); card (integer); endPole (integer)
  listPole = allPole*
  step     = step (pole, pole)
  steps    = step*

predicates
  begin        (string, steps)
  find         (allPole, listPole, steps)
  member       (allPole, listPole)
  color        (mast, color)
  test         (allPole)
  testPos      (position)
  testFree     (freePole)
  stepDelCard  (allPole, allPole, pole, card)
  stepAddCard  (allPole, allPole, pole, card)
  stepDelPole  (position, position, integer, card)
  stepAddPole  (position, position, integer, card)
  stepDelFree  (freePole, freePole, integer, card)
  stepAddFree  (freePole, freePole, integer, card)
  stepAddEnd   (EndPole , EndPole , integer, card)
  testCard     (card, card)
  ReadStartPos (string, position)
  ReadString   (position, position)
  PrintSteps   (steps)
  PrintCard    (pole)
  split        (string, liststr)
  split1       (string, liststr)
  prepare      (liststr, position, position)
  mast         (char, mast)
  value        (string, value)

clauses
  begin (Name) :-
    ReadStartPos (Name, Pos),
    find (allPole (Pos, freePole (_, _, _, _), endPole ([], [], [], [])), [], Steps),
    PrintSteps (Steps).

  find (Pole, _, []) :-
    test (Pole), !.
  find (Pole, List, _) :-
    member (Pole, List), !,
    fail.
  find (In, List, [step (Del, Add) | Rest]) :-
    stepDelCard (In, New, Del, Card),
    stepAddCard (New, Out, Add, Card),
    find (Out, [In | List], Rest).

  member (X, [X | _]) :- !.
  member (X, [_ | Rest]) :-
    member (X, Rest).

  color ('ў', black).
  color ('з', red).
  color ('Ў', red).
  color ('Є', black).

  test (allPole (Pos, FreePos, _)) :-
    testPos (Pos),
    testFree (FreePos).
    
  testpos ([]).
  testpos ([[] | T]) :-
    testpos (T).
    
  testFree (freePole (C1, C2, C3, C4)) :-
    free (C1) and
    free (C2) and
    free (C3) and
    free (C4).

  stepDelCard (allPole (PoleIn, FreeCard, EndCard), allPole (PoleOut, FreeCard, EndCard), card (N), Card) :-
    stepDelPole (PoleIn, PoleOut, N, Card).
  stepDelCard (allPole (Pole, FreeCardIn, EndCard), allPole (Pole, FreeCardOut, EndCard), freePole (N), Card) :-
    stepDelFree (FreeCardIn, FreeCardOut, N, Card).

  stepAddCard (allPole (PoleIn, FreeCard, EndCard), allPole (PoleOut, FreeCard, EndCard), card (N), Card) :-
    stepAddPole (PoleIn, PoleOut, N, Card).
  stepAddCard (allPole (Pole, FreeCardIn, EndCard), allPole (Pole, FreeCardOut, EndCard), freePole (N), Card) :-
    stepAddFree (FreeCardIn, FreeCardOut, N, Card).
  stepAddCard (allPole (Pole, FreeCard, EndCardIn), allPole (Pole, FreeCard, EndCardOut), endPole (N), Card) :-
    stepAddEnd (EndCardIn, EndCardOut, N, Card).

  stepDelPole ([[Card | List] | Rest], [List | Rest], 1, Card).
  stepDelPole ([List | Rest], [List | RestOut], N, Card) :-
    stepDelPole (Rest, RestOut, K, Card),
    N = K + 1.

  stepDelFree (freePole (Card1, Card2, Card3, Card4), freePole (_, Card2, Card3, Card4), 1, Card1).
  stepDelFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, _, Card3, Card4), 2, Card2).
  stepDelFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, Card2, _, Card4), 3, Card3).
  stepDelFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, Card2, Card3, _), 4, Card4).

  stepAddFree (freePole (Card1, Card2, Card3, Card4), freePole (Card, Card2, Card3, Card4), 1, Card) :-
    free (Card1).
  stepAddFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, Card, Card3, Card4), 2, Card) :-
    free (Card2).
  stepAddFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, Card2, Card, Card4), 3, Card) :-
    free (Card3).
  stepAddFree (freePole (Card1, Card2, Card3, Card4), freePole (Card1, Card2, Card3, Card), 4, Card) :-
    free (Card4).

  stepAddEnd (endPole ([card (V1, Mast) | Rest], Card2, Card3, Card4),
              endPole ([card (V2, Mast), card (V1, Mast) | Rest], Card2, Card3, Card4), 1, card (V2, Mast)) :-
    V2 = V1 + 1.
  stepAddEnd (endPole (Card1, [card (V1, Mast) | Rest], Card3, Card4),
              endPole (Card1, [card (V2, Mast), card (V1, Mast) | Rest], Card3, Card4), 2, card (V2, Mast)) :-
    V2 = V1 + 1.
  stepAddEnd (endPole (Card1, Card2, [card (V1, Mast) | Rest], Card4),
              endPole (Card1, Card2, [card (V2, Mast), card (V1, Mast) | Rest], Card4), 3, card (V2, Mast)) :-
    V2 = V1 + 1.
  stepAddEnd (endPole (Card1, Card2, Card3, [card (V1, Mast) | Rest]),
              endPole (Card1, Card2, Card3, [card (V2, Mast), card (V1, Mast) | Rest]), 4, card (V2, Mast)) :-
    V2 = V1 + 1.
  stepAddEnd (endPole ([], Card2, Card3, Card4), endPole ([card (1, Mast)], Card2, Card3, Card4), 1, card (1, Mast)).
  stepAddEnd (endPole (Card1, [], Card3, Card4), endPole (Card1, [card (1, Mast)], Card3, Card4), 2, card (1, Mast)).
  stepAddEnd (endPole (Card1, Card2, [], Card4), endPole (Card1, Card2, [card (1, Mast)], Card4), 3, card (1, Mast)).
  stepAddEnd (endPole (Card1, Card2, Card3, []), endPole (Card1, Card2, Card3, [card (1, Mast)]), 4, card (1, Mast)).

  stepAddPole ([[] | Rest], [[Card] | Rest], 1, Card).
  stepAddPole ([[Card1 | List] | Rest], [[Card, Card1 | List] | Rest], 1, Card) :-
    testCard (Card, Card1).
  stepAddPole ([List | Rest], [List | RestOut], N, Card) :-
    stepAddPole (Rest, RestOut, K, Card),
    N = K + 1.

  testCard (card (Val1, Mast1), card (Val2, Mast2)) :-
    color (Mast1, Color),
    not (color (Mast2, Color)),
    Val1 = Val2 - 1.

  ReadString ([], []) :-
    eof (in), !.
  ReadString (In, Out) :-
    readln (Str),
    split (Str, List),
    prepare (List, In, Pos), !,
    ReadString (Pos, Out).
  ReadString (List, List).

  PrintSteps ([]) :- !.
  PrintSteps ([step (PoleFrom, PoleTo) | Rest]) :-
    write ("From: "),
    PrintCard (PoleFrom),
    write (" to "),
    PrintCard (PoleTo), nl,
    PrintSteps (Rest).

  PrintCard (freePole (N)) :-
    write ("free pole ", N).
  PrintCard (card (N)) :-
    write ("column ", N).
  PrintCard (endPole (N)) :-
    write ("end pole ", N).

  ReadStartPos (File, Pos) :-
    openread (in, File),
    readdevice (in),
    ReadString ([], Pos),
    closefile (in).

  split ("", []) :- !.
  split (In, ["" | List]) :-
    frontchar (In, ' ', Rest), !,
    split1 (Rest, List).
  split (In, [Out | List]) :-
    frontchar (In, C, Rest),
    split (Rest, [Str | List]),
    frontchar (Out, C, Str).

  split1 ("", []) :- !.
  split1 (In, List) :-
    frontchar (In, ' ', Rest), !,
    split1 (Rest, List).
  split1 (In, [Out | List]) :-
    frontchar (In, C, Rest),
    split (Rest, [Str | List]),
    frontchar (Out, C, Str).

  prepare ([], List, List) :- !.
  prepare ([Str | List], [], [[card (Val, Mast)] | OutList]) :-
    !, frontchar (Str, M, V),
    mast (M, Mast),
    value (V, Val),
    prepare (List, [], OutList).
  prepare ([Str | List], [Rest | InList], [[card (Val, Mast) | Rest] | OutList]) :-
    frontchar (Str, M, V),
    mast (M, Mast),
    value (V, Val),
    prepare (List, InList, OutList).

  mast ('t', 'т').
  mast ('c', 'ч').
  mast ('b', 'б').
  mast ('v', 'в').
  mast ('T', 'т').
  mast ('C', 'ч').
  mast ('B', 'б').
  mast ('V', 'в').
  mast ('т', 'т').
  mast ('ч', 'ч').
  mast ('б', 'б').
  mast ('в', 'в').
  mast ('Т', 'т').
  mast ('Ч', 'ч').
  mast ('Б', 'б').
  mast ('В', 'в').

  value ("t" ,  1).
  value ("2" ,  2).
  value ("3" ,  3).
  value ("4" ,  4).
  value ("5" ,  5).
  value ("6" ,  6).
  value ("7" ,  7).
  value ("8" ,  8).
  value ("9" ,  9).
  value ("10", 10).
  value ("j" , 11).
  value ("q" , 12).
  value ("k" , 13).
  value ("J" , 11).
  value ("Q" , 12).
  value ("K" , 13).
  value ("в" , 11).
  value ("д" , 12).
  value ("к" , 13).
  value ("В" , 11).
  value ("Д" , 12).
  value ("К" , 13).