Information Technology Reference
In-Depth Information
Figure 5.4.
Using the
sudoku
predicate
?- sudoku(
% Note the anonymous variables in the query.
1, 4, _, _,
_, _, 4, _,
2, _, _, _,
_, _, _, 3
).
A solution to this puzzle is
1432
3241
2314
4123
This anonymous variable can be used to explain what a Sudoku program should
do. The user provides a
partial
solution to the problem and asks the program to print
a
complete
solution. A query is posed with some of the entries filled in the grid, and
the program will print all sixteen entries in a tabular format (see figure 5.4). The top-
level predicate is
sudoku
. Note that the solution shown in the figure satisfies all the
constraints: each row, column, and quadrant uses the numbers 1, 2, 3, and 4.
5.2.2 Sudoku as constraint satisfaction
It is easy to see Sudoku as a constraint satisfaction problem:
There are sixteen variables, one for each entry in the grid.
The domain for each variable is
{
}
.
1, 2, 3, 4
The constraints to be satisfied are the following: for each row, column, and
quadrant, the four variables must have distinct values.
Assuming there is a
solution
predicate that takes sixteen arguments and solves the
constraint satisfaction problem, it is not hard to define the top-level
sudoku
predicate
that does the printing (see the top half of figure 5.5, above the dashed line). The
sudoku
predicate uses
solution
to find a solution, then prints a one-line message,
and finally uses the predicate
printrow
four times to print out each of the rows. As
with
print_colors
, all the thinking happens in the
solution
predicate.
Let us now turn to this
solution
predicate. The easiest way to write the predicate
is to first define a predicate
uniq
that takes four arguments and ensures that they are
all different from each other:
uniq(P,Q,R,S) :- \+ P=Q, \+ P=R, \+ P=S, \+ Q=R, \+ Q=S, \+ R=S.
