On the Complexity of a Derivative Chess Problem

2007/01/08 by Barnaby Martin, Martin, Barnaby
Computer Science · Decision Sciences · Physics and Astronomy · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Game Theory and Applications #Quantum chaos and dynamical systems

paper · pdf · doi:10.48550/arxiv.cs/0701049

openalex publication_date 2007/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce QUEENS, a derivative chess problem based on the classical n-queens problem. We prove that QUEENS is NP-complete, with respect to polynomial-time reductions.

Citations

• A linear algorithm for embedding planar graphs using PQ-trees

Related

• Linear algorithm for solution n-Queens Completion problem
• The n-queens completion problem
• New explicit solution to the N-Queens Problem and its relation to the Millennium Problem
• Finding First and Most-Beautiful Queens by Integer Programming
• A lower bound for the n-queens problem