The N-Queens Problem/Puzzle is a well-known problem that consists of placing N chess queens on an N × N chessboard so that no two queens attack each other. For example, one possible solution to the N-queens problem for N = 4 is the following:
|Fig. 1: N-queens problem example (N = 4). Source: Google Optimization Tools|
As you can see, no two queens are on the same row, column or diagonal. Usually the problem consists to find all possible solutions, rather than one optimal solution.
I wrote a script in Python that calculates the number of all possible solutions. This script can be used as Benchmark for e.g. the Raspberry Pi.
Many people use the N-queens problem to test the performance of a defined solver. But this can be cheated. In my case, the solver (script) is not optimal (I implemented the backtracking way based on this solution), but it works, and it helps me to compare different configurations of the Raspberry Pi (kernel, model B & B+ etc.). I solved the N-queens problem for N=12, in single (ST) and multi-thread (MT) configurations and repeated the tests 45(ST)/100(MT) to check the result variances.
All the data, scripts and notebooks are available here: