n-Queens Completion (n-Queens Problem)

From Algorithm Wiki
Jump to navigation Jump to search


Given an $n \times n$ chessboard that already has $k$ queens on it, complete the board such that there are $n$ queens, all of which cannot attack each other.

Related Problems

Related: Counting Solutions, Constructing Solutions


$n$: size of chessboard

$k$: number of queens given

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Grigoryan 2018 $O(n)$ $O(n)$ error < 0.0001 and decreases with increasing n Randomized Time