A lower bound for the n-queens problem

MaRDI QIDQ6368407zbMATH OpenFDO

Authors Zur Luria, Michael Simkin

Publication date 24 May 2021

Abstract: The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an $nimesn$ chessboard. We present a simple two stage randomized algorithm to construct such configurations. In the first stage, a random greedy algorithm constructs an approximate extit{toroidal} $n$-queens configuration. In this well-known variant the diagonals wrap around the board from left to right and from top to bottom. We show that with high probability this algorithm succeeds in placing $(1-o(1))n$ queens on the board. In the second stage, the method of absorbers is used to obtain a complete solution to the non-toroidal problem. By counting the number of choices available at each step of the random greedy algorithm we conclude that there are more than $left(left(1-o(1)ight)n{e}^{-3}ight{)}^n$ solutions to the $n$-queens problem. This proves a conjecture of Rivin, Vardi, and Zimmerman in a strong form.

This page was built for publication: A lower bound for the $n$-queens problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368407)