# The n-queens completion problem

arXiv: https://arxiv.org/abs/2111.11402 · HTML: https://mlsanity.com/paper/2111.11402/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 34 references that are in the map.
- First posted on arXiv 22 Nov 2021.

## Abstract (arXiv)

An n-queens configuration is a placement of n mutually non-attacking queens on an n× n chessboard. The n-queens completion problem, introduced by Nauck in 1850, is to decide whether a given partial configuration can be completed to an n-queens configuration. In this paper, we study an extremal aspect of this question, namely: how small must a partial configuration be so that a completion is always possible? We show that any placement of at most n/60 mutually non-attacking queens can be completed. We also provide partial configurations of roughly n/4 queens that cannot be completed, and formulate a number of interesting problems. Our proofs connect the queens problem to rainbow matchings in bipartite graphs and use probabilistic arguments together with linear programming duality.