Complexity of n-Queens Completion
Authors: Ian P. Gent, Christopher Jefferson, Peter Nightingale
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we present an empirical study of random n-Queens Completion, Blocked n-Queens, and Excluded Diagonals Problems in Section 5. 5. Empirical Study We have shown that n-Queens Completion and Blocked n-Queens are NP-Complete, but how hard are they to solve in practice? This is an important question given the repeated controversy surrounding the use of n-Queens as a benchmark problem discussed in Section 1. We first describe solvers based on three different technologies: a special purpose solver; a SAT solver; and a constraint solver. We describe methods of generating random benchmark instances of three problem classes: Blocked n-Queens, n-Queens Completion, and the Excluded Diagonals Problem (Problem 4). We looked for phase transitions (Hogg, Huberman, & Williams, 1996) between solvable and unsolvable instances, in common with other NP-Complete problems, for example Boolean satisfiability (SAT) (Mitchell, Selman, & Levesque, 1992; Achlioptas, 2009; Altarelli, Monasson, Semerjian, & Zamponi, 2009). It is common in NP-Complete problems to see that randomly generated instances are hardest at the transition from solvable to unsolvable instances (Cheeseman, Kanefsky, & Taylor, 1991; Mitchell et al., 1992; Gent, Mac Intyre, Prosser, & Walsh, 1995). We do see this pattern for every solver in two of our generators but not in the third: a straightforward generation method for n-Queens Completion appears unable to produce instances that are hard to solve using SAT. Experiments were performed on a 32-core AMD Opteron 6272 at 2.1 GHz with 256 GB RAM. Savile Row was executed in Open JDK Java 1.7.0_131 with the 64-bit server VM. For random instances, we solved 1000 randomly generated instances per data point, and solvers were allowed to run to completion. |
| Researcher Affiliation | Academia | Ian P. Gent EMAIL Christopher Jefferson EMAIL Peter Nightingale EMAIL School of Computer Science, University of St Andrews, St Andrews, Fife KY16 9SX, UK |
| Pseudocode | No | The paper describes algorithms and reductions in prose and mathematical notation (e.g., Definitions 5, 10, 16, 20, 24, 26, 27, 28, 31, and Lemmas and Theorems), but does not contain a dedicated pseudocode or algorithm block with structured steps. |
| Open Source Code | Yes | We have made available our code including the adapted version of Savile Row that we used,7 detailed results including some additional graphs,8 and experimental instances.9 7. https://ipg.host.cs.st-andrews.ac.uk/n-queens-completion-experiments-code.tgz |
| Open Datasets | Yes | The counting version of the problem, i.e. to determine how many solutions to n-Queens there are, is sequence A000170 of the Online Encyclopedia of Integer Sequences (Sloane, 2016). The sequence is currently known only to n = 27, for which the number of solutions is more than 2.34 1017. ... We have made available our code including the adapted version of Savile Row that we used, detailed results including some additional graphs, and experimental instances.9 ... 9. https://ipg.host.cs.st-andrews.ac.uk/n-queens-completion-experiments-instances.tgz |
| Dataset Splits | No | For random instances, we solved 1000 randomly generated instances per data point, and solvers were allowed to run to completion. The paper describes a generation methodology for random instances, not a split of a pre-existing dataset. |
| Hardware Specification | Yes | Experiments were performed on a 32-core AMD Opteron 6272 at 2.1 GHz with 256 GB RAM. |
| Software Dependencies | Yes | We use the SAT solver Lingeling (Järvisalo, Heule, & Biere, 2012)... The third approach uses the constraint solver Minion 1.8 (Gent et al., 2006), with a constraint model optimised by Savile Row 1.6.4 (Nightingale et al., 2017). Savile Row was executed in Open JDK Java 1.7.0_131 with the 64-bit server VM. |
| Experiment Setup | No | The paper describes general experimental methodology (e.g., generating instances, solving 1000 instances per data point, allowing solvers to run to completion) but does not provide specific hyperparameter values or model initialization details typically found in an experimental setup for learning models or similar. |