Eight Queens Puzzle: Tree Algorithm

• Download EightQueens.zip - 8.8 KB

Introduction

"The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.

The problem can be quite computationally expensive as there are 4,426,165,368 possible arrangements of eight queens on an 8×8 board, but only 92 solutions." (Wikipedia)

Can we solve this problem (for eight and n queens) with a simple tree algorithm?

And if yes, what does it look like in C#?

Background

There are several articles (e.g. here, here, here, here, here, here, and here) on Code Project addressing this topic. But for me none of them was really clear and simple. And I also think that e.g. this "sample program" is very out of date. So I try to explain an effective tree algorithm and its implementation in C# here - step by step.

Tree Algorithm

We start with an empty chessboard and try to place the first queen on any field in the first line. We have got eight possible fields for this (a8 to h8), but when we choose one option we have less possible fields for the second queen in the second line, and even less again in the third line:

So let us choose e.g. c8 concerning the first queen in the first line (which is line 8 on a regular chessboard).

Afterwards we have got five possibilities for the second queen on a field in the second line: a7, e7, f7, g7, and h7.

Let us choose g7 here.

Now we have got two possibilities for the third queen on a field in the third line: b6 and d6.

And so on.

In this example we find a valid solution: the queens from line 8 to 1 are in rows c, g, b, h, f, d, a, and e.

So our decision path from the first to the last line can be shown as a decision tree containing the possible nodes and the chosen nodes: 

This does not look too complicated. The number of options seems to decrease line by line very quickly! So our approach looks rather promising, doesn't it? If we are lucky there will be much less posibilites here than 4.4 billion.

So lets us code this algorithm and run it for all tree paths - and then let us analyse the results:

C# Implementation

We start with a very simple class for a Position. It only has a line, a row and a parent. And of course it provides a recursive method for walking through the tree (WalkThroughTree):

public class Position
{
    private int line, row;
    private Position parent;

    public Position(int Line, int Row, Position Parent)
    {
        line = Line;
        row = Row;
        parent = Parent;
    }

    public void WalkThroughTree()
    {
        if (line == NumberOfQueens) // last line (=number of queens) reached: solution
        {
            PrintSolution(this); // print solution
            return;
        }
        for (var r = 0; r < NumberOfQueens; r++) // try all rows in next line
        {
            // check threats for all queens in previous lines

            // ...

            if (queenAbove.line == 0) // no threat found
                new Position(line + 1, r, this).WalkThroughTree(); // put queen on next line
        }
    }
}

Basically that's it. We can start with our (dummy) root node - in line 0 and no valid row on the chessboard - and generate the total tree:

new Position(0, Int32.MinValue, null).WalkThroughTree();

Of course, whenever we try to put a new queen on a field in the next line, we have to check whether the possible field is save, before we really put this queen on the new field:

In this example a6 is not safe, b6 is safe, and c6 is not safe. We check the threats by simply comparing the colum of the next queen with the column of each previous queen. If the column numbers are equal, we found a vertical threat (e.g. c8 threatens c6), and if the difference between them is equal to the difference between their line numbers, we found a diagonal threat (e.g. c8 threatens a6). So for each check of threats we only have to do very few comparisons in our WalkThroughTree from above:

for (var r = 0; r < NumberOfQueens; r++) // try all rows in next line
{
    // check threats for all queens in previous lines
    var queenAbove = this;
    while (queenAbove.row >= 0 && r != queenAbove.row // vertical threat?
           && r - queenAbove.row != line + 1 - queenAbove.line // diagonal threat left?
           && queenAbove.row - r != line + 1 - queenAbove.line) // diagonal threat right?
        queenAbove = queenAbove.parent; // repeat check for all queens in previous lines
    if (queenAbove.line == 0) // no threat found
        new Position(line + 1, r, this).WalkThroughTree(); // put queen on next line
}

Besides, we may find solutions with less than eight queens. Therefore we only print the solution (PrintSolution), if we really have enough queens identified in the attempt - see above: "if (line == NumberOfQueens)".

private static void PrintSolution(Position Node)
{
    NumberOfSolutions++;
    while (Node.row >= 0)
    {
        Console.Write(((char)('a' + Node.row)).ToString());
        Node = Node.parent;
    }
    Console.WriteLine();
}

By this method PrintSolution we simply print all columns of each successful decision path to the console, one solution after the other. The results look like this:

Here you see our sample solution from above highlighted as one result in our list of solutions (the queens from line 8 to 1 are in rows c, g, b, h, f, d, a, and e).

When we also add some counters, we can see: there are 15,720 attempts, there are (only) 2,056 nodes in our total tree (excluding the dummy root), and there are really 92 solutions:

My old and slow computer needs 3 milliseconds for calculating all these solutions. And the numbers correspond with the theory: "The backtracking depth-first search program, a slight improvement on the permutation method, constructs the search tree by considering one row of the board at a time, eliminating most nonsolution board positions at a very early stage in their construction. Because it rejects rook and diagonal attacks even on incomplete boards, it examines only 15,720 possible queen placements" (Wikipedia).

N Queens

We can also change the number of squares and queens easily:

public static int NumberOfQueens = 8; // n queens

For 7 queens I get 40 solutions in 2 milliseconds.

For 12 queens I get 14,200 solutions in 400 milliseconds.

For 13 queens I get 73,712 solutions in 2400 milliseconds.

For 14 queens I get 365,596 solutions in 9 seconds (with 27,358,552 nodes in the tree and 377,901,398 attempts of positioning a queen on a save field).

We can compare these results with Wikipedia again. They fit.

Points of Interest

At the beginning I also had the children stored in the node. But finally it turned out, that this kind of walkthrough based on this simple recursion does not need stored children.

I also found it interesting, that C# is able to process around 27 million tree nodes and nearly 378 million tree-based comparisons so fast (e.g. in the case of 14 queens). The human brain is fast, too. But it usually operates with around 50 nodes (7 times 7).

Besides I translated the whole program to C++ and Java, too. Then I compared the results concerning performance:

C++ (CLR) - 8,723 milliseconds:

Java - 8,788 milliseconds:

C# - 8,618 milliseconds:

I also compared more criteria:

For me this is an astonishing outcome: C# beats them all.

History

11^th of August, 2014 - Published.

12^th of August, 2014 - Performance and explanations enhanced, source code streamlined.

13^th of August 2014 - Comparison with C++ added.