Other pages on the n queens problem, and some comments

Wikipedia

A good article is contained in Wikipedia or the German version of it.

TU Dresden

Along with the world record for the (normal) 26 x 26 board, the TU Dresden (technical university of Dresden) has published a page. They describe in some detail how they managed to get the requested degree of parallelity, using FPGA (field programmable gate arrays).

nQueens@home project

There was a BOINC project to count number of solutions for the next higher boards. It seems that this project was dogged by bad luck. It found as first the number of solutions to the 24 x 24 board; but later the number turned out to be wrong. An overflow of 32-bit numbers had not been detected in the program. The difference to the new and hopefully correct number was 781 684 047 872 = 0xb6 0000 0000.

The projects home page was located under nQueens@home, but that page seems to be offline since some months. I do not know why it is offline, or if it has moved. The partial results that the project has found are valuable; I assume they were also an affirmation for the TU Dresden team when they started their search. I would be grateful if somebody knows about that page and could inform me.

The first alphabetic solution

A special aspect is the question: which solution is smallest, or first in alphabetic order? Martin and Colin Pearson dealt with this question. There are two pages, CSP Queens - Counting Queen-placements (of Colin), and Queens On A Chessboard (of Martin).

It is not really hard to find a n queens solution even for large n. Some articles deal with it. But we should state the question more precisely first, because explicit constructions are known which can be adopted to give a solution in virtual no time on modern computers. The articles deal more with the problem to find a solution lying "near" an initial permutation. "Near" means in this context that only few positions should be changed, from the initial state.

If a strict order is requested, the problem becomes harder. There are copious areas in the space of all permutations, where the density of n queens solutions is relatively high and a solutions can be found easily, and there are meagre areas. The starting and the ending area turn out to be extremely meagre.

The standard algorithm takes, in "greedy" manner, many long diagonals at start, and strangles itself for the upper rows doing so.

That is going so long that it takes some hundred hours to get a first solution, while the same program delivers some ten solutions per second in copious areas.

It is a challenge, of course, to find a more sophisticated algorithm which can scan the meagre areas faster than the usual algorithm. I am working on ideas for that.

Martin and Colin Pearson give also numbers of tentative queen placements needed to find the first solution with the standard algorithm. This data is wonderful to compare with. The basic idea is to invest more work before the next tentative queen placement, and to overcompensate that by a big decrease in the number of placements.

Heise news and discussion

You can find a lot of discussion under Heise message (in German) and under Discussion on Heise (in German).

• There is much discussion if it is meaningful to work on the n queens problem, and especially to spend CPU time and electric energy on it.
• Some discussion refers to use of symmetries. A good explanation on a basic level for symmetry is contained in the page of TU Dresden (see above).
• Most interesting to me, a participant of the forum ("Max-Spam") assumes that the n queens problem may be solved easily, with almost no CPU time (< 1 s) by the method discussed in Die Kunst des komplexen Zählens, (in German) an article in the German newspaper "Frankfurter Allgemeine", on a new algorithm developed by Timme, van Bussel, Fliegner and Stolzenberg. But it is not true that the n queens problem is solved by the method. While the new algorithm is useful for some problems of graf theory, it is not applicable to the n queens problem directly. The problems are near to each other but not identical. It would be a pity if people working on the n queens problem are discouraged by this misunderstanding.

More pages

More pages will be added here in the future.