Java Reference
In-Depth Information
Note that Step 1 in Listing 22.8 is performed only once to presort the points. Assume that
all the points are presorted. Let
T
(
n
) denote the time complexity for this algorithm. Thus,
Step 2
Step 3
O
(
n
log
n
)
Therefore, the closest pair of points can be found in
O
(
n
log
n
) time. The complete implemen-
tation of this algorithm is left as an exercise (see Programming Exercise 22.7).
T
(
n
)
=
2
T
(
n
/2)
+
O
(
n
)
=
22.19
✓
✓
What is the divide-and-conquer approach? Give an example.
Check
22.20
Point
What is the difference between divide-and-conquer and dynamic programming?
22.21
Can you design an algorithm for finding the minimum element in a list using divide-
and-conquer? What is the complexity of this algorithm?
Backtracking
This section solves the Eight Queens problem using the backtracking approach.
Key
Point
The Eight Queens problem is to find a solution to place a queen in each row on a chessboard
such that no two queens can attack each other. The problem can be solved using recursion (See
Programming Exercise 18.34). In this section, we will introduce a common algorithm design
technique called
backtracking
for solving this problem. The backtracking approach searches
for a candidate solution incrementally, abandoning that option as soon as it determines that the
candidate cannot possibly be a valid solution, and then looks for a new candidate.
You can use a two-dimensional array to represent a chessboard. However, since each row
can have only one queen, it is sufficient to use a one-dimensional array to denote the position
of the queen in the row. Thus, you can define the
queens
array as:
int
[] queens =
new int
[
8
];
backtracking
Assign
j
to
queens[i]
to denote that a queen is placed in row
i
and column
j
. Figure 22.6a
shows the contents of the
queens
array for the chessboard in Figure 22.6b.
0
4
7
5
2
6
1
3
queens[0]
queens[1]
queens[2]
queens[3]
queens[4]
queens[5]
queens[6]
queens[7]
(a)
(b)
F
IGURE
22.6
queens[i]
denotes the position of the queen in row
i
.
0, where
k
is the index of the current row
being considered. The algorithm checks whether a queen can be possibly placed in the
j
th
column in the row for
j
The search starts from the first row with
k
=
search algorithm
=
0, 1,
c
, 7, in this order. The search is implemented as follows:
If successful, it continues to search for a placement for a queen in the next row. If the
current row is the last row, a solution is found.
■
If not successful, it backtracks to the previous row and continues to search for a new
placement in the next column in the previous row.
■
If the algorithm backtracks to the first row and cannot find a new placement for a
queen in this row, no solution can be found.
Eight Queens animation on
the Companion Website
■
Search WWH ::
Custom Search