Information Technology Reference
In-Depth Information
2.
Imagine that by virtue of new technology received from outer space, this super-
computer suddenly becomes one billion times faster. This means that jobs that
used to take it ten years to do can now be done in under one second.
3.
Imagine that there are one billion of these supercomputers and that they can all
be made to work together, sharing the job of exploring the search space.
Then,
How many variable assignments can be explored per second?
The answer is
10
9
10
9
10
9
10
27
.
×
×
=
So how long would it take to go through the
9
×
9
Sudoku search space?
The answer is
9
81
10
27
10
50
10
40
÷
=
2
×
seconds, or about
6
×
centuries.
Given these sorts of numbers, it should be no surprise that the generate-and-test
program to solve the
9
×
9
Sudoku problem does not work very well.
5.2.4 Guessed values and forced values
This analysis of the search space seems to be suggest that even the fastest computers
would not be able to solve a 9
9 Sudoku problem. But this is not quite right. The
analysis shows that no computer (or person) would be able to explore the entire
Sudoku search space because it is too large. But, in fact, computers and people
are
able to solve Sudoku problems. How they do so is very different from the method
used in the
4
×
4
case.
The problem with the way the Sudoku and map-coloring problems were solved
is that there was far too much
guessing
: making a random selection from the search
space and then backtracking if it was not right. Sudoku experts do not think this
way. They do very little guessing, and only for the most difficult puzzles (the ones
sometimes called devilish). Instead, they repeatedly try to see if the constraints of the
puzzle
force
the values for certain entries based on the known values of other entries.
For example, figure 5.6 shows a 4
×
×
4 Sudoku problem with a
3
located at position
(
)
(top left) and at position
(
)
(bottom right). It is not hard to see that there
1, 1
4, 4
must be a
3
at
. These two entries are forced.
Programming this type of algorithm for Sudoku would take some work. The
basic idea of using forced values to minimize the guesswork is explored in the next
constraint satisfaction problem, cryptarithmetic.
(
)
and another at
(
)
2, 3
3, 2
