/*
 * Non tail recursive version of factorial with two clauses
 */
fact(0, 1).
fact(N, F) :- N > 0, N1 is N-1, fact(N1, F1), F is F1 * N.

/*
 * Non tail recursive version of factorial with if-then-else
 */
fact_ite(N, F) :-
    ( N =:= 0 -> F = 1
    ; N > 0, N1 is N-1, fact_ite(N1, F1), F is F1 * N
    ).

/*
 * Tail recursive version of factorial with if-then-else
 */
fact_ite_tr(N, F) :-
    fact_ite_tr(N, 1, F).

fact_ite_tr(N, Fin, Fout) :-
    ( N =:= 0 -> Fout = Fin
    ; N > 0, N1 is N-1, Fnext is Fin * N, fact_ite_tr(N1, Fnext, Fout)
    ).


/*======================================================*/
/*   Winning Tic-Tac-Toe				*/
/*======================================================*/

winner(L) :- L = [_,_,_], triple(L, T), is_winning_triple(T).

triple(L, T) :- member(T, L).	                  % get the rows
triple(L, T) :- transpose(L, LT), member(T, LT).  % get the columns
%% triple([[A,_,_],[D,_,_],[G,_,_]], [A,D,G]).    % get the first column
%% triple([[_,B,_],[_,E,_],[_,H,_]], [B,E,H]).    % get the second column
%% triple([[_,_,C],[_,_,F],[_,_,I]], [C,F,I]).    % get the third column
triple([[A,_,_],[_,B,_],[_,_,C]], [A,B,C]).       % get one diagonal
triple([[_,_,A],[_,B,_],[C,_,_]], [C,B,A]).       % get another diagonal

transpose([[A,B,C],[D,E,F],[G,H,I]], [[A,D,G],[B,E,H],[C,F,I]]).

is_winning_triple([x,x,x]).
is_winning_triple([x,x,b]).
is_winning_triple([x,b,x]).
is_winning_triple([b,x,x]).


/*==============================================================*/
/* Solution to the eight queens problem				*/
/*==============================================================*/

eight_queens(Queens) :-
    Queens = [1/_, 2/_, 3/_, 4/_, 5/_, 6/_, 7/_, 8/_],
    safe(Queens).

safe([]).
safe([X/Y|Qs]) :-
    safe(Qs),
    member(Y, [1,2,3,4,5,6,7,8]),
    no_attack(X/Y, Qs).

no_attack(_/_, []).
no_attack(X/Y, [X1/Y1|Qs]) :-
    % X =\= X1,		% this constraint is always true due to representation
    Y =\= Y1,
    abs(Y1-Y) =\= abs(X1-X),
    no_attack(X/Y, Qs).

/*==============================================================*/
/* Solution to the zebra puzzle	using the representation:	*/
/*    house(Nationality, Color, Pet, Smoke, Drink)		*/
/*==============================================================*/

drinks_water(Nationality) :-
    zebra_puzzle(Houses), member(house(Nationality, _, _, _, water), Houses).

owns_zebra(Nationality) :-
    zebra_puzzle(Houses), member(house(Nationality, _, zebra, _, _), Houses).

zebra_puzzle(Houses) :-
    Houses = [house(norwegian, _, _, _, _),
	      house(_, blue, _, _, _),
	      house(_, _, _, _, milk), _, _],
    member(house(englishman, red, _, _, _), Houses),
    member(house(spaniard, _, dog, _, _), Houses),
    member(house(_, green, _, _, coffee), Houses),
    member(house(ukranian, _, _, _, tea), Houses),
    rightof(house(_, green, _, _, _), house(_, white, _, _, _), Houses),
    member(house(_, _, snails, old_gold, _), Houses),
    % member(house(_, yellow, _, kools, _), Houses),
    nextto(house(_, _, _, chesterfields, _), house(_, _, fox, _, _), Houses),
    nextto(house(_, yellow, _, kools, _), house(_, _, horse, _, _), Houses),
    member(house(_, _, _, lucky_strike, orange_juice), Houses),
    member(house(japanese, _, _, parliaments, _), Houses).

rightof(R, L, [L,R,_,_,_]).
rightof(R, L, [_,L,R,_,_]).
rightof(R, L, [_,_,L,R,_]).
rightof(R, L, [_,_,_,L,R]).

nextto(H1, H2, Houses) :- rightof(H1, H2, Houses).
nextto(H1, H2, Houses) :- rightof(H2, H1, Houses).