Posted: September 13th, 2017

Computation and Complexity

Paper, Order, or Assignment Requirements

 

A SURVEY OF NP-COMPLETE PUZZLES

 

 

Graham Kendall                           Andrew Parkes                             Kristian Spoerer1

 

Nottingham, 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.

 

1. INTRODUCTION

 

This article provides a survey of puzzles that are contained in the set of those NP-Complete (Garey and Johnson, 1979) puzzles that have a single decision maker. We use the term puzzle to refer to single-player games which are enjoyable to play. By definition a puzzle should have a solution which (1) is aesthetically pleasing and (2) gives the user satisfaction in reaching it. We admit that this is rather a loose definition. A more formal definition is difficult as any other definition would only express our subjective view and would be open to debate. Therefore, we decided upon the above definition which captures our perception of a single player puzzle. We provide further comments in the conclusions. Puzzles have been the topic of artificial intelligence research for some time

(Robertson and Munro, 1978; Hearn, 2006) and this survey is intended to motivate further research in this area by providing a starting point for the interested researcher.

 

We discuss 24 puzzles presented in alphabetical order. Two puzzles (Rubik’s Cube and the Towers of Hanoi) are discussed separately. For each puzzle, a brief description of the rules and a reference to its complexity is provided. At the end of each puzzle description we summarize the decision problem that was used to prove its NP-Completeness. Note that some of the references are to URLs which suggests that there has been work

directed towards these puzzles, but the work has not been presented for scientific peer review. It is our hope that this article will start to address the small number of published works, by encouraging authors to submit their research to journals such as this.

 

A brief description of the puzzle is included so that the reader understands it. There is often a reference to some software so that the puzzle can be attempted which might give an appreciation of the subtleties involved. Furthermore, the reader might gain an insight into the similarities between these hard puzzles. For example, the implicit hidden constraints that are only revealed once a puzzle is attempted.

 

A brief outline of some of the work that has been published about each puzzle is also provided. These works tend to apply search algorithms (see, for example, Russell and Norvig (2003)) to the puzzles. We have not attempted to include all of the research for each puzzle. Our motivation for briefly outlining this research is to provide references to the texts that can be used as starting points for future work on these puzzles.

 

Erik Demaine has completed some work in the area of Combinatorial Games2. We would like to recommend this work where it details the complexity of some two-player games and also some single-player puzzles. This work can be regarded as an extension of Demaine’s (2001) survey of puzzles, and also an extension of Eppstein’s survey of puzzles3.

 

————————————————————————————————————————-

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

2See http://theory.lcs.mit.edu/˜edemaine/games/.

3See http://www.ics.uci.edu/˜eppstein/cgt/hard.html.

14 ICGA Journal March 2008

 

 

 

2. COMPUTATIONAL COMPLEXITY (this part it is the most important part for my assignment for both puzzles)

 

In this section, we provide an informal description of NP-Completeness. The treatment is informal by design as there are many other more formal treatments of this area, with Garey and Johnson (1979) being the classic text.

For the interested reader we refer to the seminal work by Stephen Cook (1971) and also his short article (Cook,1984) which provides an excellent discussion. In fact, the opening of the article succinctly shows the problem faced when considering computational complexity: “In general, it is much harder to find a solution to a problem than to recognize one when it is presented.”

 

We are concerned with decision problems. That is, those problems that can be answered by Yes or No. This might appear to be quite a restriction on the type of problems we can consider but, in fact, most problems can be reduced to a decision problem. For example, the intuitive way to consider the Travelling Salesman Problem (TSP) is to phrase it as “Given a TSP instance, return the shortest (optimal) route.” In fact, we can turn this into a decision problem by asking “Given a TSP instance, is there a tour of length L, or less?” and then we can keep reducing L until we receive a negative answer. More efficiently, we can carry out a binary search on L until we find the optimal solution.

 

The P (Polynomial) class of problems contain the decision problems that can be solved on a deterministic sequential machine in time that is polynomial to the size of the input. In some sense, these are seen as easy problems.

 

The NP (Non-deterministic Polynomial) class of problems are those problems that can have a correct solution verified in polynomial time. For example, for the TSP, once we are presented with a tour, it is easy to verify (in polynomial time) that the tour is of a given length. However, although the TSP (and all the problems in NP) can have a solution verified in polynomial time, nobody knows of any algorithm that can solve the problem in polynomial time. If we were able to show that P = NP (i.e., all NP problems can be solved in polynomial time), then we know that we can solve a wide range of difficult problems in polynomial time. NP problems are known as Non-deterministic Polynomial because if we had a non-deterministic machine, which was able to guess correctly at each decision point, it could solve the problem in polynomial time, which is the same as verifying the solution.

Showing that P = NP (or not) is one of the most important open questions in theoretical computer science and, in fact, is one of the seven most important problems across all of mathematics according to Devlin (2005). However, it is widely believed that P (not equal)= NP.

 

NP-Complete problems are considered to be the hardest problems in NP. The definition of an NP-Complete problem is that it is in NP and every other problem in NP is reducible to it. By reducible we mean that there is a polynomial time algorithm that can transform an instance of one problem to another. These properties mean that if we ever find an efficient (polynomial time) algorithm for any NP-Complete problem, then we have an efficient algorithm for solving all NP-Complete problems, as we have a way of transforming one problem instance to another, in polynomial time. To show that a problem is NP-Complete it is sufficient to show that it is in NP and can be transformed from another NP-Complete problem by a polynomial bounded algorithm.

 

 

Each of the 2 puzzles below have all been shown to be NP-Complete However, we should emphasize that any problem that has a finite problem space cannot be NP-Complete as we could solve the problem in constant time. For example, if we limit Cryptarithms (see below) to just the decimal digits then these instances are not themselves NP-Complete. Similarly, the 15-puzzle is not

NP-Complete but the generalization to the n-Puzzle is.

5.In the portfolio tasks you should write and answer the decision questions about Corral Puzzle (2 pages) Reference Kendall et. al. (2008).

 

You need to write about the games, how they work, what complexity class it is in and why. Remember the module is about Computation and Complexity, so that should be your focus.

                            

 

Corral Puzzle is played on an m×n grid. Some of the squares contain a number. The goal is to find a closed

4From Galaxy of Mahjongg 2, see http://www.greenstreetgames.com/

loop in the grid such that all of the numbered squares are inside the loop. In addition, for each of the numbered

squares, the number of squares inside the closed loop, that are either horizontally or vertically adjacent to it, must

equal that number. See Figure 2 for an example. Deciding the solvability of Corral Puzzle has been shown to be

NP-Complete by Friedman (2002a). This seems to be the only information about Corral Puzzle.

Figure 2: A Corral Puzzle instance and solution.

DECISION QUESTION (Friedman, 2002a): Does a given instance have a solution, that is, is it solvable?

 

References

Kendall G., Parkes A. and Spoerer K. (2008) A Survey of NP-Complete Puzzles, International Computer Games Association Journal (ICGA), 31(1), pages 13-34.