PG Alicja i Bogdan

nalesniki.pl

% Alice and Bogdan take turns eating naleśniki from two stacks - M, N.
% There is an initial condition given: that M > 2N.
%
% Given two stacks M and N, such that M >= N, one eats K naleśników from the M stack
% where K mod N = 0 and K >= N.
% The first person to eat the last naleśnik from either stack dies.
%
% Alice takes the first turn. How many naleśniki should she eat on each turn
% in order to win (for Bogdan to die)?

:- use_module(library(clpfd)).

% Binds L and G to the lesser and greater (or equal) of M and N respectively
order(M, N, L, G) :-
    M #<  N , L = M , G = N
  ; M #>= N , L = N , G = M.

% Action K performed on current state M0 and N0 gives new state G1 and L1
action(M0, N0, K, M1, N1) :-
    order(M0, N0, L, G)
  , K in L..G , K mod L #= 0 , M1 #= G - K , N1 #= L.

% Winning moves for a given initial state of the stacks
winning(M, N, []) :- M #= 0 ; N #= 0.                 % Alice wins immediately if Bogdan emptied either stack
winning(M, N, [K | Ks]) :-                            % Alice also wins if
    action(M, N, K, M1, N1) , label([K])              %   she takes an action such that
  , M1 #> 0 , N1 #> 0                                 %     she doesn't lose
  , forall((action(M1, N1, L, M2, N2) , label([L])),  %   and for any following action from Bogdan
           winning(M2, N2, Ks)).                      %     she wins afterwards