Proposed by Ian Gent

Overview

The N-Queens Problem, [prob054], suffers from the problem that its complexity is trivial as a decision problem.
The Blocked n-Queens problems is a variant of N-Queens which has been proven to be NP-Complete as a decision problem and #P-Complete as a counting problem.

The Blocked $n$-Queens problem is a variant where, as well as $n$, the input contains a list of squares which are blocked. A solution to the problem is a solution to the $n$-Queens problem containing no queens on any of the blocked squares.

The Blocked $n$-Queens problem is closely related to n-Queens Completion Problem and Excluded Diagonals n-Queens Problem, [prob079].

Instances

Python generators are available to implement the model from the paper [nqueenscompletion]. Generator for random blocked n-Queens instances

Also provided are instances from the ASP Competitions (thanks to Martin Gebser for providing these.) Results of ASP solvers on those instances can be found at the 2007 ASP Competition and the 2009 ASP Competition pages.

References

The Blocked $n$-Queens problem was proposed by [blocked_queens] and used in ASP Competitions [asp_competition_07]. The problem was proved NP-Complete and #P-Complete by [nqueenscompletion], and the same paper introduced a generator of ranodm instances.