:- 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]]