Solving the n-queens problem with brute-force search

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   | 2

Now 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:

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:

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   | 0

Here, 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:

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:

Here’s how we can print the solution to an n-queens problem (for n=4, there are only 2 solutions):

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!