A lower bound for the $n$-queens problem

Zur Luria, Michael Simkin

The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an $n\times n$ chessboard. We present a simple two stage randomized algorithm to construct such configuratio…