The goal of the 8 – queens problem is to place eight queens on 4 chessboard such that no queen attacks any other.

[ A queen attacks any piece in the same row, column or diagonal ]

Figure (5) shows an attempted solution that fails: The queen in the right most column is attacked by the queen at the top left.

There are two main kinds of formulation:

1] Incremental formulation.

2] Complete-state formulation.

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 1st mental 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.

- Successor function: Add a queen to any empty.

- Goal test: 8 queens are on the board, one attacked a better formulation world prohibit placing a queen in any square that is already attacked:

- States: Arrangements of n queen $( n \leq h \leq 8)$, One per column, in the left most n columns, with no queen attacking another are states.

- Successor function: Add a queen to any squares in the left most empty column such as that it is not attacked by any other queen.

This formulation reduces the 8 – 9 queens state space from $3 \times 10^{14}$ to just 2,057 and solutions are easy to find.

On other hand, for 100 queens the initial formulation has roughly $10^{400}$ states whereas the improved formulation has about $10^{52}$ states. This is huge reduction, but the improved state space is still too big for the algo.

Figure (5) Almost a solution to the 8 - queens problem (Solution is left as an exercise.)