eight queens puzzle

(redirected from N-queens problem)
Also found in: Acronyms.

eight queens puzzle

(algorithm)
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 ?
Gu, "Efficient local search with conflict minimization: a case study of the n-queens problem," IEEE Transactions on Knowledge and Data Engineering, vol.
Macuk, "A neural network designed to solve the N-queens problem," Biological Cybernetics, vol.
Li, "A parallel algorithm for solving the n-queens problem based on inspired computational model," BioSystems, vol.
Muniyandi, "Accelerated execution of P systems with active membranes to solve the N-queens problem," Theoretical Computer Science, vol.
Tanik Different perspectives of the N-Queens problem", Proceeding CSC '92 Proceedings of the ACM annual conference on Communications 99 108 (1992).
Aliyazicioglu, "Linear congruence equations for the solutions of the N-queens problem," Information Processing Letters, vol.
Akbaripour, "Landscape analysis and efficient metaheuristics for solving the n-queens problem," Computational Optimization and Applications.
For this purpose, four different well-known combinatorial optimization problems have been used, the traveling salesman problem (TSP), the capacitated vehicle routing problem (CVRP), the N-queens problems (NQP), and the one-dimensional bin packing problem (BPP).
Since the min-conflicts approach "blew away" prior techniques on the benchmark n-queens problem by an over four orders of magnitude performance improvement, it clearly indicated a new focus for the field.