+2 votes
in Artificial Intelligence by
Consider the n-queens problem using the “efficient” incremental formulation given on page 72. 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.)

1 Answer

+1 vote
selected by (user.guest)
Best answer

n -queens problem using the “efficient” incremental formulation

Any arrangement of n queens image  with one per column, in the left most n columns, and with no queen attacking another are states.

Add a queen to any square in the left-most empty column, such that it is not attacked by another queen.

The state space size is at least image and the largest n for exhaustive exploration is feasible.


From this diagram, a lower bound on the size of the state space is formulation on this n-queens problem.

In each column contains a queen, and queens are filled in neighboring columns in locations that are not attacked by previous queens

The first column can be placed in any square in column nd the second column 2, except the same row that has the place in column 1. ‘n!’ element of the search space is available.

The number of valid states may fit in each queen from the previous columns and attacks exactly 3 squares in this lower bound.

These squares have been attacked by a previous queen in a real situation.

Here there are at least (n-6) squares that the 3rd queen can take on and n-choices for the first queen, (n-3) choices for the second, (n-6) the third and so on.

So if S is the size of the state space, then


This becomes infeasible.

Related questions

+1 vote
1 answer
Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that