n queen topics
Other themes
This page in another language

Other pages on the n queens problem, and some commentsWikipediaA good article is contained in Wikipedia or the German version of it. TU DresdenAlong 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 projectThere 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 32bit 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 solutionA 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 Queenplacements (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 discussionYou can find a lot of discussion under Heise message (in German) and under Discussion on Heise (in German).
More pagesMore pages will be added here in the future. 