The n-queens problem

Thesis

The famous n-queens problem asks how many ways there are to place n queens on an n × n chessboard so that no two queens can attack one another. The toroidal n-queens problem asks the same question where the board is considered on the surface of the torus and was first studied by P´olya in 1918. Let Q(n) denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. P´olya showed that T(n) > 0 if and only if n ≡ 1, 5 mod 6 and much more recently, in 2017, Luria showed that T(n) ≤ ((1 + o(1))ne−3)n and conjectured equality when n ≡ 1, 5 mod 6. Our main result is a proof of this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n ≡ 1, 5 mod 6. Furthermore, we also show that Q(n) ≥ ((1 + o(1))ne−3)n for all n ∈ N which was independently proved by Luria and Simkin. Our result counts only those configurations with at most 12 queens attacking toroidally. Combined with our main result, this completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n). Our proof combines a random greedy algorithm to count ‘almost’ configurations with a complex absorbing strategy that uses ideas from the recently developed methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

Authors: Bowtell, C

• DOI: 10.5287/ora-rbbbkjepk
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English