While reading Artificial Intelligence a Modern Approach I came across the following formulation for the 8-queen problem:
- Initial state: No queens on the board.
- States: Arrangements of n queens (0 <= n <= 8), one per column in the leftmost n columns, with no queen attacking another are states.
- Successor function: Add a queen to any square in the leftmost empty colum such that it is not attacked by any other queen.
I have been trying to find some pattern that would allow me to sort out the number of states for each n given the constraints above but I have not been succeeded for n > 2.
- n=1 => 8 states
- n=2 => 42 states
Even though I could generate all the possible combinations for each n and then filter out all those that do not represent a valid state, I would rather not go that way because it would be really time and space consuming for n, say, greater or equal than 10.
To sum up, is there any sort of formula to find the number of states given n and at the same time taking into account the following constrains?