Home Up Leave Message

The idea of the Eight Queens puzzle is to place 8 queens (colour doesn't matter) on a chess board such that no queen would be in line of any other queen. Please remember that a queen can capture anything in direct line of sight of the same row or column or on any diagonal from her.

The following is an example of such a solution.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

But, we are more interested in how to get to the solution than in what the (or a) solution is in this instance.

Basic Solution

The way to do this is actually quite simple start on line (rank) 1 and column (file) a and place a queen there.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Now we know that:

• we cannot place anything else on the same line because they would endanger each other, therefore we need to proceed to the next line,
• we cannot take the same column on the next line (a2) because once again they would endanger each other,
• we cannot place anything at b2 because a1 and b2 are on the same diagonal.

Now we can try b3 seeing that it and a1 doesn't endanger each other.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Now we move to the next line for the same reasons mentioned previously. Here we see that the first column that would not endanger any of the previous queens would be at e3.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

For the next line b4 would be an option:

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

An for the next d5 would be an option (don't be mislead by an apparent pattern that emerges, we'll see why shortly):

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

We mentioned that an apparent pattern is starting to emerge. But on line 6 we see that none of the column produce a possible solution. Columns a to e are endangered directly by the previous queens in those columns. Columns f to g are endangered diagonally by the queens in lines 1 to 3.

Thus we have to backtrack to line 5 and move the queen to the next possible valid potion, and this is at column h.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

But here we run into another problem if we try to put a queen on line 6. There is once again no place to put queen that will not endanger any previous ones.

Now if be backtrack to line 5 we cannot proceed to another column so we have to backtrack to line 4 and move the queen on that line to the next possible position. Which in this case will be at column g.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

I'm sure by now you get the idea. And if you continue on this wise you can get to our example that we started with or one of its permutations.

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

The Algorithm

We will now proceed to put our discussion above into an algorithm. We will have as a first go something that is more word based than really code.

First we note that we use the same approach on every line and test against previous lines for endangerement and if we reach to no solution on a line then we backtrack to the previous line and try the next column.

Function EightQueens(line)
// Line is the line we are trying to solve
// Board is the board as it was populated on the previous line
 1. If line > 8
    // All lines were searched thus a solution was found
    // seeing that none of the previous lines had any endangerment 
    1. Print the solution
    2. Return true to indicate success
 2. for each column (on this line)
     1. if no other queen on this column (on any other line)
         1. if no other queen on a diagonal
             1. Update board by setting the line and column
             2. Call EightQueens(line+1)
             3. If answer
                 1. Return true to previous line
 3. No solution found on this line, return false and backtrack to previous line

We can now make the algorithm a bit more code like. To make things easier for us we will use lines 0 to 7 and columns 0 to 7.

Function EightQueens(line)
 1. If line > 7
    1. Print the solution
    2. Return true
 2. for column := 0 to 7
     1. endangered := false
     2. for line2 := 0 to line-1
        1. if board[line2,column-(line-line2)] = 1 or board[line2,column+(line-line2)] = 1
           // remember that on a diagonal the line difference is the same as the 
           //       column difference
           // also note that there is no column before 0 or after 7, but we will 
           //       handle that in the actual code
            1. endangered := true
     3. if not endangered
        1. board[line,column] := 1
        2. if EightQueens(line+1)
            1. Return true
        3. board[line,column] := 0 // To clear a postion that did not work
 3. Return false

Function Main
 1. board := empty board (8 columns and 8 rows)
 2. EightQueens(0)

A slightly more optimized solution

We can take above algorithm and make is slightly better. We notice that we use a two dimensional array with a 1 where the queens are to be. We now that each line can only have one column, so we instead of using a two dimensional array we can use a one dimensional array for the lines and for each line the column where the queen appears.

To check if two queens are on the same diagonal we just need to check if the absolute values of the differences of their columns and of their rows are the same. If they are then they are on the same diagonals.

Function EightQueens(line)
 1. If line > 7
    1. Print the solution
    2. Return true
 2. for column := 0 to 7
     1. endangered := false
     2. for line2 := 0 to line-1
        1. if board[line2]==column or abs(line-line2)=abs(column-board[line2])
           1. endangered := true
     3. if not endangered
        1. board[line] := column
        2. if EightQueens(line+1)
            1. Return true
 3. Return false

Function Main
 1. board := empty board (8 columns and 8 rows)
 2. EightQueens(0)

Program Source