Information Technology Reference
In-Depth Information
Figure 5.5.
A Sudoku solver
sudoku.pl
% The main predicate. Solve the puzzle and print the answer.
% The variable Rij stands for the number in row i and column j.
sudoku(R11,R12,R13,R14,R21,R22,R23,R24,R31,R32,R33,R34,
R41,R42,R43,R44) :-
solution(R11,R12,R13,R14,R21,R22,R23,R24,R31,R32,R33,R34,
R41,R42,R43,R44),
nl, write('A solution to this puzzle is'), nl,
printrow(R11,R12,R13,R14), printrow(R21,R22,R23,R24),
printrow(R31,R32,R33,R34), printrow(R41,R42,R43,R44).
% Print a row of four numbers with spaces between them.
printrow(P,Q,R,S) :- write(' '), write(P), write(' '), write(Q),
write(' '), write(R), write(' '), write(S), nl.
%------------------------------------------------------------------
solution(R11,R12,R13,R14,R21,R22,R23,R24,R31,R32,R33,R34,
R41,R42,R43,R44) :-
uniq(R11,R12,R13,R14), uniq(R21,R22,R23,R24), % rows 1,2
uniq(R31,R32,R33,R34), uniq(R41,R42,R43,R44), % rows 3,4
uniq(R11,R21,R31,R41), uniq(R12,R22,R32,R42), % cols 1,2
uniq(R13,R23,R33,R43), uniq(R14,R24,R34,R44), % cols 3,4
uniq(R11,R12,R21,R22), uniq(R13,R14,R23,R24), % NW and NE
uniq(R31,R32,R41,R42), uniq(R33,R34,R43,R44). % SW and SE
% uniq holds if P,Q,R,S are all distinct nums (from 1 to 4).
uniq(P,Q,R,S) :- num(P), num(Q), num(R), num(S),
\+ P=Q, \+ P=R, \+ P=S, \+ Q=R, \+ Q=S, \+ R=S.
% The four numbers to go into each cell
num(1).
num(2).
num(3).
num(4).
So uniq(1,3,2,4) succeeds, but uniq(1,3,2,3) fails. (This idea of having a certain
number of values that are different from each other shows up in many constraint
satisfaction problems.)
As written, however, the uniq predicate can only be used to test the four arguments
for uniqueness, not to generate them. This is because negation needs its arguments to
be instantiated (see section 3.2.3). Assuming there is a predicate num that can test or
generate the numbers from 1 to 4, the uniq predicate can be rewritten so that it will
test or generate a group of four numbers from 1 to 4 that are unique. Then, using
this predicate for each row, column, or quadrant, one can test or generate a group of
sixteen numbers that solves the Sudoku problem. This is shown in the bottom half of
figure 5.5.
Search WWH ::




Custom Search