Paper by Erik D. Demaine

Reference:

MIT Hardness Group, Josh Brunner, Erik D. Demaine, Timothy Gomez, Markus Hecher, and Meryl Zhang, “ETH Lower Bounds for n-Queens: Time Waits for Nobody”, in Proceedings of the 36th International Workshop on Combinatorial Algorithms (IWOCA 2025), Lecture Notes in Computer Science, volume 15885, Bozeman, MT, July 21–24, 2025, pages 287–301.

Abstract:

We develop lower bounds with often-matching exponential algorithms for several variants of the n-queens problem. In particular, we prove that placing n queens onto an n × n board with holes requires 2^Θ(n) time for both decision and counting, assuming the Exponential Time Hypothesis (ETH) and #ETH respectively. The same result extends to more general manifolds. If the n × n board has no holes, but some of the queens are already placed, then completing the placement of n queens is known to be NP-complete and #P-complete; we show that both versions require between 2^Ω(√n) and 2^O(n) time, again assuming (#)ETH.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 14 pages.

Availability:

The paper is available in PDF (420k).

See information on file formats.

[Google Scholar search]