% Esercitazioni Prolog
% MPradella, MMXIII


% ===========================
% Consider the operation revmap which reverses a list and then performs a map: 
% i.e. revmap (*2) [1,2,3] is [6,4,1]
% Define a Prolog implementation of revmap traversing the list only once. 

revmap(F,[X|Y],Z,W) :- call(F,X,X1), revmap(F,Y,[X1|Z],W). 
revmap(_,[],X,X).


%% test it
cube(X,R) :- R is X*X*X.
testrev :- revmap(cube, [2,3,4], [], X), print(X), nl.



% ===========================
% Consider a tree whose nodes are stored as lists, and the first
% element is the value stored at that node, while the other elements are subtrees.
% Define a possibly concise function to find an element in the tree

% version 1:
% we suppose that trees are stored as lists [key, subtree_1, subtree_2, ...]
% e.g. [root,[a,[b,1,2,3],[c,2],[f,[g,x,y]]]]

findlist([],_) :- fail.
findlist([X|_],X).
findlist([Y|L],X) :- findlist(Y,X) ; findlist(L,X). 




testfindlist :- 
    findlist([root,[a,[b,1,2,3],[c,2],[f,[g,x,y]]]], f).




% version 2:
% a more natural way of representing such trees is by using terms
% e.g. root(a,b(1,2,3),c(2),f(g(x,y)))

findtreel([],_) :- fail.
findtreel([Y|_],X) :- findtree(Y,X).
findtreel([_|L],X) :- findtreel(L,X). 

findtree(X,X).
findtree(T,X) :- T =.. [X|_].
findtree(T,X) :- T =.. [_|L], findtreel(L,X).



testfindtree :- 
    findtree(root(a,b(1,2,3),c(2),f(g(x,y))), a).




% =============================
% try: A.
% =============================





% ===========================
% Implement the Prolog predicate countpreds, which has two inputs: 
% an atom x, and a binary tree t. 
% Such predicate must return the number of times that 
% x is used as an internal node in t.
%
% E.g.
% if x = a, t = a(1,a(c(1,2),a(1,1))), countpreds returns 3;
% if x = a, t = a(1,a(c(1,2),a)), countpreds returns 2.

countpreds(_, Tree, C) :- atomic(Tree), !, C is 0.
countpreds(Name, Tree, C) :- 
    Tree =.. [X,L1,L2], X = Name, !,
    countpreds(Name, L1, C1), 
    countpreds(Name, L2, C2),
    C is C1+C2+1.
countpreds(Name, Tree, C) :- 
    Tree =.. [_,L1,L2], !,
    countpreds(Name, L1, C1), 
    countpreds(Name, L2, C2),
    C is C1+C2.



testcountpreds :-
    countpreds(a, a(1,a(c(1,2),a(1,1))), N),
    print(N), nl.





% ===========================
% Towers of Hanoi
% (not very meaningful, in C it is almost the same)
%
%        **       |       |
%       ****      |       |
%      ******     |       |
%   --------------------------
%        a        b       c

hanoi(N) :- dohanoi(N, a, b, c). % Move the tower from peg a to peg b

dohanoi(0, _, _, _)	:- !.
dohanoi(N, A, B, C)	:- !,
	N1 is N-1,
    dohanoi(N1, A, C, B), % move the N-1 top-most from A to C
	moveit(A, B),         % move the last one
    dohanoi(N1, C, B, A). % move the ones in C to B

moveit(F, T) :- print(F), print(--->), print(T), nl.

testhanoi :- hanoi(4).



% ===========================
% Sudoku solver - variant of a version found on the Web,
% original author unknown


% Prerequisites



% For-All
%
% example:
%  member(X=Y, [a=b, c=d]).
%  X = a,
%  Y = b ;
%  X = c,
%  Y = d.
%
%  forall(member(X=Y, [a=b, c=d]), (atomic(X), atomic(Y))).

% ! forall implementation:
all(Cond, Action) :- \+ (Cond, \+ Action).

% es: all(member(X, [1,2,3]), X > 0).




% The standard Sudoku relation:
%
%    1 2 3 4 5 6 7 8 9
%  1
%  2   1     2     3 
%  3
%  4 
%  5   4     5     6
%  6       x
%  7  
%  8   7     8     9
%  9

related(vt(R,_), vt(R,_)).
related(vt(_,C), vt(_,C)).
related(vt(R,C), vt(R1,C1)) :- 
    A  is ((R  - 1) // 3) * 3 + ((C  - 1) // 3) + 1, 
    A1 is ((R1 - 1) // 3) * 3 + ((C1 - 1) // 3) + 1, 
    A = A1. 

%  e.g. position x is vt(6,4), area: 5
% 
% s relation is for the solution: 
% e.g. s(vt(6,4), 3)



/**
* Brute force Sudoku solver 
*
* For all vertices choose a color from 1..9, such
* that none of the related vertices have the same color.
* Grouping constraints are encoded in related(V1, V2) predicate.
*/

colors(C) :- C = [1, 2, 3, 4, 5, 6, 7, 8, 9].

sudoku_solve([], _, Solution, Solution).
sudoku_solve([V | Vr], Hints, Solution, Result) :-
    member(s(V,Ch), Hints),
    sudoku_solve(Vr, Hints, [s(V,Ch) | Solution], Result).
sudoku_solve([V | Vr], Hints, Solution, Result) :-
    colors(Cols), member(C,Cols),
    forall(member(s(Vs1,Cs1), Hints),    
           (Cs1 \= C ; not(related(V, Vs1)))), 
    forall(member(s(Vs2,Cs2), Solution), 
           (Cs2 \= C ; not(related(V, Vs2)))),
    sudoku_solve(Vr, Hints, [s(V,C) | Solution], Result). 



% let us try the algorithm

% define board
% i.e. double loop on 1..9 
board(B) :-
    colors(C),
    def_row_board(C, C, [], B).

% loop on the first argument (i.e. row)
def_row_board([], _, S, S).
def_row_board([R | Rs], C, B, S) :-
    def_col_board(R, C, B, S1),
    def_row_board(Rs, C, S1, S).

% loop on the second argument (i.e. column)
def_col_board(_, [], S, S).
def_col_board(R, [C | Cs], B, S) :-
    def_col_board(R, Cs, [vt(R, C) | B], S).



% hints from image example (from Wikipedia)
hints(H) :- H = [s(vt(1,1), 5), s(vt(1,2), 3), s(vt(1,5), 7),
                 s(vt(2,1), 6), s(vt(2,4), 1), s(vt(2,5), 9),
                 s(vt(2,6), 5), s(vt(3,2), 9), s(vt(3,3), 8),
                 s(vt(3,8), 6), s(vt(4,1), 8), s(vt(4,5), 6),
                 s(vt(4,9), 3), s(vt(5,1), 4), s(vt(5,4), 8),
                 s(vt(5,6), 3), s(vt(5,9), 1), s(vt(6,1), 7),
                 s(vt(6,5), 2), s(vt(6,9), 6), s(vt(7,2), 6),
                 s(vt(7,7), 2), s(vt(7,8), 8), s(vt(8,4), 4),
                 s(vt(8,5), 1), s(vt(8,6), 9), s(vt(8,9), 5),
                 s(vt(9,5), 8), s(vt(9,8), 7), s(vt(9,9), 9)].

testsudo :-
    board(B), 
    hints(H),
    sudoku_solve(B, H, [], S),
    print(S).





