Solving the n-queens problem with brute-force search
In this post, we take the brute force and other abstractions we created earlier, to solve the n-queens problem for a relatively small n.
NOTE: This post is part of a series of posts on Solving problems with simple yet powerful abstractions in Python. This is Part 4 of the series. You can find an index of the posts in the series in the specified link.
In the previous post, we solved for multiple variables using brute-force search. In this post, we’re going to try to solve for the n-queens problem using the same algorithm. We’ll be reusing some abstractions we defined earlier, so please go through the earlier posts to follow along. We’re going to look at a naive implementation, and then apply a few optimizations. And then we’re going to find out the limitations of brute-force search before we move on to optimizations.
Understanding the problem
As usual, the first step in solving a problem
The n-queens problem is the problem of placing n queens in an nxn chess board such that no queen attacks another. The problem is n, a natural number that’s not 2 or 3. The solution can be thought of as finding a solution per row of the board, and for each row, the solution is the column the queen is present at, some index from 0 to n-1. For every problem, the solution is a product of n row domains — using the abstraction from our previous post.
For example, here’s a board for n = 4: 1, 3, 0, 2
pictorial | row | column
----------|-----|-------
_ Q _ _ | 0 | 1
_ _ _ Q | 1 | 3
Q _ _ _ | 2 | 0
_ _ Q _ | 3 | 2Now that we’re able to represent the board, let’s add a way to work with the board. Instead of just using a vector of int s, we want to strongly type our solution domain. In this case, this is what our chess board can be described by:
| from copy import deepcopy | |
| from typing import NewType | |
| Row = NewType("Row", int) | |
| Column = NewType("Column", int) | |
| Board = NewType("Board", list[Column]) | |
| def place_queen(board: Board, row: Row, column: Column) -> Board: | |
| next_board = deepcopy(board) | |
| next_board[row] = column | |
| return next_board | |
| def stringify(board: Board): | |
| size = len(board) | |
| row_strings = [] | |
| for row in board: | |
| col_strings = [] | |
| for i in range(size): | |
| col_strings.append("Q" if i == row else "_") | |
| row_strings.append("{}\n".format(" ".join(col_strings))) | |
| return "".join(row_strings) |
Understanding valid solutions
The description of our accept function to the brute-force search
A valid solution should be such that no two rows have queens in the same columns. In addition, none of the queens should be in the same diagonal. That’s about it. Let’s write some code to express the same. Since whether a board has any collisions is part of the solution domain, I’d just keep it within the board utilities:
| from typing import Generator, NewType, Tuple | |
| Size = NewType("Size", int) | |
| Row = NewType("Row", int) | |
| Column = NewType("Column", int) | |
| Board = NewType("Board", list[Column]) | |
| # ... rest of the code omitted for clarity | |
| def has_collision(board: Board, pair: Tuple[Row, Row]) -> bool: | |
| row_x, row_y = pair | |
| if row_x == row_y: | |
| return False | |
| col_x = board[row_x] | |
| col_y = board[row_y] | |
| if col_x == col_y: | |
| return True | |
| row_diff = row_x - row_y | |
| col_diff = col_x - col_y | |
| return row_diff == col_diff or row_diff == -col_diff | |
| def row_pairs(size: Size) -> Generator[Tuple[Row, Row], None, None]: | |
| for x in range(size): | |
| for y in range(size): | |
| yield Row(x), Row(y) |
The has_collision method checks whether there exists a collision between any pair of rows. If the rows are the same, there’s no collision. If the location of the queens in both the rows are the same, then there’s a collision. Due to the nature of the board, collisions within a row are impossible. With the other condition, two queens cannot be on the same column, or else there’s a collision. To check for the queens in the same diagonal, we check the difference in the positions of the queen (columns) at those rows. If the difference is positive or negative but the same as the row difference, it means they are present in the same diagonal and therefore there’s a collision.
Here’s an example:
pictorial | row | column
----------|-----|-------
_ Q _ _ | 0 | 1
_ _ _ _ | 1 | _
_ _ _ Q | 2 | 3
_ _ _ _ | 3 | _Here, for the row pair (0, 2) , the row difference is 0 — 2 = -2 and the column difference is 3 — 1 = 2 so they are in the same diagonal. In another example:
pictorial | row | column
----------|-----|-------
_ _ _ Q | 0 | 3
_ _ _ _ | 1 | _
_ _ _ _ | 2 | _
Q _ _ _ | 3 | 0Here, for the row pair (0, 3), the row difference is 0 — 3 = -3 and the column difference is 0 — 3 = -3 so they are in the same diagonal. So, if the magnitude of the column difference is the same on the row difference, there’s a collision. Note that we already check that the 2 rows in comparison are not the same.
Now that we have a representation of the board, and a way to check for collisions, let’s apply our brute-force solution.
Solving the n-queens problem
Using our brute-force search algorithm and related abstractions
Notice that while our domain is a product of several smaller domains, we actually need a domain of chess boards, and not a domain of a list of integers. What we need is to be able to map elements of one domain into elements in another domain. Time to add that abstraction:
| from typing import Protocol, TypeVar | |
| from domain import Domain | |
| from solve import Problem | |
| T = TypeVar("T") | |
| R = TypeVar("R") | |
| class Up(Protocol[Problem, T, R]): | |
| def __call__(self, problem: Problem, candidate: T) -> R | None: | |
| pass | |
| class Down(Protocol[Problem, T, R]): | |
| def __call__(self, problem: Problem, candidate: R) -> T: | |
| pass | |
| class Map(Protocol[Problem, T, R]): | |
| def __call__(self, domain: Domain[Problem, T]) -> Domain[Problem, R]: | |
| pass | |
| def map_domain( | |
| up: Up[Problem, T, R], down: Down[Problem, T, R] | |
| ) -> Map[Problem, T, R]: | |
| def map(domain: Domain[Problem, T]) -> Domain[Problem, R]: | |
| def first(problem: Problem) -> R | None: | |
| first_value = domain.first(problem) | |
| return None if first_value is None else up(problem, first_value) | |
| def next(problem: Problem, candidate: R) -> R | None: | |
| next_value = domain.next(problem, down(problem, candidate)) | |
| return None if next_value is None else up(problem, next_value) | |
| return Domain(first, next) | |
| return map |
Now that we’re able to map solutions, let’s try to add a brute force solver for the n-queens problem. We can see how most of the abstractions we came up with earlier prove really useful:
| from functools import cache, partial | |
| from typing import Tuple, TypeAlias | |
| from board import Board, Size, has_collision, row_pairs | |
| from brute_force import First, Next | |
| from domain import Domain, brute_force | |
| from func_utils import always | |
| from integers import integers | |
| from map_domain import Down, Up, map_domain | |
| from product import product | |
| Rows: TypeAlias = Tuple[int, ...] | |
| @cache | |
| def __rows_domain(size: Size) -> Domain[Size, Rows]: | |
| row_domain = integers(always(0), always(size)) | |
| row_domains = [row_domain] * size | |
| return product(*row_domains) | |
| __first: First[Size, Rows] = lambda n: __rows_domain(n).first(n) | |
| __next: Next[Size, Rows] = lambda n, rows: __rows_domain(n).next(n, rows) | |
| __up: Up[Size, Rows, Board] = lambda n, rows: Board(rows) | |
| __down: Down[Size, Rows, Board] = lambda n, board: board | |
| __boards = map_domain(__up, __down)(Domain(__first, __next)) | |
| def __accept(size: Size, board: Board) -> bool: | |
| return not any(filter(partial(has_collision, board), row_pairs(size))) | |
| n_queens = brute_force(__boards, __accept) |
Here’s how we can print the solution to an n-queens problem (for n=4, there are only 2 solutions):
| from board import Size, stringify | |
| from n_queens import n_queens | |
| # find solutions for n queens problem where n = 4 | |
| n = Size(4) | |
| format_string = "solution for n-queens where n={}, {}:\n{}" | |
| for board in n_queens(n): | |
| print(format_string.format(n, board, stringify(board))) | |
| # prints | |
| # solution for n-queens where n=4, [1, 3, 0, 2]: | |
| # _ Q _ _ | |
| # _ _ _ Q | |
| # Q _ _ _ | |
| # _ _ Q _ | |
| # | |
| # solution for n-queens where n=4, [2, 0, 3, 1]: | |
| # _ _ Q _ | |
| # Q _ _ _ | |
| # _ _ _ Q | |
| # _ Q _ _ |
Wow, we just solved a kind of a complex problem using the same abstraction we introduced in the first post. And the subsequent abstractions are proving to be really useful!
Conclusion
That was some serious progress!
We just went from finding multiples of a number to solving the n-queens problem. And it seems like the abstractions we create are really powerful even if they seem simple. Being able to compose abstractions like domain, product, and map_domain helped us quickly whip up a solver for the n-queens problem.
In the next post, we’re going to look at a few optimizations on top of the naive brute-force search we’re doing right now, and see what other abstractions we can come up with. We can also review our current abstractions to see if they can be redone. Until then, have fun!