A Polynomial Time Algorithm for the N-Queens Problem

E. El-Qawasmeh and K. Al-Noubani (Jordan)


. The n-queens problem, Backtracking, Linear.


This paper presents a fast algorithm for solving the n queens problem. The basic idea is that many cases can be solved using pre-computed solutions, while the remaining cases are solved by calling the Sosic algorithm [1]. The novelty of the paper is in the observation that these pre computable cases exhibit a modular nature, i.e. they can be applied to of the cases. The speedup for these cases is about 10 times faster than those solved using Sosic algorithm.

Important Links:

Go Back