Eight Queens: A Simple Backtracking Algorithm In Golang

The Eight Queens Puzzle, a popular computer science question reads:

How do you place eight queens on a chess board so that they do not attack each other?

The queen is the most powerful piece in a chess game. She can move in any direction and as far as she likes. This means a queen placed on the board attacks quite some fields. None of these fields can be used to place another queen because they would attack one another.

One solution to this problem includes backtracking, which is defined by Wikipedia as follows:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

The QueensBoard Package

Let’s implement a simple backtracking algorithm for the puzzle! It uses a package called QueensBoard which includes the following functions:

  • New() creates an 8x8 board.
  • board.Queens() returns the number of queens that are currently placed on the board. We will use this function to check if we have found a place for all the queens.
  • board.AvailableFields() returns a list of coordinates which are not under attack and therefore available to place a queen there.
  • board.PlaceQueen() takes coordinates as parameter and places a queen there if possible. It updates the board to mark all fields unavailable that are under attack.
  • board.RemoveQueen() takes coordinates as parameter and removes the queen from the field addressed by the coordinates.
  • board.Print() takes a Writer interface as parameter and writes a Unicode-powered human-readable representation of the state of the board to it. We will use it with os.Stdout to print the final result.

Recursive Approach

Backtracking and recursion often go very well together. We can use recursion to dive deeper and deeper into a prospective solution until

  • we either hit the base case and return the solution, or
  • we realize that we are on a path that will not lead to a solution.

If we barking up the wrong tree, we backtrack to the last state and try a different way. In our example, backtracking means, that we remove the last queen that we placed on the board if we realize that we can not place all eight queens. This usually happens when there are not enough unattacked fields left to place queens on.

Boringly, we will name then function queens(). It will take a *qb.Board as parameter and also return a pointer to a qb.Board struct. The base case will be the perfect board: One with eight queens that do not attack each other:

func queens(board *qb.Board) *qb.Board {
	if board.Queens() == 8 {
		return board
	}

	// here be magic

	return nil
}

Now we need to fill in the actual algorithm. First, we fetch the coordinates of all the fields that are currently not under attack. We are free to place a queen on any of them, so why not start with the first one? After placing the queen, we recursively dive into this prospective solution and place the next queen and the next queen and so on… If we did not reach our goal of placing eight queens, we remove the queen and try again with the next coordinate.

func queens(board *qb.Board) *qb.Board {
	if board.Queens() == 8 {
		return board
	}
	for _, coordinate := range board.AvailableFields() {
		board.PlaceQueen(coordinate)
		next := queens(board)
		if next != nil {
			return next
		}
		board.RemoveQueen(coordinate)
	}
	return nil
}

Find the full source at the end of the article. This algorithm is not the fastest one, however, on most machines, it should finish in less than a second. The final board should look like this:

Here is an animation of the first couple of steps of the algorithm:

small

Improve!

The QueensBoard package also offers the ability to create custom sized boards via the NewCustom() function.

  • Investigate how the algorithms scales for increasing board sizes?
  • Have you tried to randomize the list returned from board.AvailableFields()? How did this influence the average runtime of your algorithm?

Source Code

Here is the full source, ready to run:

package main

import (
	"os"

	qb "github.com/danrl/golibby/queensboard"
)

func queens(board *qb.Board) *qb.Board {
    // uncomment the next line to print intermediate steps
	//board.Print(os.Stdout)
	if board.Queens() == 8 {
		return board
	}
	for _, coordinate := range board.AvailableFields() {
		board.PlaceQueen(coordinate)
		next := queens(board)
		if next != nil {
			return next
		}
		board.RemoveQueen(coordinate)
	}
	return nil
}

func main() {
	board := qb.New()
	queens(board)
	board.Print(os.Stdout)
}