The solution to Puzzle 007 “Wolves and Chicks” in Professor Layton and the Curious Village written in Prolog

wolves_and_chicks.pl

% X1 chick, X2 wolf
valid(X1,X2) :- X1 >= X2, 3 - X1 >= 3 - X2, X1 > 0, X2 >= 0, X1 < 3, X2 =< 3.
valid(3,X2) :- X2 >= 0, X2 =< 3.
valid(0,X2) :- X2 >= 0, X2 =< 3.

move(0,1).
move(1,0).
move(0,2).
move(2,0).
move(1,1).
% moving to the right
validmove((X1,X2),(Y1,Y2),(A,B),r) :- move(A,B), Y1 is X1 - A, Y2 is X2 - B, valid(Y1,Y2).
% moving to the left
validmove((X1,X2),(Y1,Y2),(A,B),l) :- move(A,B), Y1 is X1 + A, Y2 is X2 + B, valid(Y1,Y2).
next(r,l).
next(l,r).

solution(START, _, [], _, START).
solution(START, DIRECTION, [(A,B)|Ss], VISITED, END) 
    :- validmove(START, NEXT, (A,B), DIRECTION),
       next(DIRECTION,DIRECTION2),
       not(member((DIRECTION2,NEXT), VISITED)),
       solution(NEXT, DIRECTION2, Ss, [(DIRECTION,START)|VISITED], END).

% to get the solution, type this as a query:
% solution((3,3), r, STEPS, [], (0,0))