1984 Reports
Construction Through Decomposition: A Linear Time Algorithm for the N-queens Problem
Configuring N mutually non-attacking queens on an N-by-N chessboard is a contemporary problem that was first posed over a century ago. Over the past few decades, this problem has become important to computer scientists by serving as the standard example of backtracking search methods. A related problem, placing the N queens on a toroidal board, has been discussed in detail by Polya and Chandra, Their work focused on characterizing the solvable cases and finding regular solutions, board setups that solve the problem while arranging the queens in a regular pattern. This paper describes a new linear time divide-and-conquer algorithm that solves both problems. When applied to the toroidal problem, the algorithm yields a family of non-regular solutions based on number factorization. These solutions, in turn, can be modified to solve the standard N-queens problem for board sizes which are unsolvable on a torus.
Subjects
Files
- CUCS-129-84.pdf application/pdf 998 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-129-84
- Published Here
- August 7, 2013