n-Queens
The table shows the size of the state space for dierent ways of representing an n  n chess board with n queens placed on it.
A. n queens in dierent squares, with no other restrictions, gives

n2
n

possibilities.
B. Restricting to exactly one queen per row, but no restrictions on columns or diagonals, gives nn possibilities.
C. Restricting to exactly one queen per row and exactly one per column, but no restrictions on diagonals, gives permutations, so
there are n! possibilities.
D. A \solution" is n queens positioned so that no two are in the same row, column, or diagonal.
E{F. The algorithm shown on the back of the page (based on the backtracking algorithm in Chapter 5.1{5.2), constructs space B
described above one row at a time, pruning when the rows already constructed are not promising. The number of (E) promising
and (F) non-promising nodes are as indicated. An upper bound on E + F is to do a depth-rst search without pruning, which
explores n0 + n1 + 
 
 
+nn = (nn+1 − 1)=(n − 1) nodes (nk nodes at depths k = 0; : : : ; n).
n A.
􀀀n2
n


B. nn C. n! D. # solutions E. # promising F. # not promising
1 1 1 1 1 2 0
2 6 4 2 0 3 4
3 84 27 6 0 6 13
4 1820 256 24 2 17 44
5 53130 3125 120 10 54 167
6 1947792 46656 720 4 153 742
7 85900584 823543 5040 40 552 3033
8 4426165368 16777216 40320 92 2057 13664
9 260887834350 387420489 362880 352 8394 63985
10 17310309456440 10000000000 3628800 724 35539 312612
11 1276749965026536 285311670611 39916800 2680 166926 1639781
12 103619293824707388 8916100448256 479001600 14200 856189 9247680