Slitherlink Solver (#159)

Slitherlink is a neat puz­zle in which you are presented with a num­ber matrix and the goal is to draw one connected, not interlooping line in be­tween the cells. The num­ber in each cell determines exactly how many line segments must be drawn around each cell (0, 1, 2 or 3). When a cell does not con­tain any num­ber, the num­ber of line segments adjacent to this cell are unrestricted.

*  *  *  *  *  *          *--*  *  *--*--*
     2  1  3              |  | 2  1| 3   |
*  *  *  *  *  *          *  *--*  *--*  *
        2  2  2           |     | 2  2| 2|
*  *  *  *  *  *          *--*  *--*  *  *
     2              ->       | 2   |  |  |
*  *  *  *  *  *          *  *--*  *--*  *
  1  3  1     1             1  3| 1     1|
*  *  *  *  *  *          *--*--*  *--*  *
  3     2     3           | 3     2|  | 3|
*  *  *  *  *  *          *--*--*--*  *--*

A sample 5x5 Slitherlink with solution.

Slitherlink was invented by the Japanese publisher Nikoli in 1989. It has many oth­er names than “Slitherlink”, yet I prefer this descriptive name. Imagining a snake slithering along the board, seeking to link up with itself is a bit charming.

As with most of these puzzles that have simple rules and are fairly easy to work out by hand — on small scales that is —, writ­ing a solver for them can prove to be more difficult than one may ex­pect.

The first solving strat­e­gy I tried out was to brute force the prob­lem. Using the Slitherlink from above as an example, there would be dif­fer­ent cells with line segments. With each line segment ei­ther being drawn or not, there are dif­fer­ent boards to check. With one board being checked per nanosecond the solver would take seconds or 36.56 years. Brute force is definitely not a viable way to conquer Slitherlink.

After this harsh discovery, I needed a better way to ap­proach solving a given Slitherlink puz­zle. Doing some research, I even discovered that Slitherlink is an NP-com­plete prob­lem (see this paper⁠¹ by Stefan Herting), whereby it — assuming — is not even possible to write a solving algorithm which takes polynomial time.
How­ev­er, solving small Slitherlink puzzles is fortunately possible in a rea­son­able time frame.

The strat­e­gy I used in the solver consists of pre-programmed rules — figured out by humans — which de­ter­mine parts of the board based on special arrangements and enforcing the puz­zle’s rules (such as that there must on­ly be one line). Using those clues, the solver partly solves a given Slitherlink until there are no more known rules to advance. At that point the solver guesses for a given line segment to be ei­ther crossed (marking it cannot be drawn) or drawn, building a tree.
Conflicting attempts (where the solver wrongly guessed, then later — through applying the given rules — determines the at­tempt as flawed) are thrown away, on­ly leaving possible solved scenarios. Because each Slitherlink has one unique solution, this process ultimately results in one surviving at­tempt, which then is checked for cor­rect­ness and printed out as the solution.
A list of Slitherlink rules can be found in this Wiki­pe­dia article.

Using the above described meth­od, my solver takes roughly 0.05 seconds on an Intel Core i7 (4.00 GHz) to solve the example 5 ⨉ 5 Slitherlink. A 10 ⨉ 10 Slitherlink takes around 1.6 seconds where­as it takes 32 seconds to solve a 15 ⨉ 15 Slitherlink. The non-polynomial time is clear­ly recognisable.⁠²

My solver best runs in a bash shell⁠³, as it uses ANSI escape sequences to give the solved line a vivid blue and is entirely writ­ten in Python as well as fully text-based. The source code is listed below.

Oth­er people also have writ­ten solvers, including puz­zle generators, such as kakuro-online or appspot. The latter even supports dif­fer­ent polygons as the Slitherlink base.

Source code: slitherlink-solver.py