Consider the n-queens problem using the “efficient” incremental formulation give
ID: 3792175 • Letter: C
Question
Consider the n-queens problem using the “efficient” incremental formulation given below. Explain why the state space has at least 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.)
NIV Figure 3.5 Almost a solution to the 8-queens problem. (Solution is left as an exercise.) Although efficient special-purpose algorithms exist for this problem and for the whole n-queens family, it remains a useful test problem for search algorithms. There are two main kinds of fommulation. An incremental formulation involves operators that augment the state description, starting with an empty state: for the 8-queens problem, this means that each action adds a queen to the state. A complete-state formulation starts with all 8 queens on the board and moves them around. In either case, the path cost is of no interest because only the final state counts. The first incremental formulation one might try is the following States: Any arrangement of 0 to 8 queens on the board is a state. Initial state: No queens on the board. Actions: Add a queen to any empty square. Transition model: Returns the board with a queen added to the specified square. Goal test: 8 queens are on the board, none attacked. In this formulation, we have 64-63 R 1.8 x 10 14 sequences to investigate. A possible better formulation would prohibit placing a queen in any square that is already attacked: States: All possible arrangements of n queens (0 S n S 8), one per column in the leftmost n columns, with no queen attacking another. Actions: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen. This formulation reduces the8-queens state space from 1.8 x 10 4 to just 2,057, and solutions are easy to find. On the other hand, for 100 queens the reduction is from roughly 10 states to about 10 states (Exercise 3.5-a big improvement, but not enough to make the problem tractable. Section 4.1 describes the complete-state formulation, and Chapter 6 gives a simple algorithm that solves even the million-queens problem with ease.Explanation / Answer
We only put one queen per column and a new queen in squares where it isn’t attacked by any other queen per say. If we took n queens, we can see that it can go into max number of 3 squares in each column so there are n-3 choices and n-6 choices in column. The state space will then be n*n-3*n-6. This should be 3 n!.