Java Reference
In-Depth Information
solveKnapSack(chosen , goal , i+1,total ) ;
}
}
Running this program, we find that it reported 396 cuts.
9.2.2 Backtracking illustrated: The eight queens puzzle
The queen puzzle consists of placing eight queens on an 8
8 chessboard so that
the queens are in a mutually safe position. That is, none of the queens is able to
capture any other. Figure 9.1 graphically depicts such a solution. Historically,
finding whether there exist solutions was first asked by German chess player
Max Bezzel in 1848. A brute force algorithm will enumerate all possible ways
of putting the eight queens on a chessboard. The exhaustive search paradigm
will thus explore...
64
8
×
= 64
×
×
...
×
63
57
= 283 , 274 , 583 , 552
8!
...different configurations: There are 64 choices for placing the first queen, and
then 63 choices for the second, up to 57 = 64
8 + 1 choices for placing the
last queen. Since queens are not distinguishable, we divide the former number
by the number of queen permutations: 8!.
Figure 9.1 Illustrating one of the 92 distinct
solutions to the eight queen puzzle
Thus a direct implementation of exhaustive search would not be ecient since
the number of recursive calls is too important. We are going to exploit some
structural properties of the eight queen problem to guide the exploration.
Observe that trivially two queens cannot be located on the same row of
the chessboard. Therefore a much better exhaustive search will consider only
8 8 =2 24 =16 , 777 , 216 configurations (for each queen, there are only 8 potential
 
 
Search WWH ::




Custom Search