:- use_module(library(clpfd)).

% solve a SuDoku puzzle given as list of rows
sudoku(Rows) :-
	concat(Rows,Digits), domain(Digits,1,9), % every entry is a digit
	
	all(all_different,Rows), % digits in rows are different
	transpose(Rows,Cols), all(all_different,Cols), % also in cols
	squares(Rows,Squares), all(all_different,Squares), % and in squares
	
	labeling([],Digits). % label entries

% construct and decompose lists
cons(X,Xs,[X|Xs]).
head([X|_],X).
tail([_|Xs],Xs).

% map unary predicate over list
all(_,[]).
all(P,[X|Xs]) :- Call =.. [P,X], call(Call), all(P,Xs).

% map binary predicate over lists
map(_,[],[]).
map(P,[X|Xs],[Y|Ys]) :- Call =.. [P,X,Y], call(Call), map(P,Xs,Ys).

% combine 3 lists with given predicate
zipWith3(_,[],[],[],[]).
zipWith3(P,[X|Xs],[Y|Ys],[Z|Zs],[E|R]) :-
	Call =.. [P,X,Y,Z,E], call(Call), zipWith3(P,Xs,Ys,Zs,R).

% fold a list with given predicate and unit element
foldr(_,E,[],E).
foldr(P,E,[X|Xs],R) :- foldr(P,E,Xs,R1), Call =.. [P,X,R1,R], call(Call).

% append two lists
append(Xs,Ys,Zs) :- foldr(cons,Ys,Xs,Zs).

% concatenate a list of lists
concat(Xs,Ys) :- foldr(append,[],Xs,Ys).

% transpose a matrix
transpose([[]|_],[]).
transpose(L,[X|Ys]) :- map(head,L,X), map(tail,L,Xs), transpose(Xs,Ys).

% compute squares of 9 in given matrix
squares(Xs,L) :-
	map(group3,Xs,L1), group3(L1,L2), map(combine,L2,L3), concat(L3,L).

% group list into lists of length 3
group3([],[]).
group3([X,Y,Z|Xs],[[X,Y,Z]|Ys]) :- group3(Xs,Ys).

% combine grouped rows to obtain squares
combine([X,Y,Z],L) :- zipWith3(append3,X,Y,Z,L).

% append 3 lists
append3(Xs,Ys,Zs,L) :- concat([Xs,Ys,Zs],L).

% example call

% | ?- Puzzle =
%      [[9,_,_,2,_,_,5,_,_],
%       [_,4,_,_,6,_,_,3,_],
%       [_,_,3,_,_,_,_,_,6],
%       [_,_,_,9,_,_,2,_,_],
%       [_,_,_,_,5,_,_,8,_],
%       [_,_,7,_,_,4,_,_,3],
%       [7,_,_,_,_,_,1,_,_],
%       [_,5,_,_,2,_,_,4,_],
%       [_,_,1,_,_,6,_,_,9]],
%      sudoku(Puzzle),
%      write(Puzzle).

% [[9,6,8,2,4,3,5,7,1],
%  [1,4,5,7,6,9,8,3,2],
%  [2,7,3,8,1,5,4,9,6],
%  [8,1,6,9,3,7,2,5,4],
%  [3,9,4,1,5,2,6,8,7],
%  [5,2,7,6,8,4,9,1,3],
%  [7,3,2,4,9,8,1,6,5],
%  [6,5,9,3,2,1,7,4,8],
%  [4,8,1,5,7,6,3,2,9]]