The N Queens Problem

The N Queens problem is an abstract problem from Chess that is often used as a simple non-trivial example domain for algorithm design. The solutions discussed below apply Prolog's backtracking mechanism to perform a controlled search of the space.

Source code for both solutions are available in the zip file here.

This problem, and the following Logic Puzzle problem, provide good candidate problems for investigating how to design generate and test algorithms more efficiently than a purely brute force approach.

First solutionThe Problem Description

On a standard chess board the problem is to place 8 Queens on the 8x8 board in such a way that no Queen threatens any other Queen. This is then generalized to NxN boards with N Queens.

The image on the right shows one solution to this problem for the standard 8x8 board. Note that no queen is in the same column as any other queen, no queen is in the same row as any other queen, and no queens share a common diagonal.

This particular solution is the first one found by the algorithm described in the following pages.

You can find some useful introductory discussion on the Wikipedia page for the 8 Queens problem.

An Algorithm

We want to define an algorithm that will find solutions to this problem. We want the algorithm to find every solution, but to only find each solution once. And, ideally, we'd like the algorithm to be easy to understand.

Details here The initial solution

Implementing the Solution

Two versions of the program are presented.

The First Solution

The first solution has no concerns about efficiency. It implements the algorithm as described as clearly and cleanly as possible.

Details here The initial solution

Improving Efficiency

Now we have a clean solution that works, we can look at its implementation with a view to improving the run-time efficiency of the code. In this case it is possible to significant improvements.

Details here The performance tuned solution

Comparing the Implementations

When we compare the two implemenations, the difference seems small. If anything, the second implementation seems more complex. However, we will see that the effect this has on the relative efficiency of the two programs is very significant.

Details here The performance tuned solution

Conclusions

Although the term is normally used in a slightly different way, what we have found here is the algorithmic benefit of failing fast. That is, detecting any condition that means we cannot possibly find a solution from the current state as early as possible means we can abandon any further computation on that path.

Details here The performance tuned solution