Hi guys,
I have been trying to understand this sudoku solver in prolog. But I can't really fathom it ! I've spent 2 nights on it without advancing much. Can you please help me by adding comments or explaining parts of this code?
Thanks!
Code :
%GNU Prolog code to solve sudoku puzzels
%written by Niels & Andreas
:- dynamic(counter/1).
go :-
File = 'sudoku.txt',% the file to read from, file should have 9 lines, each 9 charaters
start(File).% 0 or spaces should be used for unknown values
start(File) :-
write(trying_file(File)),nl,% writeln doesn't work in GNU prolog
see(File),% open file
(readall(List),nl,% read the file into the List
write('list after reading: '),nl,
pretty_sudo_print(List),nl,% print to see if reading went ok
retractall(counter(_)),
SolveTimes = 10,
assert(counter(SolveTimes)),
solve(List,SolveTimes)
;
true
),
seen.% close the file
solve(List,C) :-%solve List max C times
correct_whole(List),!, %vérifier que la liste est correcte
fill_numbers_in(List),
retract(counter(X)),
Xnew is X -1,
Numb is C - X +1,
write('number '),write(Numb),write(' found: '),
pretty_sudo_print(List),nl,
(Xnew < 1,!,
write('solving completed: '),write(C),write(' solutions found.... there might be more out there ... '),
fail;
true
),
assert(counter(Xnew)),
fail.
% S'il y a erreur.
solve(List,_) :-
writeln(not_able_to_solve(List)).
correct_whole(List) :-% check the file which was read for mistakes already existing
control_hori(List),
control_verti(List),
control_regio(List).
% check if all rows have no double items
control_hori([]).
control_hori([H|T]) :-
all_different(H),
control_hori(T).
% check if all columns have no double items
control_verti([[],[],[],[],[],[],[],[],[]]).
control_verti([[A|TA],[B|TB],[C|TC],[D|TD],[E|TE],[F|TF],[G|TG],[H|TH],[I|TI]]) :-
all_different([A,B,C,D,E,F,G,H,I]),
control_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI]).
% check if every 3x3 area has no double items
control_regio([]).
control_regio([A,B,C|T]) :-
control_regio_row([A,B,C]),
control_regio(T).
control_regio_row([[],[],[]]).
control_regio_row([[A,B,C|TA],[D,E,F|TB],[G,H,I|TC]]) :-
all_different([A,B,C,D,E,F,G,H,I]),
control_regio_row([TA,TB,TC]).
correct_part(List,X,Y) :-% control a part of the sudoku with locations X and Y
control_part_verti(List,Y),
control_part_regio(List,X,Y),!.
control_part_verti([[A|_],[B|_],[C|_],[D|_],[E|_],[F|_],[G|_],[H|_],[I|_]],1) :-%right column found
!,
all_different([A,B,C,D,E,F,G,H,I]).
control_part_verti([[_|TA],[_|TB],[_|TC],[_|TD],[_|TE],[_|TF],[_|TG],[_|TH],[_|TI]],Y) :-
Ynew is Y -1,
control_part_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI],Ynew).%check next column
control_part_regio(List,X,Y) :-
Xnew is (X -1)// 3,% make the 9x9 to a 3x3
Ynew is (Y -1)// 3,
control_part_regio_area(List,Xnew,Ynew).
control_part_regio_area([Row1,Row2,Row3|_],0,Y) :-
!,control_part_regio_row([Row1,Row2,Row3],Y).% rows where the 3x3 area is are found
control_part_regio_area([_,_,_|List],X,Y) :-
Xnew is X -1,
control_part_regio_area(List,Xnew,Y).% try next rows
control_part_regio_row([[A,B,C|_],[D,E,F|_],[G,H,I|_]],0) :-% 3x3 area found
!,all_different([A,B,C,D,E,F,G,H,I]).
control_part_regio_row([[_,_,_|TA],[_,_,_|TB],[_,_,_|TC]],Y) :-
Ynew is Y -1,
control_part_regio_row([TA,TB,TC],Ynew).%check next columns
all_different([]) :- !.% an empty list has no double items
all_different([H|T]) :-
(var(H)% if H is a Var, don't let it match with other items in the list
;
not(membervar(H,T))% else, make sure H is not in T
),!,
all_different(T).%check rest of list
membervar(H,[Var|T]) :-
var(Var),!,% don't match Var with H
membervar(H,T).% check if H is in T
membervar(H,[H|_]) :- !.
membervar(H,[_|T]) :-
!,membervar(H,T).
fill_numbers_in(List) :-
findanVar(H,List,0,X,Y,Sublist),%find an var
difference([1,2,3,4,5,6,7,8,9],Sublist,Choices),
!,
member(H,Choices),% find available number for that row
correct_part(List,X,Y), ,
fill_numbers_in(List).%check if it is correct
fill_numbers_in(_).%there are no vars to fill in anymore.
% give difference bewteen List and another list, all items which are in 1st but not in 2nd
difference(List,[],List) :- !.
difference(List,[H|Sublist],Difference) :-
var(H),!,difference(List,Sublist,Difference),!.
difference(List,[H|Sublist],Difference) :-
remove(H,List,Newlist),
difference(Newlist,Sublist,Difference),!.
% remove item from the list
remove(H,[H|T],T) :- !.%there is always max one time H in the list
remove(_,[],[]).
remove(H,[V|T],[V|NewT]) :-
remove(H,T,NewT).
findanVar(V,[Row|_],X,Xend,Yend,Row) :-
Xnew is X +1,
findaVar(V,Row,Xnew,1,Xend,Yend).% find a Var inside this row
findanVar(V,[_|Rest],X,Xend,Yend,Sublist) :-
Xnew is X +1,
findanVar(V,Rest,Xnew,Xend,Yend,Sublist).%loop thru all horizontal rows
findaVar(V,[V|_],X,Y,X,Y) :-%lovely.. :]
var(V),!.
findaVar(V,[_|T],X,Y,Xend,Yend) :-
Ynew is Y + 1,
findaVar(V,T,X,Ynew,Xend,Yend),!.
% to read from the file
readall(List) :-
List = [_,_,_,_,_,_,_,_,_],
readrows(List),!.
readall(_) :-
write('reading failed :/'),!,fail.
readrows([]).
readrows([H|T]) :-
readrow(H),
readrows(T).
%read one row
readrow(Var) :-
Var = [_,_,_,_,_,_,_,_,_],
readchars(Var).
readchars([]) :-
get0(Y),
(Y == 10 ; Y == 13; Y == -1),!.
readchars([H|T]) :-
get0(Y),
(((Y == 10 ; Y == 13),!,readchars([H|T]));
((Y == 32;Y == 48),!;
(Y > 48,Y < 58,!,H is Y - 48)
),
readchars(T)).
% pretty printing \0/
pretty_sudo_print([]).
pretty_sudo_print([A,B,C|T]) :-
nl,printsudorow(A),
printsudorow(B),
printsudorow(C),
pretty_sudo_print(T).
printsudorow([]) :- nl.
printsudorow([A,B,C|T]) :-
writerepv(A),tab(1),
writerepv(B),tab(1),
writerepv(C),tab(3),
printsudorow(T).
writerepv(X) :-
var(X),!,write(' ').
writerepv(X) :-
write(X).
I have been trying to understand this sudoku solver in prolog. But I can't really fathom it ! I've spent 2 nights on it without advancing much. Can you please help me by adding comments or explaining parts of this code?
Thanks!
Code :
%GNU Prolog code to solve sudoku puzzels
%written by Niels & Andreas
:- dynamic(counter/1).
go :-
File = 'sudoku.txt',% the file to read from, file should have 9 lines, each 9 charaters
start(File).% 0 or spaces should be used for unknown values
start(File) :-
write(trying_file(File)),nl,% writeln doesn't work in GNU prolog
see(File),% open file
(readall(List),nl,% read the file into the List
write('list after reading: '),nl,
pretty_sudo_print(List),nl,% print to see if reading went ok
retractall(counter(_)),
SolveTimes = 10,
assert(counter(SolveTimes)),
solve(List,SolveTimes)
;
true
),
seen.% close the file
solve(List,C) :-%solve List max C times
correct_whole(List),!, %vérifier que la liste est correcte
fill_numbers_in(List),
retract(counter(X)),
Xnew is X -1,
Numb is C - X +1,
write('number '),write(Numb),write(' found: '),
pretty_sudo_print(List),nl,
(Xnew < 1,!,
write('solving completed: '),write(C),write(' solutions found.... there might be more out there ... '),
fail;
true
),
assert(counter(Xnew)),
fail.
% S'il y a erreur.
solve(List,_) :-
writeln(not_able_to_solve(List)).
correct_whole(List) :-% check the file which was read for mistakes already existing
control_hori(List),
control_verti(List),
control_regio(List).
% check if all rows have no double items
control_hori([]).
control_hori([H|T]) :-
all_different(H),
control_hori(T).
% check if all columns have no double items
control_verti([[],[],[],[],[],[],[],[],[]]).
control_verti([[A|TA],[B|TB],[C|TC],[D|TD],[E|TE],[F|TF],[G|TG],[H|TH],[I|TI]]) :-
all_different([A,B,C,D,E,F,G,H,I]),
control_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI]).
% check if every 3x3 area has no double items
control_regio([]).
control_regio([A,B,C|T]) :-
control_regio_row([A,B,C]),
control_regio(T).
control_regio_row([[],[],[]]).
control_regio_row([[A,B,C|TA],[D,E,F|TB],[G,H,I|TC]]) :-
all_different([A,B,C,D,E,F,G,H,I]),
control_regio_row([TA,TB,TC]).
correct_part(List,X,Y) :-% control a part of the sudoku with locations X and Y
control_part_verti(List,Y),
control_part_regio(List,X,Y),!.
control_part_verti([[A|_],[B|_],[C|_],[D|_],[E|_],[F|_],[G|_],[H|_],[I|_]],1) :-%right column found
!,
all_different([A,B,C,D,E,F,G,H,I]).
control_part_verti([[_|TA],[_|TB],[_|TC],[_|TD],[_|TE],[_|TF],[_|TG],[_|TH],[_|TI]],Y) :-
Ynew is Y -1,
control_part_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI],Ynew).%check next column
control_part_regio(List,X,Y) :-
Xnew is (X -1)// 3,% make the 9x9 to a 3x3
Ynew is (Y -1)// 3,
control_part_regio_area(List,Xnew,Ynew).
control_part_regio_area([Row1,Row2,Row3|_],0,Y) :-
!,control_part_regio_row([Row1,Row2,Row3],Y).% rows where the 3x3 area is are found
control_part_regio_area([_,_,_|List],X,Y) :-
Xnew is X -1,
control_part_regio_area(List,Xnew,Y).% try next rows
control_part_regio_row([[A,B,C|_],[D,E,F|_],[G,H,I|_]],0) :-% 3x3 area found
!,all_different([A,B,C,D,E,F,G,H,I]).
control_part_regio_row([[_,_,_|TA],[_,_,_|TB],[_,_,_|TC]],Y) :-
Ynew is Y -1,
control_part_regio_row([TA,TB,TC],Ynew).%check next columns
all_different([]) :- !.% an empty list has no double items
all_different([H|T]) :-
(var(H)% if H is a Var, don't let it match with other items in the list
;
not(membervar(H,T))% else, make sure H is not in T
),!,
all_different(T).%check rest of list
membervar(H,[Var|T]) :-
var(Var),!,% don't match Var with H
membervar(H,T).% check if H is in T
membervar(H,[H|_]) :- !.
membervar(H,[_|T]) :-
!,membervar(H,T).
fill_numbers_in(List) :-
findanVar(H,List,0,X,Y,Sublist),%find an var
difference([1,2,3,4,5,6,7,8,9],Sublist,Choices),
!,
member(H,Choices),% find available number for that row
correct_part(List,X,Y), ,
fill_numbers_in(List).%check if it is correct
fill_numbers_in(_).%there are no vars to fill in anymore.
% give difference bewteen List and another list, all items which are in 1st but not in 2nd
difference(List,[],List) :- !.
difference(List,[H|Sublist],Difference) :-
var(H),!,difference(List,Sublist,Difference),!.
difference(List,[H|Sublist],Difference) :-
remove(H,List,Newlist),
difference(Newlist,Sublist,Difference),!.
% remove item from the list
remove(H,[H|T],T) :- !.%there is always max one time H in the list
remove(_,[],[]).
remove(H,[V|T],[V|NewT]) :-
remove(H,T,NewT).
findanVar(V,[Row|_],X,Xend,Yend,Row) :-
Xnew is X +1,
findaVar(V,Row,Xnew,1,Xend,Yend).% find a Var inside this row
findanVar(V,[_|Rest],X,Xend,Yend,Sublist) :-
Xnew is X +1,
findanVar(V,Rest,Xnew,Xend,Yend,Sublist).%loop thru all horizontal rows
findaVar(V,[V|_],X,Y,X,Y) :-%lovely.. :]
var(V),!.
findaVar(V,[_|T],X,Y,Xend,Yend) :-
Ynew is Y + 1,
findaVar(V,T,X,Ynew,Xend,Yend),!.
% to read from the file
readall(List) :-
List = [_,_,_,_,_,_,_,_,_],
readrows(List),!.
readall(_) :-
write('reading failed :/'),!,fail.
readrows([]).
readrows([H|T]) :-
readrow(H),
readrows(T).
%read one row
readrow(Var) :-
Var = [_,_,_,_,_,_,_,_,_],
readchars(Var).
readchars([]) :-
get0(Y),
(Y == 10 ; Y == 13; Y == -1),!.
readchars([H|T]) :-
get0(Y),
(((Y == 10 ; Y == 13),!,readchars([H|T]));
((Y == 32;Y == 48),!;
(Y > 48,Y < 58,!,H is Y - 48)
),
readchars(T)).
% pretty printing \0/
pretty_sudo_print([]).
pretty_sudo_print([A,B,C|T]) :-
nl,printsudorow(A),
printsudorow(B),
printsudorow(C),
pretty_sudo_print(T).
printsudorow([]) :- nl.
printsudorow([A,B,C|T]) :-
writerepv(A),tab(1),
writerepv(B),tab(1),
writerepv(C),tab(3),
printsudorow(T).
writerepv(X) :-
var(X),!,write(' ').
writerepv(X) :-
write(X).