Title: Solve the eight queens problem in Python, Part 2

My post Solve the eight queens problem in Python, Part 1 shows how to use the itertools library's combinations function to search for solutions to the eight queens problem. It uses that function to enumerate possible arrangements of the queens on the board until it finds one where no queen can attack another.

This post describes a second approach that is much faster.

(For more information on this problem and other interesting algorithms, see my book Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#.)

Checking Every Arrangement

For example, the number of ways you can pick 8 positions for queens on an 8×8 board is:

It's possible to examine a large fraction of 4 billion possible arrangements, but the board doesn't need to grow much larger before this approach becomes prohibitively slow. What we need is a way to reduce the number of arrangements that we must consider.

Narrowing the Choices

(0, 1, 2, 3, 4, 5, 6, 7) (0, 1, 2, 3, 4, 5, 6, 8) (0, 1, 2, 3, 4, 5, 6, 9) (0, 1, 2, 3, 4, 5, 6, 10) (0, 1, 2, 3, 4, 5, 6, 11) (0, 1, 2, 3, 4, 5, 6, 12) (0, 1, 2, 3, 4, 5, 6, 13) (0, 1, 2, 3, 4, 5, 6, 14) (0, 1, 2, 3, 4, 5, 6, 15) (0, 1, 2, 3, 4, 5, 6, 16)

The second arrangement leaves the first seven queens on the first row and moves the last queen to position 8, which is in the first column of the second row. The first seven queens are still all on the same row, so they can attack each other and therefore this arrangement is also illegal.

At this point, you can probably see the problem. The next solutions are only small modifications of these. In particular, they keep the first two queens on the first row where they can attack each other so all of these arrangements are illegal. In fact, the enumeration begins with 61,474,519 arrangements where the first two queens are in positions 0 and 1 so none of those will work.

Examining all of those initial arrangements is a huge waste of time, but the problem is even worse than that. Every time the program finds that an arrangement won't work, the next arrangement is very similar. Just as in the problem with the first two queens, wrong solutions lead to many more wrong solutions that are only slight modifications of the original.

This example uses an approach that is similar to the one used by the previous example. It also enumerates arrangements. This time, however, the program does the enumeration instead of relying on itertools.combinations. That would be more work and probably less efficient than just using itertools.combinations, except the program can short-circuit its tests and bail out on any arrangement as soon as it is illegal.

For example, the program starts with the first queen in position 0. It then adds a second queen in position 1. At that point, the board is already illegal so there's no need for the program to examine all of the 61,474,519 arrangements that have the first two queens in those positions.

Similarly when the program find other illegal partial arrangements, it doesn't need to continue working on those arrangements. That results in a huge savings in time.

Enumerating Arrangements

def solve_eight_queens(num_rows, num_cols): ''' Solve the eight queens problem. Return the solution (if any) and the number of test placements we made. ''' # Start with an empty board. board = [[False for c in range(num_cols)] for r in range(num_rows)] # See how many queens could fit. num_queens = min(num_rows, num_cols) # Try to extend the empty solution. success, num_attempts = place_queen(num_rows, num_cols, num_queens, board) return board, num_attempts

def place_queen(num_rows, num_cols, num_queens, board, num_placed=0): ''' Explore this test solution. Return True if we find a solution. Also return the number of test placements we make. ''' # See if the test solution is already illegal. if not board_is_legal(num_rows, num_cols, board): return False, 0 # If we have positioned all of the queens, this is a solution. if num_placed == num_queens: return True, 0 # Extend the partial solution. Try all positions for the next queen. num_attempts = 0 for row in range(num_rows): for col in range(num_cols): if not board[row][col]: # Make sure this spot is empty. num_attempts += 1 board[row][col] = True # Recursively see if this leads to a solution. success, new_num_attempts = place_queen( num_rows, num_cols, num_queens, board, num_placed + 1) num_attempts += new_num_attempts if success: return True, num_attempts # The extension did not lead to a solution. Undo the change. board[row][col] = False # If we get here, we could not find a solution from this partial solution. return False, num_attempts

The code first checks to see if the current board is illegal and, if it is, the function returns False.

If the board is legal and we have assigned the full number of queens, then the current board is a solution so the function returns True.

If the board is legal so far and as have not positioned all of the queens, the code uses two nested loops to loop over every squares on the board. If a square is empty, the function does the following.

First, the code increases num_attempts, the number of times the function places a queen on the board. It then sets board[row][col] = True to temporarily put a queen at this position.

The function then recursively calls itself to try to position the remaining queens.

When the recursive call returns, the function adds the number of positionings used by the recursive call to its own num_attempts value.

If the recursive call found a legal solution, this call to the function returns so the solution passes back up the call stack.

If the recursive call could not find a legal solution, the function sets board[row][col] = False to remove the current queen from its test position.

The loop then continues, trying to place the queen in other squares. If the function finishes examining every square without finding a solution, then the initial partial solution that this function call started from cannot be extended to a full solution so the function returns False.

Eventually the top-level call to place_queen returns True if it found a solution or False if there is no possible solution for this board.

Conclusion

Notice how the new algorithm is much faster than the old one. The original algorithm starts taking a significant amount of time on the 6×6 board and really starts testing my patience on the 8×8 board at almost 40 minutes.

In contrast, the new algorithm doesn't start to really slow down until the 10×10 boards.

The following graphs show the two algorithms' times and number of tests. They make it more obvious that the time used by both algorithms really starts to head toward the moon on larger boards.

In my next post, I'll describe a different way of thinking about the arrangements that makes the program even faster. Until then, download the example to experiment with it and to see additional details.