Slitherlink Comps Project Page

GOAL

Our project was to create a solver for Slitherlink puzzles, as well as a generator for Slitherlink puzzles that generate puzzles of various difficulty with unique solutions.

Solving a Slitherlink puzzle is an NP-hard problem, and verifying that a Slitherlink puzzle has only one solution is an NP-hard problem. As such, we focused our algorithms to be able to quickly create and solve puzzles that people typically create and solve.

A SLITHERLINK PUZZLE

According to Wikipedia, "Slitherlink (also known as Fences, Takegaki, Loop the Loop, Loopy, Ouroboros, Suriza and Dotty Dilemma) is a logic puzzle developed by publisher Nikoli."

Wikipedia Page on Slitherlink

Slitherlink is a rectangular lattice of dots, creating square "cells". Some cells have numbers in them. To solve a slitherlink puzzle, a single loop must be made such that each cell has exactly the number of sides in the loop as the number in the cell, if the cell has a number. The loop cannot intersect itself.

(Images from puzzle-loop.com)

If you want to solve some puzzles: Puzzle Loop Website

If you want help with solving puzzles: Puzzle Loop Slitherlink Guide

SOLVER

We implemented our version of a solver in C++. Our solver begins by applying all the simple “rules” for the puzzle in each possible spot until no more rules can be applied. Once no more rules can be applied, for each empty edge in the grid we guess whether that edge is a line or an “x” (which means that no line can exist in that spot). If one of these guesses leads to a contradiction in the puzzle (e.g. the loop intersects itself), we know that the opposite guess has to be true. Once we learn information from a guess, we try to apply the rules again until we can’t apply rules anymore. Once we get to a state where we can’t apply rules and no new information can be learned from one-edge guesses, we start to recursively nest guesses, using iterative deepening to increase the max number of guesses in a row. By the time our solver finds a solution to a puzzle, it is likely that we needed to make a guess or two to get to that state in the grid. To ensure there is only one solution, we simply try to solve the puzzle using the opposite of those guesses, and if we come to contradictions for every opposite guess we know that the solution we found is the only one.

GENERATOR

To generate puzzles we first create a loop using a random process. As long as two rules are followed, we can use a greedy algorithm that is able to generate all valid loops. This can be modified to generate more satisfying loops that fill up the puzzle. After generating a loop, we populate the puzzle with numbers based on the loop. Lastly, we iteratively delete numbers from the puzzle until we have deleted a satisfactory percentage of the numbers and make sure that no number deletion creates a puzzle that is either too hard or has multiple solutions. We can make a puzzle easier by deleting only half of the numbers, pretending we know fewer rules, limiting the depth of the guessing to 1, and maintaining an approximate ratio of '1's to '2's and '2's to '3's in the puzzle.

A more detailed run through of our algorithms are outlined in this presentation.

RESULTS

Below is a Slitherlink puzzle that our algorithm generated (in 4.275 seconds). Try it out!

REFERENCES:

On the NP-completeness of the Slither Link Puzzle. Takayuki Yato.

Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs. Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita and Shin-ichi Minato.

A rule-based approach to the puzzle of Slither Link. Stefan Herting.

Puzzles and Games: A Mathematical Modeling Approach. Tony Hürlimann, 2015

Solving logical puzzles using mathematical models. KVIS Susanti, S Lukas.