Information Technology Reference
In-Depth Information
How does this
solution
predicate work? It needs to generate sixteen values. It
starts by using
uniq(R11,R12,R13,R14)
to generate four distinct values for the vari-
ables of row 1. Then it does the same for rows 2, 3, and 4. At this point, all sixteen
variables have values. It then tests
uniq(R11,R21,R31,R41)
, which is for the variables
of column 1. If these four values are distinct, it continues and tests the distinctness
of columns 2, 3, and 4; if they are not distinct, the test fails, and it backtracks to
generate new values for the variables in row 4 or 3 or 2 or perhaps all the way back
to row 1, as necessary. Once all the column tests succeed, the
solution
predicate
tests
uniq(R11,R12,R21,R22)
, which is for the variables of the NW quadrant. If these
four values are distinct, it tests the quadrants NE, SW, and SE in turn; if they are not
distinct, it again backtracks all the way to the rows and tries to generate new values.
If all the column and quadrant tests are successful, a solution has been found, and
the program is done.
5.2.3 Search spaces
It is easy to generalize this
4
9
Sudoku puzzles. Instead of having
twelve constraints (for rows, columns, and quadrants) over sixteen variables, there
would be twenty-seven constraints over eighty-one variables.
Will this work? The answer is, in
principle
, definitely yes; in
practice
, definitely no.
The problem is that the
9
×
4
solution to
9
×
×
×
9
Sudoku puzzle is
much larger
than the
4
4
one. Just
how much larger is worth investigating further.
A useful measure of the size of a constraint satisfaction problem is the size of its
search space. The
search space
is the collection of all the different ways the variables of
a problem can be assigned values from the domain before taking the constraints into
account.
For a 4
4 Sudoku, each of the sixteen variables can take on four possible values.
So there are 4
×
4
16
×
×···×
=
possible assignments to the variables, which is
4
4
10
9
about 4
×
(four billion). This is considered to be small (for computers).
For a 9
9 Sudoku puzzle, each of the eighty-one variables can take on nine
possible values. So there are 9
×
9
81
×
×···×
=
possible assignments to the
9
9
10
77
. This is considered to be enormous.
To understand the insurmountable difficulty this second number poses even for the
fastest supercomputers, it is useful to do a thought experiment:
1.
variables, which is about 2
×
Imagine that there is a supercomputer capable of exploring a billion variable
assignments per second in the search space. (No existing computer is fast enough
to do this.)
