Programming Problem: Solve the Eight-Queen Problem with Recursion
This is one of the series of articles on programming problems. Usually these problems are small and interesting and some arise from simplification of larger problems to make the solution easier to understand and implement.
The problem we are going to solve in this article is the Eight queen puzzle. Given an 8x8 chess board, we need to place eight queens on the board such that they don't attack one another. Our purpose here is to illustrate how to solve this problem with recursion and please keep in mind that fast performance is not our goal here because recursion will become slow when we extend this to a larger NxN board.
We have two prior articles on using recursion to solve some programming problems: Find all the root-to-leaf paths of a given tree and Reverse singly-linked list. We also show how recursion works when we implement a simple Checkers game study tool. However so far they only deal with problem of size-N. The N-queen problem we face now seems to be of problem size NxN. How shall we approach this problem with recursion?
On our initial thought, we may assume that we have the solutions for the (N-1) x (N-1) board so that the first N-1 queens do not attack one another. However, this recursion will not work because then the N-th queen has to be placed at (N, N) which is not always the case. Then we will not be able to find all the solutions. For example, when N = 4, there is one solution below:
-Q-- ---Q Q--- --Q-
It is clear that none of the queens are in any of the four corners. In fact, another fundamental flaw with this approach is that for a N x N solution, the first N-1 queens are not necessarily placed in the N-1 x N-1 board. We have to try it another way.
We can assume that we have the solution for putting the first M-1 queens in the (M-1) x N board so they don't attack one another. Here M can be 2 to N. In fact, any solution for N x N must satisfy that the first M-1 queens in the first M-1 rows cannot attack one another and that they have guarded M-1 columns out of the N columns.
This looks very promising. Now we can check how we can put the M-th queen on the M-th row to get the solutions for the M x N board. This can be done by putting the queen at the columns that are not under attack by any of the other M-1 queens. We also need to check that it is not attacked diagonally by the other M-1 queens. When all the conditions are met, we find one solution.
The base case is 1 x N which is simple and has N solutions. That is, the first queen can be put at any of the columns of the first row. Since we know how to find the solutions for M x N given (M-1) x N, we can get the solution for N x N after N-1 iterations.
Now we have to decide how to encode the solutions for M x N.
Because it is much easier to think in terms of really high-level
programming languages such as Perl, we can consider the return
value of the recursive function resolve_queue_helper(M, N)
to be a reference to a list of list references which encode the
row-ordered columns.
For example, suppose resolve_queue_helper(2, 8) has the following solutions,
1 2 3 4 5 6 7 8 1 Q - - - - - - - 2 - - Q - - - - -
1 2 3 4 5 6 7 8 1 Q - - - - - - - 2 - - - Q - - - -
Then we can encode it as [ [1, 3], [1, 4] ].
The solution for the base case resolve_queue_helper(1, N) is
just [ [1], [2], ... , [N] ].
Now suppose we have the solution for resolve_queue_helper(M-1, N), then the check for the solution of resolve_queue_helper(M, N) works like this
- For each solution for problem (M-1, N), find the columns that are not covered yet.
- For each of the columns, put the M-th queen at it and then check this queen can attack any of the other queens. We only need to check the diagonals.
- If it cannot attack any, then this is one of the solutions and we can add it to the list.
We need to implement a few helper functions along the way but they are simple and straightforward.
You can download the complete Perl script that solves the N queen problem using recursion and study it yourself.
Once we get the Perl script working, it is actually very trivial to implement it in C++ with the standard template library (STL) and the boost library. We can use a vector of integers to record one solution and then a vector of such solutions to record all the solutions.
You can also download the complete C++ program that solves the N queen problem using recursion and study it yourself.