Igor's Website - Articles - Recursion tutorial, N-queens problem

Science, stories, art and music.

Science / Computer science articles.

Recursion tutorial: N-queens in C

Recursion is a method of solving a problem by means of solving its sub problems. It usually implies usage of self-calling (recursive) functions in some programming language. Another concept which could also be described as "solving a problem by dividing it into sub problems and solving them first" is called dynamic programming. One does not exclude the other, as dynamic programming often requires recursion. Recursion is merely means of achieving some goal by utilizing functions which make calls to themselves. One could say that "to understand recursion, one must first understand recursion".

I will assume you know the basics of recursion, and use the term accordingly.

Here I will give a short analysis of a simple recursive solution to the N-queens problem. The N-queens problem is the problem of placing N chess queens on an NxN chessboard so that no two queens attack each other. An interesting instance of this problem is the eight queens puzzle, which is an instance of the N-queens problem, for N=8.

For solving this we employ a version of recursive backtracking. From Wikipedia:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, which incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

We declare an array of integers (note: array, not a matrix) where we will store vertical positions of a queen in a single column. That is, array[i] represents the i-th column. Obviously, two queens cannot be in a same column, which allows for this approach.

Generally speaking, recursion may be the way of creating multiple for loops to solve a problem. In a specific instance of the N-queens problem, we could use N for loops to solve the problem efficiently, however when the generalization of a problem needs to be solved, we need a mechanism which would behave in a similar manner as N nested for loops.

If we place a for loop in some function f() and then call the same function in that for loop, we would effectively have created an infinite nested for loop. Of course, in practice, this is impossible and probably useless. But if there is a limit to the nesting of the for loops (in our problem, this would be N) we can achieve N nested for loops with a recursive function.

For each column of the chess table we will need one for loop. We can model this using the function Queen(short index), where calling a function with a parameter index is, in fact, the index-th for loop. In each loop we need to check whether placing a queen at a specified position is valid. For this, we implement the function Check(short index) which checks whether there is a queen before the index-th column which is in the same row, or on the diagonal. Obviously, checking for the queen on the same row is trivial, as it is only necessary to check whether there is a same value of array before the index-th column as in the array[index].

bool Check(short ind)
{
    for (short i=0; i<ind; i++)
        if ((arr[i]==arr[ind])||(arr[i]==arr[ind]+(ind-i))||(arr[i]==arr[ind]-(ind-i)))
             return false;
        return true;
}

Checking for a queen on a diagonal requires a bit more thought. Let’s assume we have a queen on position y of the column x, and we want to check if the column x-2 has a queen in a position such that the two queens do not attack each other. The value of the array[x-2] must be different from array[x]+2 and array[x]-2. This can be generalized for the (x-i)-th column. Thus the function Check(short index) can be written. If no two queens attack each other, the Check(short index) returns true.

void Queen(short index) 
{ 
    if (unsolved&&(index<n)) 
    { 
        for (short i=0;i<n;i++)
        {
            if (!unsolved)
                break; 
            arr[index]=i; 
            if (Check(index))
                Queen(index+1);
        }
     }
     else
     {
         unsolved=false;
         for (short i=0; i<n;i++)
             sol[i]=arr[i]; 
     }
}

Stopping condition of the function Queen(short index) is met when index reaches n or when Check(short index) returns false. For each iteration in function Check(short index) we call that same function with a parameter index+1, which is the next for loop. When the stopping condition is met, the board is printed, and variable unsolved set to false.

N-queens – mathematical solution

The N-queens problem has a much faster solution. A solution can be obtained using a simple algorithm:

This heuristic solves N queens for any N ≥ 4. It forms the list of numbers for vertical positions of queens with horizontal position simply increasing. Note that this notation is different from the one given in the above solution.

  • If the remainder from dividing N by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers less than N
  • Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - 1,3,5,7)
  • If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i.e. 3,1,7,5)
  • If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (i.e. 4,6,8,2 - 5,7,9,1,3)
  • Append odd list to the even list and place queens in the rows given by these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5)

This solution is implemented in the included code. This algorithm is presented in Pascal on the Wikipedia page.

The code for the solution can be found here.

10.12.2012

Google Code Prettify

I use Google Prettify to format the source code in my articles. If the code is displaying in one line, you can try opening the page in a different browser.

Request software design

If you wish to have a specific application designed, contact me at software@igorsevo.com. If you want to know more about what I do, check out my home page and Science page.

Support this site

Suggest an article

You can suggest an article or ask a question on the Questions page.

Social