Construction Through Decomposition: A Linear Time Algorithm for the N-queens Problem
Bruce D. Abramson, Mordechai M. Yung · Korean Journal of Gastroenterology · 1984
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.