Chapter 3, Problem 5E

Explanation of Solution

Formulation for a planar map:

• The formulation puts one queen per column, with a new queen placed only in a square that is not attacked by any other queen.
• To simplify matters, we’ll first consider the n–rooks problem where the first rook can be placed in any square in column 1 (n choices), the second in any square in column 2 except the same row that as the rook in column 1 (n−1 choices), and so on.
• This gives n! elements of the search space.
• For n queens, notice that a queen attacks at most three squares in any given column, so in column 2 there are at least (n − 3) choices, in column at least (n − 6) choices, and so on.
• Thus the state space size $S\ge n\cdot \left(n-3\right)\cdot \left(n-6\right)\mathrm{...}$ Hence we have:

$\begin{array}{c}{S}^3\ge n\cdot n\cdot n\cdot \left(n-3\right)\cdot \left(n-3\right)\cdot \left(n-6\right)\cdot \left(n-6\right)\mathrm{}\end{array}$