This would eliminate many combinations, but would still allow 88 = 16,777,216 possible solutions (x 8 = 134,217,728 total queen placements)

If we further note that all queens must be in different rows, we reduce the possibilities more

Now the queen in the first column can be in any of the 8 rows, but the queen in the second column can only be in 7 rows, etc.

This reduces the possible solutions to 8! = 40320 (x 8 = 322,560 individual queen placements)

We can implement this in a recursive way

However, note that we can prune a lot of possibilities from even this solution execution tree by realizing early that some placements cannot lead to a solution

Using this approach we come up with the solution as shown in 8-Queens handout

JRQueens.java

Idea of solution:

Each recursive call attempts to place a queen in a specific column

A loop is used, since there are 8 squares in the column

For a given call, the state of the board from previous placements is known (i.e. where are the other queens?)

If a placement within the column does not lead to a solution, the queen is removed and moved "down" the column

8 Queens Problem

When all rows in a column have been tried, the call terminates and backtracks to the previous call (in the previous column)

If a queen cannot be placed into column i, do not even try to place one onto column i+1 – rather, backtrack to column i-1 and move the queen that had been placed there