Recently I downloaded and played the excellent game “Human Resource Machine” (Human Resource Machine) – this one must have passed me by without me noticing it as it was released in 2015. In this game you instruct a character to solve various problems using an assembler type language. It starts off easy and then goes through some problems relating to computer science such as sorts and data structures. I really enjoyed this game, and it made me remember a problem discussed a long time ago in a lecture at university. The 8 Queens Problem.
This problem is a great introduction to various topics, but mainly backtracking.
What is the problem?
Imagine a standard 8 x 8 chess board
The idea is to find a way of placing 8 queens onto the board without them being in a position where they could take each other. (For those that don’t know chess the queen can move any number of squares in any direction).
Initially this seems simple – the first couple of queens you might place will not cause any issues – but as you add more it becomes complex. Consider the following.
At this point all the queens are safe from attaching each other, however no square in column H is free from attack.
So is there a way we can find all the combinations where this is possible programmatically?
Solutions
One way of solving this problem is with backtracking.
What is Backtracking?
Backtracking is an approach to solve problems recursively by trying to build a solution incrementally one piece at a time, if a solution fails to meet the constraints at a point in time we revert to the previous state and reposition, this approach can be represented in the diagram below.
This approach can be written in pseudo code as follows.
Backtrack (s)
If s is not a solution
Return false
Else if it is a new solution
Add to list
Backtrack (expand s)
Backtracking Example – 4 Queens
to consider how this works with our problem – lets reduce the scale somewhat and consider a 4*4 Chess board.
Lets start by putting the initial queen in row 3 column A;
If we work row by row the next available place the queen is safe is C3
However, at this point we have a problem – row 2 has no safe squares.
We have a failure – and need to backtrack.
let’s reposition the first queen to its next position to the right (B4);
From this staring position a solution is possible and all the positions are forced (going row by row). The only safe position on Row 3 is D3
and from here on there are only 2 safe options left C1 for column 3 and D3 for column 4.
Coding the algorithm
I have coded a small console app in C# to show how this works in code. The code is located at the following GitHub repository: 8QueensProblem.
The output of this program is a representation of a chessboard written to the console window. Interestingly there is a character set for chess pieces in unicode and character u2655 represents a queen (I did not know this prior to writing this blog!).
An example of the output produced by the program can be seen below;
A count of solutions is recorded in the code and as shown there are 92 distinct outcomes on an 8*8 board (although some of these are rotated versions of another one)
Optimisations
Like all problems there are many ways in which this could be solved. Backtracking is faster than a simple brute force approach, but there are faster methods of doing this. I recommend the Wikipedia page on this problem for if you have an interest in this – it also has a good animation showing the backtracking approach (Eight queens puzzle – Wikipedia)