I had some time to kill today, so I decided to take a brief look at a subject I’ve been wanting to study for some time: backtracking algorithms. One of the most common example problems used to demonstrate backtracking algorithms is the eight queens puzzle, so I thought I’d try my hand at writing a solver for it in python.

The solver itself consists of one core class, Board, which contains a representation of a chess board as an 8×8 matrix of integers (the reason for this will be explained later in the article) and a list of queens on the board, where each queen is represented by a (row, col) tuple.

class Board: def __init__(self): self.board = [ [ 0 for x in range(8) ] for y in range(8) ] self.queens = [] |

Since we’ll be placing queens on the board and removing them as part of the backtracking algorithm, our Board class should provide this functionality. The backtrack algorithm will only need to remove the last queen that was placed, so we can implement it like a stack, with two operations: push:

def push_queen(self, coord): #XXX: Should check if coord is a valid move row, col = coord self.board[row][col] += QUEEN self.mark_queen(coord, 1) self.queens.append(coord) |

and pop:

# Remove the last queen that was placed on the board. def pop_queen(self): row, col = self.queens.pop() # 'Unmark' all the squares the queen was covering. self.mark_queen((row, col), -1) # 'Unmark' the square the queen itself was on. self.board[row][col] -= QUEEN |

(I’ll explain the `+= QUEEN` and `-= QUEEN` business in a moment. For now, just understand that these lines of code ‘mark’ and ‘unmark’ the square the queen lies on).

We can’t just mark the square a queen occupies on the board; we also need to indicate which squares are no longer valid for a queen to be placed in. This is where the `mark_queen()` function comes into play. It marks all of the squares that the queen can cover. The way I have chosen to implement this is by ‘radiating’ out from the queen: that is, I check squares in all 8 directions from the queen, starting with a distance of 1 and going up to a distance of 7 (the maximum distance away a square on the board could be from the queen). If the square is still within the boundaries of the board, I mark it as being covered by the queen:

# 'Mark off' the squares the given queen at coord covers on the board. def mark_queen(self, coord, mark): row, col = coord # 'Radiate' out in all 8 directions from the queen. for x in range(1, 8): if row - x >= 0: self.board[row - x][col] += mark # -x, 0 (W) if col - x >= 0: self.board[row - x][col -x] += mark # -x, -x (SW) if col + x < = 7: self.board[row - x][col + x] += mark # -x, +x (NW) if row + x <= 7: self.board[row + x][col] += mark # +x, 0 (E) if col - x >= 0: self.board[row + x][col - x] += mark # +x, -x (SE) if col + x < = 7: self.board[row + x][col + x] += mark # +x, +x (NE) if col - x >= 0: self.board[row][col - x] += mark # 0, -x (S) if col + x < = 7: self.board[row][col + x] += mark # 0, +x (N) |

To further explain this code, it’s helpful to take a step back and look at a problem with a naive implementation of this function. Let’s assume for a second that instead of integers, we just use two values, say T and F, to indicate that a square is or isn’t covered by a queen. So we place a queen on the board by setting that square to F, and using `mark_queen()` to set all the squares the queen covers to F, indicating that a queen can no longer be placed in those squares. Now, say we place a second queen on the board using the same process; set the square the second queen is on to F and use `mark_queen()` to set all the squares the second queen covers to F. So far, so good.

Let’s see what happens if we use `pop_queen()` to remove that second queen we just placed. We set the square the second queen was on to T, and then use `mark_queen()` to set all of the squares the second queen covered to T, indicating they are now valid squares to place a queen. And here we have our problem: this is not necessarily true! If there is a square that both the first and second queen cover, its value needs to remain F since the first queen still covers it! But in using our naive implementation of `mark_queen()`, we have erroneously marked that square as T.

One way to solve this problem is to use an integer instead of just T and F. The integers act as ‘counters’ for the squares, indicating how many queens cover those squares. When the counter is 0, the square is free (since no queens are covering it) and any value greater than 0 will indicate the square is covered by at least one queen. Following this idea, we can now see how `mark_queen()` works: when a queen is placed on the board, we increment the counter of every square it covers, and when a queen is removed from the board, we decrement the counter of every square that queen covered. This method solves the problem above, since now if two queens cover the same square and we remove one of them, the counter will stay above 0 and the square will retain it’s “covered” status. To record the queen itself, I picked an arbitrarily large integer in order to distinguish it from squares that are merely covered:

# Arbitrarily large constant to use for the value of the queen QUEEN = 100000 |

This helps aid us in printing out the board in a human-readable format:

# Pretty-print the board def pprint(self): for x in range(8): for y in range(8): if self.board[x][y] == QUEEN: print "Q", else: print "_", #print self.board[x][y], print |

The last thing we need to implement the backtrack algorithm is a function to find all the free squares where we can place a queen. Following the ideas above, we just need to find all the squares that have a value of 0:

# Generate a list of all the valid squares a queen can be placed on. def list_valid_moves(self): valid_moves = [] for x in range(8): for y in range(8): if self.board[x][y] == 0: valid_moves.append((x, y)) return valid_moves |

We are now ready to implement the backtrack algorithm. Given all the work above to implement the Board class, this function is surprisingly short:

# Backtracking depth-first solver. def solver(self): # Get a list of valid moves valid_moves = self.list_valid_moves() for valid_move in valid_moves: self.push_queen(valid_move) self.solver() if len(self.queens) == 8: return # this queen placement did not lead to a solution with 8 queens. # Therefore, this placement can't be part of any valid solution, so # roll it back and try the next one. self.pop_queen() # Nothing in the list of valid moves led to a solution, or there were # no valid moves left to try. return |

In this function, we first generate a list of all the valid squares to place a queen. Then, for each valid square, we try placing a queen there and repeating the process: generating a new list of valid squares, and placing a queen in each one. Eventually, we will get to a point where one of two things will have occurred:

- We have placed 8 queens in total on the board, in which case this is a valid solution and we're done.
- There are no more valid squares to place a queen, and there are less than 8 queens in total on the board, in which case no solution involving the given queen placements exists.

So once the function terminates, the board will either contain a full solution, or it will contain a partial solution, in which case no full one exists. Another way to think of the code is as a depth-first search on the solution tree: the for loop cycles through all the children (possible queen placements) of a given node (the current board configuration), and each call to `self.solver()` expands a child node (places a queen) to go deeper into the solution tree (analyzing the new board configuration). However, instead of examining the entire tree, as soon as the algorithm sees a solution isn't possible from the current configuration it 'backs up' (removes the last queen placed) and tries a different branch (a different queen placement). The code goes through about 26,000 queen placements before finding the full solution; much faster than checking all 4.5 billion possible configurations. This is the solution it found:

$ python 8queens.py Q _ _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ Q _ _ _ _ _ Q _ _ _ _ Q _ _ _ _ _ _ _ _ _ _ _ Q _ _ Q _ _ _ _ _ _ _ _ _ Q _ _ _ _ $

And here's the code. Enjoy!