Consider the n-queens problem using the
“efficient” incremental formulation given on page nqueens-page. Explain why the state
space has at least 3√n! states and estimate the largest n
for which exhaustive exploration is feasible. (Hint:
Derive a lower bound on the branching factor by considering the maximum
number of squares that a queen can attack in any column.)
Consider the n-queens problem using the “efficient” incremental formulation given on page nqueens-page. Explain why the state space has at least 3√n! states and estimate the largest n for which exhaustive exploration is feasible. (Hint: Derive a lower bound on the branching factor by considering the maximum number of squares that a queen can attack in any column.)