Complexity of n-Queens Completion (Extended Abstract)

Ian P. Gent, Christopher Jefferson, Peter NightingaleIJCAI 2018 · DOI

TL;DR

This paper proves that the n-Queens Completion problem, a classic puzzle variant where some queens are pre-placed, is NP-Complete and #P-Complete. This provides a theoretically sound and empirically challenging benchmark for AI, addressing long-standing debates about the suitability of the n-Queens problem for AI research.

What Problem Does This Paper Address?

The n-Queens problem, a well-known puzzle where you place n queens on an n x n chessboard so no two queens attack each other, has been a popular benchmark in Artificial Intelligence for decades. However, the decision version of the standard n-Queens problem is trivial (a solution exists for all n > 3), leading to debates about its usefulness as a benchmark. This paper tackles the n-Queens Completion problem, a variant where some queens are already placed, and the task is to place the remaining queens. The authors aim to establish the computational complexity of this variant and explore its potential as a more robust AI benchmark. They also introduce related problems like "Blocked n-Queens" and "Excluded Diagonals Problem" for benchmarking.

Methods

The core of the paper's contribution lies in its theoretical analysis of the n-Queens Completion problem. The authors employ polynomial reductions to prove its complexity. Specifically, they demonstrate that n-Queens Completion is NP-Complete by reducing a known NP-Complete problem to it. They also show it is #P-Complete, which relates to counting the number of solutions. Beyond theoretical proofs, the paper describes the implementation of generators for random instances of these problems and three solvers. They then conduct an empirical analysis of the hardness of these randomly generated instances.

Datasets

The paper does not discuss specific pre-existing datasets for training or evaluation. Instead, it introduces newly generated random instances for the n-Queens Completion, Blocked n-Queens, and Excluded Diagonals problems. These generators are designed to explore the phase transitions associated with hard instances in some of these problems.

Key Insights and Ideas

  • Formalizing a Classic Puzzle: The paper provides a rigorous complexity-theoretic foundation for the n-Queens Completion problem, moving it beyond a mere puzzle to a formally defined computational problem.
  • Resolving Benchmark Debates: By proving n-Queens Completion is NP-Complete and #P-Complete, the authors offer a strong argument for its use as a challenging and theoretically sound benchmark in AI, addressing criticisms of the original n-Queens problem.
  • Phase Transitions in Hardness: The research reveals that for related problems like Blocked n-Queens and Excluded Diagonals, there's a "phase transition" where instances suddenly become much harder to solve as parameters change. This is a common phenomenon in NP-Complete problems and is valuable for understanding problem difficulty.
  • Generator Design Matters: The authors found that a "natural" generator for n-Queens Completion didn't consistently produce hard instances, highlighting the importance of careful generator design for creating challenging benchmarks.

Key Results

  • The n-Queens Completion problem is proven to be NP-Complete.
  • The n-Queens Completion problem is also proven to be #P-Complete.
  • As a corollary, the Blocked n-Queens problem is also shown to be NP-Complete and #P-Complete.
  • Empirical analysis showed the existence of phase transitions associated with hard instances for the Blocked n-Queens and Excluded Diagonals problems.
  • A natural generator for n-Queens Completion did not consistently produce hard instances.

Limitations and Future Work

The paper acknowledges that a "natural" generator for n-Queens Completion did not yield consistently hard instances, suggesting that further work is needed to develop generators that effectively produce challenging problems for this specific variant. The authors also mention that their work provides a foundation for exploring alternative benchmarks that are theoretically hard and empirically challenging, implying that further investigation into the practical performance of various AI techniques on these new benchmarks would be a valuable next step.

Summary updated

BibTeX
@inproceedings{gent2018complexity,
  author = {Ian P. Gent and Christopher Jefferson and Peter Nightingale},
  title = {{Complexity of n-Queens Completion (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/794},
}
Figure