This file contains the exercises, hints, and solutions for Chapter 12 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 12.1
1. a. Continue the backtracking search for a solution to the four-queens
problem, which was started in this section, to find the second solution to
2. a. Which is the last solution to the five-queens problem found by the
backtracking algorithm?
3. a. Implement the backtracking algorithm for the -queens problem in the
language of your choice. Run your program for a sample of values to
4. IDesign a linear-time algorithm that findsasolutiontothe-queens
problem for any ≥4
5. Apply backtracking to the problem of finding a Hamiltonian circuit in the
1
8. a. Apply backtracking to solve the following instance of the subset-sum
problem: ={13,45}and =11
10. Write a program implementing a backtracking algorithm for
11. Puzzle pegs This puzzle-like game is played on a board with 15 small
holes arranged in an equilateral triangle. In an initial position, all but
one of the holes are occupied by pegs, as in the example shown below. A
legal move is a jump of a peg over its immediate neighbor into an empty
square opposite; the jump removes the jumped-over neighbor from the
board.
2
Hints to Exercises 12.1
1. a. Resume the algorithm by backtracking from the first solution’s leaf.
b. How can you get the second solution from the first one by exploit-
ing a symmetry of the board?
To make your comparison with an exhaustive-search algorithm easier, you
may consider the version that finds all the solutions to the problem with-
out taking advantage of the symmetries of the board. Also note that an
exhaustive-search algorithm can try either all placements of queens on
distinct squares of the ×board, or only placements of the queens in
different rows, or only placements in different rows and different columns.
b. Although it is interesting to see how accurate such an estimate is for a
single random path, you would want to compute the average of several of
them to get a reasonably accurate estimate of the tree size.
7. This application of backtracking is quite straightforward.
8. a. Another instance of this problem is solved in the section.
b. Some of the nodes will be deemed promising when, in fact, they are
not.
3
1. a. The second solution reached by the backtracking algorithm is
1234
b. The second solution can be found by reflection of the first solution with
respect to the vertical line through the middle of the board:
2. a. The last solution to the 5-queens puzzle found by backtracking last is
1234
1
2
3
Q
Q
5
Q
4
1234
1
2
Q
5
Q
1234
1
2
Q
5
Q
middle column is
1234
1
2
Q
5
Q
1234
1
2
Q
5
Q
The solution obtained using the board’s symmetry with respect to its main
south-west—north-east diagonal is
1234
1
5
Q
1234
1
5
Q
3. For a discussion of efficient implementations of the backtracking algorithm
4. The solution for =4obtained by backtracking in the text (see Figure
12.2) suggests the following structure of solutions for other even ’s. For
the first 2rows, place the queens in columns 2, 4, …, 2; for the last
2rows, place the queens in columns 1, 3, …, −1Indeed, this works
not only for any =4+6 but also for any =6. Moreover, since none
of these solutions places a queen on the main diagonal, the solution can be
extended to yield a solution for the next value of by just adding a queen
in the last column of the last row (see the figures below for examples).
Solutions to the -queens problems for (a) =4;(b) =6;(c) =7
Unfortunately, this does not work for =8+6 Although it is possible to
place queens on such boards as it was done above and then rearrange them, it
6
last column of the last row of the larger board.
Solutions to the -queens problems for (d) =8and (e) =9
Thus we have the following algorithm that generates column numbers for placing
3queens in consecutive rows of an ×board.
Compute the remainder of division by 6.
Case 1 (is neither 2 nor 3): Write a list of the consecutive even numbers
Note: The -queens problem is one of the most well-known problems in
recreational mathematics, which has attracted the attention of mathematicians
since the middle of the 19th century. The search for efficient algorithms for solv-
Surprisingly, this alternative has been all but ignored by computer scientists
until B. Bernhardsson alerted the community of its existence in “Explicit so-
lutions to the n-queens problem for all n,” SIGART Bulletin, vol. 2, issue 2,
(April 1991), p. 7.
5. Finding a Hamiltonian circuit in the graph
a b
by backtracking yields the following state-space tree:
d
b
a
e
0
1
2
11
6. Here are the graph and a state-space tree for solving the 3-coloring problem
8
for it using backtracking
a, 1
b,1 b, 2
X
7. Here is a state-space tree for generating all permutations of {1234}
by backtracking:
8. a. Here is a state-space tree for the given instance of the subset-sum
problem: ={13,45}and =11:
0
wit h 1
w/ o 1
9. Eliminate else from the template’s pseudocode.
10
Exercises 12.2
1. What data structure would you use to keep track of live nodes in a best-
first branch-and-bound algorithm?
2. Solve the same instance of the assignment problem as the one solved in the
4. Write a program for solving the assignment problem by the branch-and-
bound algorithm. Experiment with your program to determine the av-
erage size of the cost matrices for which the problem is solved in a given
amount of time, say, 1 minute on your computer.
5. Solve the following instance of the knapsack problem by the branch-and-
bound algorithm:
item weight value
1 10 $100
7. Write a program to solve the knapsack problem with the branch-and-
bound algorithm.
8. a. Prove the validity of the lower bound given by formula (12.2) for in-
stances of the traveling salesman problem with integer symmetric matrices
11
problem for the following graph:
a
b
2
10. As a research project, write a report on how state-space trees are used
for programming such games as chess, checkers, and tic-tac-toe. The two
12
Hints to Exercises 12.2
1. What operations does a best-first branch-and-bound algorithm perform
on the live nodes of its state-space tree?
2. Use the smallest numbers selected from the columns of the cost matrix to
3. a. Your answer should be an ×matrix with a simple structure making
the algorithm work the fastest.
b. Sketch the structure of the state-space tree for your answer to part
(a).
4. n/a
Solutions to Exercises 12.2
1. The heap and min-heap for maximization and minimization problems,
respectively.
2. The instance discussed in the section is specified by the matrix
job 1 job 2 job 3 job 4
9278person
Here is the state-space tree in question:
Start
lb = 12
0
3. a. An ×matrix whose elements are all the same is one such example.
b. In the best case, the state-space tree will have just one node devel-
oped on each of its levels. Accordingly, the total number of nodes will be
4. n/a
5. The instance in question is specified by the following table, in which the
items are listed in nonincreasing order of their value-to-weight ratios:
item weight value
w = 10, v = 100
1
w = 0, v = 0
ub = 160
0
w = 0, v = 0
2
with 1 w/o 1
w = 19 w = 15, v = 119
ub = 119
12
11
X
not feasible
optimal solution
{2,3}
15
6. a. We assume that the items are sorted in nonincreasing order of their
efficiencies: 11≥··· ≥and, hence, new items are added in this
order. Consider a subset ={item 1…, item }represented by a node
in a branch-and-bound tree; the total weight and value of the items in
b. The instance is specified by the following data
item weight value
1 10 $100
2 7 $63
3 8 $56
4 4 $12
=16
1
w = 0, v = 0
Ub = 154
0
2
with 1 w/o 1
16
7. n/a
8. a. Any Hamiltonian circuit must have exactly two edges incident with
each vertex of the graph: one for leaving the vertex and the other for
entering it. The length of the edge leaving the th vertex, =12 is
given by some nondiagonal element [ ]in the th row of the distance
9. Without loss of generality, we’ll consider as the starting vertex and
17
ignore the tours in which is visited before .
a
0
a
b
2
10. n/a
18
Exercises 12.3
1. a. Apply the nearest-neighbor algorithm to the instance defined by the
distance matrix below. Start the algorithm at the first city, assuming
that the cities are numbered from 1 to 5.
2. a. Write a pseudocode for the nearest-neighbor algorithm. Assume that
its input is given by an ×distance matrix.
4. BProve that making a shortcut of the kind used by the twice-around-the-
tree algorithm cannot increase the tour’s length in an Euclidean graph.
7. Consider the greedy algorithm for the bin-packing problem, which is called
the first-fit (FF )algorithm: place each of the items in the order given
into the first bin the item fits in; when there are no such bins, place the
item in a new bin and add this bin to the end of the bin list.
19