2022/07/06 by Stefan Glock, David Munhá Correia, Benny Sudakov · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #graph theory and CDMA systems
paper · pdf · doi:10.1007/s40687-022-00335-1
openalex created_date 2021/12/06 · openalex publication_date 2022/07/06 · openalex updated_date 2026/08/01
Abstract An n -queens configuration is a placement of n mutually non-attacking queens on an n× n <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> 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.