eight queens puzzle

(redirected from N-queens)

eight queens puzzle

A puzzle in which one has to place eight queens on a chessboard such that no queen is attacking any other, i.e. no two queens occupy the same row, column or diagonal. One may have to produce all possible such configurations or just one.

It is a common students assignment to devise a program to solve the eight queens puzzle. The brute force algorithm tries all 64*63*62*61*60*59*58*57 = 178,462,987,637,760 possible layouts of eight pieces on a chessboard to see which ones meet the criterion. More intelligent algorithms use the fact that there are only ten positions for the first queen that are not reflections of each other, and that the first queen leaves at most 42 safe squares, giving only 10*42*41*40*39*38*37*36 = 1,359,707,731,200 layouts to try, and so on.

The puzzle may be varied with different number of pieces and different size boards.

References in periodicals archive ?
It also provides comprehensive coverage of recursion, which includes problems on list manipulation, Tower of Hanoi, permutation generation, n-queens' problem, Sudoku and plotting Hilbert curves.
In this activity we cover Hamming Distance and its use in information theory and we cover N-Queens problem and its use in computer science.
Previous researches have been trying to find the domination number [gamma](Qn) for the n-queens problem using mathematical and combinatorial approaches [1-8].
Ruggiero, "The n-queens problem," INFORMS Transactions on Education, vol.
A number of techniques have been developed for solving N-queens chessboard problem.
Batouche, A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem" The International Arab Journal of Information Technology, 7(1): 21-28 (2010).
The team also applied their method to a classic benchmark constraint satisfaction problem, the n-queens problem (where the goal is to place n queens on an n x n chessboard so that none attack any other).
That system performed even better than the original GDS scheduler/constraint satisfaction system (on the n-queens problem where GDS was able to solve 1 thousand queens problems in 11 minutes, the new min-conflicts systems solved 1 million queens in less than 4 (using comparable computational resources).
Due space reasons we show only experimental results measured in number of backtracks but the conclusion is the same using other performance metrics (nodes visited, time): for each problem the dynamic approach gains very good position in the global ranking (it was the best for N-Queens n=8; the second for N-Queens n=16, N-Queens n=20 and Magic Square n=3; and rank fourth for Magic Square n=4).
Number of Backtracks solving N-Queens (NQ) and Magic Square (MS) with different strategies Strategy NQ n=8 NQ n=16 NQ n=20 MS n=3 MS n=4 F + ID 10 542 10026 0 12 F + IDM 11 542 10026 1 51 MRV + ID 10 3 11 0 3 MRV + IDM 10 3 11 1 97 AMRV + ID 11 517 2539 4 1191 AMRV + IDM 11 517 2539 0 42 O + ID 10 542 10026 0 10 O + IDM 10 542 10026 1 29 Dynamic 6 404 629 1 23
For example, there are several orders of magnitude between the first and first- fail pure strategies in the n-queens problem.