/*
author: Wiebke Petersen
date: 11.5.2017
topic: Constraint Logic Programming in Prolog


Good Tutorial on CLP: http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html
The manual on clpfd is also very good.
library clpfd: Constraint Logic Programming over Finite Domains
*/

:- use_module(library(clpfd)).
:- use_module(library(lists)).
:- use_module(library(apply)).

/*
Some builtin predicates that will be used in the sudoku solver below:

same_length(List1,List2) from lists: true if List1 and List2 have the same length.
?- same_length([1,2],[1,2,3]).
?- same_length([1,2],X).


transpose(Rows,Columns) from clpfd: true if Rows is a list of lists of same lengths and
Columns is the transposed matrix.
?- transpose([[1,2,3],[4,5,6]],L).
append(ListOfLists,List): List is the result of appending all lists in ListOfLists
?- append([[1,2],[3],[4,5,6]],L).

maplist(Function,List) from apply: applies the function Function to every element in List
?- maplist(=(1),[X,Y,Z]).
?- maplist(=([1|_]),[X,Y,Z]).
?- maplist(=([1|_]),[X,Y,Z]), X=[1,2],Y=[1,3].
?- maplist(same_length([a,b,c]),[L,M]).

writeln/1: Short for 'write(X),nl'

X in N..M. : puts a constraint on X restricting it to be a natural number between N and M.
List ins N..M. : puts a constraint on the elements of List restricting them to be natural numbers between N and M.
#/\ : conjunction of constraints
#\/: disjunction of constraints
#\ : inversion of constraint
domain constraints by boundaries: #>, #<
#= : constraint equal numeric value

?- X in 1..2.
?- X in 1..3 #/\ X in 3..7.
?- length(L,3), L ins 1..3.
?- X#>Y,X in 1..4, Y in 3..5.


all_different/1 from clpfd:  all_different(List) adds a constraint on the list elements that they
must be different.
?- length(L,4), all_different(L), L ins 1..4, L=[1,2,3,_].
?- length(L,4), all_different(L), L ins 1..3, L=[1,2,3,_].
?- length(L,4), all_different(L), L ins 1..3.

all_distinct/1 from clpfd: like all_different/1 but it is immediately checked whether the constraints can
be fullfilled.
?- length(L,4), all_different(L), L ins 1..4.
?- length(L,4), all_different(L), L ins 1..3.

label/1, label(List): predicate for grounding variables. An instantiation fullfilling all constraints which are put on
the variable in the list is searched and the variables are instantiated accordingly.
?-  X in 1..4, Y in 1..4, X#=Y+2.
?-  X in 1..4, Y in 1..4, X#=Y+2,label([X]).
?-  X in 1..4, Y in 1..4, X#=Y+4,label([X]).
?- length(L,4), all_different(L), L ins 1..3,label(L).
?- length(A,3),A ins 1..3,all_different(A),length(L,4),maplist(=(A),L),maplist(label,L).
?- length(A,3),maplist(same_length(A),A),append(A,AllVars),AllVars ins 1..3,maplist(all_different,A).
?- length(A,3),maplist(same_length(A),A),append(A,AllVars),AllVars ins 1..3,maplist(all_different,A),maplist(label,A).
?- N = 4, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], label([B,C]).
?- N = 3, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], label([B,C]).
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], label([B,C]).

*/

% sudoku solver with constraints (using all_distinct)
% ?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows).
% Try what happens if the problem has more than one solution (problem 3)
sudoku(Rows) :-
        length(Rows, 9), maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs),
        blocks(Ds, Es, Fs),
        blocks(Gs, Hs, Is).

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

problem(2, [[9,8,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

problem(3, [[_,8,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,_]]).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

n_factorial(0, 1).
n_factorial(N, F) :-
        N #> 0,
        N1 #= N - 1,
        F #= N * F1,
        n_factorial(N1, F1).






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
        Vars = [S,E,N,D,M,O,R,Y],
        Vars ins 0..9,
        all_different(Vars),
                  S*1000 + E*100 + N*10 + D +
                  M*1000 + O*100 + R*10 + E #=
        M*10000 + O*1000 + N*100 + E*10 + Y,
        %M #\= 0, S #\= 0,
        label(Vars).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ?- increase([1,3,6,8,9]).
% ?- increase([1,8,3,6,8,9]).
% ?- increase([1,3,X,8,9]).

increase([_]).
increase([X,Y|T]):- X #< Y, increase([Y|T]).




hoo(X,Y):- X in 1..5, Y in 3..7,X#=Y+1,label([X]).
