Back-tracking solver of Toads and Frogs game.

toadsfrogs.P

% Program to find all winning plays of Toads and Frogs.
% See http://en.wikipedia.org/wiki/Toads_and_Frogs_(game)
% Author: Jon Brandvein
% Changes:
%   05/02/13 - eliminate list processing helper rules in favor of
%              a simpler append-based definition of player moves
%              (thanks to David Warren)

:- import select/3, append/3 from basics.

% Configurations are represented as lists. Moves are transitions
% from one configuration to another. All moves preserve the size
% of the list and cause only local changes.

writeconf([]).
writeconf([H|T]) :-
    write(H),
    writeconf(T).
writeconf_nl(L) :-
    writeconf(L),
    writeln('').


% Valid moves. Each player can move their frog/toad ("anurum"?)
% forward to an empty space, or hop over one opponent piece
% immediately in front of them.

p1move(C1, C2) :-
    append(Before, [t, '.' | After], C1),
    append(Before, ['.', t | After], C2).
p1move(C1, C2) :-
    append(Before, [t, f, '.' | After], C1),
    append(Before, ['.', f, t | After], C2).

p2move(C1, C2) :-
    append(Before, ['.', f | After], C1),
    append(Before, [f, '.' | After], C2). 
p2move(C1, C2) :-
    append(Before, ['.', t, f | After], C1),
    append(Before, [f, t, '.' | After], C2).

% Play continues until one player has no possible moves.

p1play(C1, CF, V) :-
    p1move(C1, C2),
    p2play(C2, CF, V).
p1play(C1, CF, 'toads win') :-
    p1move(C1, CF),
    not p2play(CF, _, _).
p2play(C1, CF, V) :-
    p2move(C1, C2),
    p1play(C2, CF, V).
p2play(C1, CF, 'frogs win') :-
    p2move(C1, CF),
    not p1play(CF, _, _).

showplays(C) :-
    setof((CF, V), p1play(C, CF, V), L),
    ((select((EC, EV), L, _),
      writeconf(EC), write('  '), write(EV), writeln(''),
      fail);
     writeln('')
    ).

% Example runs.

:- showplays([., t, t, ., f, f]).
:- showplays([t, t, ., ., f, f]).
:- showplays([t,t,.,.,.,f,f]).