Counting Solutions (n-Queens Problem)

From Algorithm Wiki
Jump to navigation Jump to search


How many ways can one put $n$ queens on an $n \times n$ chessboard so that no two queens attack each other? In other words, how many points can be placed on an $n \times n$ grid so that no two are on the same row, column, or diagonal?

Related Problems

Related: Constructing Solutions, n-Queens Completion


$n$: number of queens, size of chessboard

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Naive Algorithm 1848 $O(n^n)$ $O(n)$ Exact Deterministic
Naive + 1 queen per row restriction 1850 $O(n!)$ $O(n)$ Exact Deterministic
Dijkstra 1972 $O(n!)$ $O(n)$ Exact Deterministic Time
Nauck 1850 $O(n!)$ Exact Deterministic
Gunther Determinants solution 1874 $O(n!)$ $O(n!)$ ? Exact Deterministic
Rivin, Zabih 1992 $O({8}^n*poly(n)$) $O({8}^n*n^{2})$ Exact Deterministic Time & Space

Time Complexity Graph

N-Queens Problem - Counting Solutions - Time.png