Reyhane
2011/5/10, 07:51 AM
تقديم شماhttp://artificial.ir/intelligence/images/smilies/yahoo/5.gif
Prolog Sudoku Solver (http://blog.milesbarr.com/2007/01/prolog-sudoku-solver/)
GNU Prolog code to solve sudoku puzzels (http://student.science.uva.nl/%7Enout/sud.pl)
كد:
%
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) :-
statistics(cputime,Cpu), % to count cpu time+
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,
write('cpu time taken: '),
statistics(cputime,CpuNew),
CpuUsed is CpuNew - Cpu,
writeln(CpuUsed). % close the file
solve(List,C) :- %solve List max C times
correct_whole(List),!,
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.
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).
Powered by vBulletin® Version 4.1.12 Copyright © 2012 vBulletin Solutions, Inc. All rights reserved.