Hands-On Data Structures and Algorithms with Rust

N queens

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, ...