A SURVEY OF NP-COMPLETE PUZZLES

Article type: Research Article

Authors: Kendall, Graham¹ | Parkes, Andrew | Spoerer, Kristian

Affiliations: Nottingham, UK

Note: [1] School of Computer Science, University of Nottingham, Nottingham NG8 IBB, UK. Email: {gxk,ajp,kts}@cs.nott.ac.uk

Abstract: Single-player games (often called puzzles) have received considerable attention from the scientific community. Consequently, interesting insights into some puzzles, and into the approaches for solving them, have emerged. However, many puzzles have been neglected, possibly because they are unknown to many people. In this article, we survey NP-Complete puzzles in the hope of motivating further research in this fascinating area, particularly for those puzzles which have received little scientific attention to date.

DOI: 10.3233/ICG-2008-31103

Journal: ICGA Journal, vol. 31, no. 1, pp. 13-34, 2008