The N Queens Problem

The N queens problem is a classic problem. It can be stated as follows:

Place N queens on an NxN chessboard such that no two queens threaten each other. So, no two queens lie on the same row, column, or diagonal.

The reason that the N queens problem is a classic problem is that it introduces various algorithmic techniques. Here, I applied backtracking.

A solution S to the problem is a list of N integers. S[i] is the row on which the queen on column i lies.

Because a solution is a list of N integers, it consists of N parts. To find a solution, you can try all of the possibilities for the first part, then all of the possibilities for the second part, and so on. This is an exhaustive search, because you search for solutions by trying all possibilities.

Let's go over this in some more detail. For concreteness, let N = 8.

On your first move, you have 64 squares that you can place a queen on. Because you occupy a square on your first move, you have 63 available squares on your second move. And so on. On your eighth and final move, you have 57 available squares. So, there are 64 * 63 * ... * 57 = 178,462,990,000,000 possible configurations of the board. To solve the problem, you can generate all 178,462,990,000,000 possible configurations of the board and test each configuration for validity. But it is clear that this approach is inefficient.

So, it's a good thing that you can approach the problem in a better way. Remember that you have to place all eight queens on the board, that there are eight columns, and that no two queens can lie on the same column. So, each column must have one and only one queen on it. So, on your first move, you really only have eight squares to choose from. Given the first column, you pick one of the eight available rows to place the queen on.

Because no two queens can lie on the same row, you cannot place the next queen on the row that you placed the first queen on. So, you only have seven squares to choose from on your second move. Likewise, you only have six squares to choose from on your third move. And, all in all, you only have 8 * 7 * 6 * ... * 1 = 8! = 40,320 possible moves. So, if we take this approach, then we only have to examine 40,320 possible configurations of the board. That's a huge reduction from 178,462,990,000,000 possible configurations.

And we can do even better than this. Remember that no two queens can lie on the same diagonal. So, when you place a queen on a square, you don't just eliminate as possibilities all the squares on its column and row. You eliminate all the squares on its diagonal, too. So, you can consider even fewer possibilities than 8! possibilities.

The program places a queen in the first column. Then it places a queen on an available square in the second column. And so on. If the current column does not have any available squares, then it backtracks to the previous column and tries to move the queen in that column to another square.

My solution to the N queens problem is up at my GitHub.