Optimizing the brute-force search for an n-queens solution

NOTE: This post is part of a series of posts on Solving problems with simple yet powerful abstractions in Python. This is Part 5 of the series. You can find an index of the posts in the series in the specified link.

In our last post, we came up with a solver for the n-queens problem using abstractions we came up with in our previous posts. In this post, we’re going to take a look at optimizing our brute-force search.

Before we go about optimizing, let’s ensure we have some numbers to know that we’re indeed causing improvements due to our optimization efforts. Changing our main program/calling code would be the easiest way to do this. As things stand, let’s run a test evaluation of our brute-force solution to the n-queens problem. This can serve as a useful benchmark for us:

Avoiding useless work

And reducing the search space in the process

When we look at the present search, we’re iterating over all queen positions at each row. However, we could never have solutions where 2 queens are present in the same column on two different rows. Given our representation, no two elements in the list of size n can ever be the same. To put it differently, our candidate solutions are only those that have n unique columns, not all possible combinations of them.

Given our domain is made up of a product of other domains, we need a way to filter out candidates to refine our domain. There’s another neat abstraction! Let’s write one:

Notice that we’re reusing the map_domain abstraction we came up with in the previous post. Using our latest abstraction, filtering out the unnecessary candidates is really simple:

We can see the performance improve:

This optimization works better as the sizes of the boards increase, but we’re still doing a lot of work generating boards which are being filtered out later. Is there something better we can do?

Looking at this another way

This is where knowing a lot of concepts helps

So far, we’ve been thinking that every row has its own domain, and the board is a product of all the row domains. Which is neat, and it works! But can we do better? If we really think about the values we’re filtering out, and not filtering out, we can see there’s a pattern:

All the boards are just permutations of [0, 1, 2, 3]! What if we generated only permutations? This should be simple to write. Let’s try:

Notice that since we’re only generating valid rows, we don’t need to use the filter anymore. And here’s our results:

Sure enough, there’s a huge improvement. Now we hardly take a third of a second to find all 92 solutions for a size of 8! That’s pretty cool — all it required was to think of the problem slightly differently. Having a different perspective always helps — a lot! And this is just one such instance. Note that there’s nothing wrong with how we approached the solution initially. Sometimes, there’s just other ways to think about things that drastically simplify things for us.

Conclusion

How far can we go with this?

Well, for one, we just learnt that we can use brute force to solve problems like n-queens. Our initial abstraction of brute-force search seems to be holding up well. But exhaustively searching for solutions from all possible candidates is sometimes not possible. To illustrate this, we’re going to take a larger size, and see how brute-force may not work, and see what else we can come up with.

But that’s for the next post. Until then, have fun!