New bounds on the number of n-queens configurations

2017/05/15 by Zur Luria, Luria, Zur · 3 citations
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Advanced Combinatorial Mathematics #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1705.05225

Abstract

In how many ways can n queens be placed on an n × n chessboard so that no two queens attack each other? This is the famous n-queens problem. Let Q(n) denote the number of such configurations, and let T(n) be the number of configurations on a toroidal chessboard. We show that for every n of the form 4^k+1, T(n) and Q(n) are both at least n^Ω(n). This result confirms a conjecture of Rivin, Vardi and Zimmerman for these values of n. We also present new upper bounds on T(n) and Q(n) using the entropy method, and conjecture that in the case of T(n) the bound is asymptotically tight. Along the way, we prove an upper bound on the number of perfect matchings in regular hypergraphs, which may be of independent interest.

Cited by

• Entropy methods in combinatorics
• Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs
• The existence of designs II

Related

• The n-queens problem
• A lower bound for the n-queens problem
• The n-queens completion problem
• The number of n-queens configurations
• Improved lower bounds for Queen's Domination via an exactly-solvable relaxation