The N queens chess problem (the generalized version of the 8 queens problem/puzzle) is defined as follows:
On a chessboard with N by N squares, place N queens so that they cannot attack each other.
As a first step, it's important to understand the ways a queen can move in chess, which is luckily straightforward: they can move in a straight line up, down, left, right, and diagonally, as demonstrated in the following diagram:
With this known, the rest is very similar to the preceding knapsack problem, but with a few more possibilities caused by various placement options. There are a number of strategies to tackle that:
- Each cell individually, which would result in a large number of recursive calls quickly
- Each row (or column) individually, and iterate over the cells within
The latter is clearly the preferred method, since a 10 by 10 board results in 100 recursive calls for each individual cell (including allocations, for example) and thereby quickly results in a stack overflow...
