Click here to Skip to main content
15,170,602 members
Articles / Programming Languages / C#
Posted 11 Aug 2014


33 bookmarked

Eight Queens Puzzle: Tree Algorithm

Rate me:
Please Sign up or sign in to vote.
4.98/5 (20 votes)
11 Aug 2014CPOL5 min read
How to solve the "eight queens puzzle" with a simple tree algorithm.


"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#?

Image 1


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:

Image 2

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: 

Image 3

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
        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:

Image 4

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)
    while (Node.row >= 0)
        Console.Write(((char)('a' + Node.row)).ToString());
        Node = Node.parent;

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:

Image 5

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:

Image 6

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:

Image 7

Java - 8,788 milliseconds:

Image 8

C# - 8,618 milliseconds:

Image 9

I also compared more criteria:

Image 10

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


11th of August, 2014 - Published.

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

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


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

dietmar schoder
United Kingdom United Kingdom
generative artist:

Comments and Discussions

Questionwhat is the configuration of the computer used in testing this algorithm? Pin
abdo513-May-18 3:37
Memberabdo513-May-18 3:37 
A I tested the algorithm on my laptop put it take much time than recorded in the article.

lliseconds: 46175
Queens/Squares: 13
Attempts: 59,815,314
Nodes: 4,674,889
Solutions: 73,712

QuestionLink for c++ Pin
Member 1301462620-Mar-17 4:11
MemberMember 1301462620-Mar-17 4:11 
Questionconvert to C. great request Pin
Marta Piela-Bendkowska9-Jun-16 4:38
MemberMarta Piela-Bendkowska9-Jun-16 4:38 
AnswerRe: convert to C. great request Pin
dietmar paul schoder9-Jun-16 5:00
professionaldietmar paul schoder9-Jun-16 5:00 
QuestionVery nice, but is it more efficient than the "standard" iterative solution? Pin
Daniel Pfeffer23-Dec-15 1:11
professionalDaniel Pfeffer23-Dec-15 1:11 
AnswerRe: Very nice, but is it more efficient than the "standard" iterative solution? Pin
dietmar paul schoder23-Dec-15 10:08
professionaldietmar paul schoder23-Dec-15 10:08 
GeneralRe: Very nice, but is it more efficient than the "standard" iterative solution? Pin
Daniel Pfeffer24-Dec-15 1:45
professionalDaniel Pfeffer24-Dec-15 1:45 
GeneralRe: Very nice, but is it more efficient than the "standard" iterative solution? Pin
dietmar paul schoder24-Dec-15 10:26
professionaldietmar paul schoder24-Dec-15 10:26 
QuestionNaming Pin
Mr.PoorEnglish5-Sep-15 2:37
MemberMr.PoorEnglish5-Sep-15 2:37 
AnswerRe: Naming Pin
dietmar schoder5-Sep-15 2:54
Memberdietmar schoder5-Sep-15 2:54 
GeneralRe: Naming Pin
Mr.PoorEnglish5-Sep-15 20:43
MemberMr.PoorEnglish5-Sep-15 20:43 
GeneralRe: Naming Pin
dietmar schoder6-Sep-15 8:06
Memberdietmar schoder6-Sep-15 8:06 
GeneralRe: Naming Pin
Mr.PoorEnglish9-Sep-15 7:07
MemberMr.PoorEnglish9-Sep-15 7:07 
GeneralRe: Naming Pin
dietmar schoder9-Sep-15 8:48
Memberdietmar schoder9-Sep-15 8:48 
QuestionLove this puzzle! Pin
A. A. J. Rodriguez12-Aug-14 8:09
MemberA. A. J. Rodriguez12-Aug-14 8:09 
AnswerRe: Love this puzzle! Pin
dietmar schoder12-Aug-14 8:17
Memberdietmar schoder12-Aug-14 8:17 
GeneralRe: Love this puzzle! Pin
PIEBALDconsult12-Aug-14 8:21
professionalPIEBALDconsult12-Aug-14 8:21 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.