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 problemthan 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 Puzzleis 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.
Order Now
https://thecustomwritings.com/order/
YOU CAN ALSO PLACE OTHER SIMILAR ORDERS ON OUR WEBSITE AND GET AMAZING DISCOUNTS!!!
Our Service Charter
-
Excellent Quality / 100% Plagiarism-Free
We employ a number of measures to ensure top quality essays. The papers go through a system of quality control prior to delivery. We run plagiarism checks on each paper to ensure that they will be 100% plagiarism-free. So, only clean copies hit customers’ emails. We also never resell the papers completed by our writers. So, once it is checked using a plagiarism checker, the paper will be unique. Speaking of the academic writing standards, we will stick to the assignment brief given by the customer and assign the perfect writer. By saying “the perfect writer” we mean the one having an academic degree in the customer’s study field and positive feedback from other customers. -
Free Revisions
We keep the quality bar of all papers high. But in case you need some extra brilliance to the paper, here’s what to do. First of all, you can choose a top writer. It means that we will assign an expert with a degree in your subject. And secondly, you can rely on our editing services. Our editors will revise your papers, checking whether or not they comply with high standards of academic writing. In addition, editing entails adjusting content if it’s off the topic, adding more sources, refining the language style, and making sure the referencing style is followed. -
Confidentiality / 100% No Disclosure
We make sure that clients’ personal data remains confidential and is not exploited for any purposes beyond those related to our services. We only ask you to provide us with the information that is required to produce the paper according to your writing needs. Please note that the payment info is protected as well. Feel free to refer to the support team for more information about our payment methods. The fact that you used our service is kept secret due to the advanced security standards. So, you can be sure that no one will find out that you got a paper from our writing service. -
Money Back Guarantee
If the writer doesn’t address all the questions on your assignment brief or the delivered paper appears to be off the topic, you can ask for a refund. Or, if it is applicable, you can opt in for free revision within 14-30 days, depending on your paper’s length. The revision or refund request should be sent within 14 days after delivery. The customer gets 100% money-back in case they haven't downloaded the paper. All approved refunds will be returned to the customer’s credit card or Bonus Balance in a form of store credit. Take a note that we will send an extra compensation if the customers goes with a store credit. -
24/7 Customer Support
We have a support team working 24/7 ready to give your issue concerning the order their immediate attention. If you have any questions about the ordering process, communication with the writer, payment options, feel free to join live chat. Be sure to get a fast response. They can also give you the exact price quote, taking into account the timing, desired academic level of the paper, and the number of pages.