December 14, 2013

This Week's Coding Practice - The N Queens Puzzle

On top of being a challenge in itself, the game of Chess has been fertile ground for researchers for a very long time. A famous example of a chess-related research problem is the Eight Queens Puzzle - how can you place 8 queens on a regular 8x8 chessboard such that none of the queens are under attack from any of the other queens?

Помню: всех главнее - королева,
Ходит взад-вперед и вправо-влево.
В. Высоцкий, “Честь шахматной короны II. Игра.”

For those unfamiliar with chess, the Queen is the most powerful piece in the game, since it can move horizontally, vertically and diagonally. This property allows the queen to cover a lot of space on the board. It’s rare to see more than two queens on the board at the same time - both white & black players start the game with a queen each, but pawns can be promoted to queens once they reach the end of the board - so seeing 8 queens on one board is a real luxury.

There are several ways to solve the Eight Queens Puzzle. The easiest way is to set up a brute-force search that cycles through all potential queen arrangements and eliminates those where a queen attacks another queen. Unfortunately, the number of all potential arrangements is prohibitively large. This doesn’t rule out the brute-force approach, however - you just need to be a little smarter in applying it.

The first thing to notice is that each queen must be on a separate rank (row), file (column) and diagonal. Therefore, if you start with an empty board and place queens onto it one by one, the number of unattacked squares will decrease with additional queen. This is a very useful property for a search problem, at it restricts the number of options and reduces the time needed to complete the search.

The second thing to notice is that the queens are identical, that is, swapping any of the queens with each other achieves nothing. This further reduces the number of options.

With that in mind, the search algorithm tackles the problem by performing a depth-first search, one row at a time. If there is an available square on the current row, the algorithm puts a queen there and moves on to the next row. If there are no more available squares, then the algorithm backtracks - goes back to moving one of the queens on the higher rows. Once the algorithm reaches the bottom of the board (places a queen on the bottom row), it has found a solution to the problem. At this stage, it again backtracks and looks for other solutions.

This is what the algorithm looks like in action. You can go through it in individual steps, or just have it run until in finds a solution (click here for a full-screen result).

Of course, there are many solutions. If you don’t have the patience to watch the algorithm find the solutions one by one, and just want to see the solutions, then here they are (click here for a full-screen result):

An extension to the Eight Queens Problem is the N Queens Problem, in which board is still square but can be of arbitrary size. Solutions exist for all natural N greater than 3.