Final Results
Slither Link Puzzler
Advisor: Sherri Goings
I. Background
One of my favorite logic puzzles is called Slitherlink (or sometimes loop-the-loop). Slitherlink is deceptive in that there are only a few simple rules, but finding a solution can be quite complex, and in fact has been proven to be NP-complete (Yato, 2000). The rules of Slitherlink are as follows:
1. The final solution must be a continuous line that does not cross itself.
2. Each numbered cell must have the given number of edges filled by the solution line.
3. Each puzzle should have a single unique solution.
Here is an example puzzle shown in its initial state, partially solved, and fully solved.
Many methods have been explored in Slitherlink to both solve and automatically generated puzzles, including rule-based systems, constraint logic programming, learning algorithms, and even evolutionary algorithms.
II. The Project
The goal of this project will be to implement and compare several of these methods to solve and generate Slitherlink puzzles. It will likely be useful to create a very simple visualization to see an algorithm solving a specific puzzle, or to see the puzzle that an algorithm creates, however the focus of this project will be the analysis of the algorithms themselves, not creating an app for the puzzle. The deliverables for this project will include a paper describing the methods used and comparing them in efficiency/effectiveness.
The outline of this project will be something like the following:
- Implement a brute-force Slitherlink puzzle solver. This will require choosing how to represent a given Slitherlink puzzle as well as a solution. A simple visualization may be useful.
- Design and implement several other methods of solving a given puzzle, and compare them in efficiency/success. You will likely use a hybrid for these methods where you use some algorithm to mostly solve the puzzle, and then brute force to complete the final bits.
- Design and implement one or more methods to automatically generate Slitherlink puzzles. Note that generating some puzzle is easy, however generating puzzles that have only one unique solution AND are interesting for a human to solve is difficult. This step will include exploring what makes a puzzle easy or hard to solve, and again comparing generating methods in terms of both efficiency and quality of puzzles created.
Further directions for this project could include generating puzzles for a specific user based on data from their previous puzzle solving. For example tailoring the difficulty of puzzles to the user's current solving ability, or determining the traits of puzzles the user enjoys most based on ratings and creating puzzles for them with those traits.
III. References
- Takayuki Yato. On the NP-completeness of the Slither Link Puzzle. IPSJ SiG Notes, AL 74:25-32, 2000. In Japanese.
IV. Recommended Experience
It would be useful to have taken algorithms and/or computability & complexity. Also for some of the more advanced methods any experience with AI or EvoComp would be beneficial.