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

The eight queens problem is to place eight queens on a chess board so none of them can attack any of the others. More generally, the N queens problem is to place N queens on an N×N board.

If you allow non-square boards, you get some new solutions. For example, there are no solutions for 2 queens on a 2×2 board but there are solutions on a 2×3 board.

This problem is interesting for a two main reasons. First, it provides an interesting exercise in recursion. Second, there are a few different approaches that you can take depending on how you think about the problem and the difference in performance is huge.

This post is the first in a series of three that look at some different approaches.

(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#.)

Testing Boards

The board_is_legal function tests a board to see if any queens can attack each other. It takes as parameters the number of rows and columns, and board. The board parameter is a two-dimensional array (list of lists) holding True for squares that contain queens and False for empty squares.

The following code shows how board_is_legal tests a board to see if any queen can attack another.

def board_is_legal(num_rows, num_cols, board): '''Return True if this board arrangement is legal.''' for row in range(num_rows): for col in range(num_cols): # See if this position is taken and attacks another square. if spot_is_illegal(num_rows, num_cols, board, row, col): return False return True

Testing Squares

def spot_is_illegal(num_rows, num_cols, board, row, col): '''Return True if this spot holds a queen and attacks another queen.''' if not board[row][col]: return False # No queen here. # Check the row. for c in range(col + 1, num_cols): if board[row][c]: return True # Check the column. for r in range(row + 1, num_rows): if board[r][col]: return True # Check the upper left to lower right diagonal. r = row + 1 c = col + 1 for i in range(max(num_rows, num_cols)): if r >= num_rows or c >= num_cols: break # We ran off the board. if board[r][c]: return True # Enemy queen spotted. r += 1 c += 1 # Check the upper right to lower left diagonal. r = row + 1 c = col - 1 for i in range(max(num_rows, num_cols)): if r >= num_rows or c < 0: break # We ran off the board. if board[r][c]: return True # Enemy queen spotted. r += 1 c -= 1 # If we get here, we can't attack another queen. return False

Next, the code uses a loop to see if any square to the target square's right contains a queen and, if so, it returns True. Notice that the loop doesn't check any squares to the left of the target because, if there was a queen in that position, we would have found it when we examined the squares to the right of that queen.

The code uses a similar loop to look for queens in the target square's column.

Checking the diagonals is a little more complicated. The code sets variable's r and c to the square one position down to the right of the target square. It then enters a loop to check squares down and to the right. Inside the loop, the code first checks whether the row or column has moved off of the board and, if so, it breaks out of the loop. Next, if the square contains a queen, the function returns True. The code then increments r and c to move to the next square along the diagonal.

After it checks the diagonal down and to the right, the code uses a similar loop to check the diagonal down and to the left.

If the function survives all of its tests, it returns False to indicate the target square does not attack another queen.

Enumerating Possible Solutions

The most straightforward approach to the problem is to enumerate all possible solutions until you find one that works. For example, on an 8×8 board, you generate all possible selections of 8 squares and look for one that works.

You can write your own recursive function for generating combinations of squares, or you can use the itertools library. This example uses the later approach because it's easier.

The following solve_eight_queens function takes as parameters the board's dimensions. It returns True to indicate whether it found a solution and the number of combinations it examined.

from itertools import combinations 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. ''' # Make a list of square numbers to generate combinations. squares = list(range(num_rows * num_cols)) # Figure out how many queens there wlll be. num_queens = min(num_rows, num_cols) # Generate the combinations. generator = combinations(squares, num_queens) # Enumerate the combinations. for i, combination in enumerate(generator): # Make a board for this combination. board = [[False for c in range(num_cols)] for r in range(num_rows)] for square in combination: row = square // num_cols col = square - row * num_cols board[row][col] = True # See if this combination works. if board_is_legal(num_rows, num_cols, board): return board, i + 1 return None, i + 1

Next, the code calculates the maximum number of queens that could fit on the board. It then uses the itertools library's combinations function to make an object that can generate combinations of num_queens values from the square numbers.

The code then enumerates the values returned by the generator. Each value is a list holding num_queens square numbers. For example, the value [0, 1, 2, 3, 4, 5, 6, 7] represents putting eight queens on the board's first eight squares across the top row.

For each generated combination, the code creates a board, a two-dimensional array (list of lists) holding False for each square on the board. It then loops through the indices in the current combination and sets their board values to True.

Next, the code passes the board into the board_is_legal function to see if any of the queens can attack each other. If board_is_legal returns True, we have found a solution so solve_eight_queens returns the board and the number of combinations it examined.

If the function finishes testing every combination without finding a solution, the function returns None and the number of combinations it examined.

Conclusion

The main takeaway from this example, is how the program searches for solutions. It does that by examining all possible selections of squares until it finds one that works. The following three pictures show solutions for 6×6, 7×7, and 8×8 boards.

You can see that the time needed grows extremely quickly. That makes sense because the number of possible solutions on an N×N board grows extremely quickly as N increases. The number of solutions on a board is large, but the number of possible solutions is much larger so it takes a while to find an arrangement of queens that works.

In my next two posts, I'll describe different ways that you can look at the problem. Those new approaches provide new, faster solutions.