Slitherlink is a neat puzzle in which you are presented with a number matrix and the goal is to draw one connected, not interlooping line in between the cells. The number 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 contain any number, the number 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 other 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 –, writing a solver for them can prove to be more difficult than one may expect.

The first solving strategy I tried out was to brute force the problem. Using the Slitherlink from above as an example, there would be $5 \cdot 5 = 25$ different cells with $2 \cdot 5 \cdot 5 + 5 + 5 = 60$ line segments. With each line segment either being drawn or not, there are $2^{60} = 1.15 \cdot 10^{18}$ different boards to check. With one board being checked per nanosecond the solver would take $\frac{2^{60}}{10^9} = 1.15 \cdot 10^9$ 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 approach solving a given Slitherlink puzzle. Doing some research, I even discovered that Slitherlink is an NP-complete problem (see this paper [Update 29th of January 2019: The link appears to be dead; I was able to find two mirrors: labri.fr and docplayer.net.] by Stefan Herting), whereby it — assuming $\text{P} \neq \text{NP}$ — is not even possible to write a solving algorithm which takes polynomial time.
However, solving small Slitherlink puzzles is fortunately possible in a reasonable time frame.

The strategy I used in the solver consists of pre-programmed rules — figured out by humans — which determine parts of the board based on special arrangements and enforcing the puzzle’s rules (such as that there must only 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 either 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 attempt as flawed) are thrown away, only leaving possible solved scenarios. Because each Slitherlink has one unique solution, this process ultimately results in one surviving attempt, which then is checked for correctness and printed out as the solution.
A list of Slitherlink rules can be found in this Wikipedia article.

Using the above described method, 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 whereas it takes 32 seconds to solve a 15×15 Slitherlink. The non-polynomial time is clearly 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 written in Python as well as fully text-based. The source code is listed below.

Other people also have written solvers, including puzzle generators, such as kakuro-online or appspot. The latter even supports different polygons as the Slitherlink base.

# Python 2.7.7 Code
# Jonathan Frech, 22nd of December 2016
# edited 23rd, 24th, 25th, 26th, 27th, 29th, 30th, 31st of December 2016
# edited 1st, 2nd, 3rd, 5th, 8th of January 2017
# edited 10th of February 2017

# import
import copy, time, sys

# data
data00 = ("1 31 3", "   3  ", " 3 21 ", " 02 1 ", "  2   ", "2 23 3")
data01 = (" 213 ", "  222", " 2   ", "131 1", "3 2 3")
data02 = ("  3 3  3", "1  31  1", "1     22", "2  1    ", "    3  3", "20     1", "2  02  2", "2  3 3  ")
data03 = ("    0 ", "33  1 ", "  12  ", "  20  ", " 1  11", " 2    ")
data04 = ("323  ", "  2  ", "2 22 ", "   32", "3 23 ")
data05 = ("0232", "   2", "   2", " 33 ")
data06 = ("  3 3 2   ", "2    13 3 ", "2  2   2 2", "3 20 2 33 ", " 3 2 3   2", " 21 3 3  1", "23     1 2", "   22 23 3", "2212   2  ", "3 3   3223")
data07 = ("3223 3", "2   21", "22 133", "023 22", "13   2", "0 2212")
data08 = (" 22 3", "201 1", "2 3 2", " 2232", "32 1 ")
data09 = ("1 2 3 ", "2 21  ", "  13 2", "  1   ", "21 21 ", "   10 ")
data10 = ("11 12 ", "    2 ", " 22 13", " 3  1 ", "12 0 3", "  12  ")
data11 = ("23   0", "   0  ", " 1   2", "3 3  2", "   02 ", " 0   0")
data12 = ("   22  2  ", " 32 3 1  3", " 02 2 2202", "3     2  3", "  123 2  2", "3     1   ", "3 3 3 3 1 ", "      1 12", "12      0 ", "3 1  31 2 ")
data13 = ("1 221 3", "    1  ", "12  2  ", "21  33 ", "  1  1 ", "  3  0 ", "0 3  3 ")
data14 = ("     2  2 ", " 32 2 2   ", "3 322 1  3", "202   3   ", "   2303222", "  2   3222", " 3 22  21 ", "12  2  21 ", "   23   11", " 1 23 212 ")
data15 = (" 2333   3   3 3", " 1   2 1  2 2  ", "  1 21122 2   2", " 213 0  33   2 ", "   2  2  123 0 ", "3 2 1       0  ", "22123  2  3 123", "2   2 22 1 2 11", "   2131        ", "2 2    3 33232 ", "33 211        1", " 2 2 2313 11 2 ", "  32  222 2 321", "211 2 2 1  11  ", "  13  3 2     1")
data16 = ("0123 3 ", " 3   1 ", "  13 1 ", " 2  10 ", " 01   1", "3   212", "  1    ")
data17 = ("1   1 022 ", "  2 212  2", "1  1    32", "1  112    ", " 0 3  2  3", "  0   22  ", "3  13 30  ", "  0    102", "1  11222  ", " 11     32")
data18 = ("  32  ", "3   03", " 11 12", "      ", "2 21  ", "0   0 ")
data19 = (" 21 3", "  122", "1 2 0", "22 0 ", "3 0  ")

# chech if data is valid
def checkdata():
global data, w, h

# select data
data = data15

# there needs to be some data
if len(data) <= 0 or len(data) <= 0:
return False

# determine width and height
w, h = len(data), len(data)

# check every line for its length and characters
for y in range(h):
if len(data[y]) != w:
print "Incorrect data width in line %d." % y
return False
else:
for x in range(w):
if data[y][x] not in (" ", "0", "1", "2", "3"):
print "Unknown character '%s' in line %d, row %d." % (data[y][x], y, x)
return False

# slither should not be too small
if w < 4 or h < 4:
print "Slither too small, solve it yourself!"
return False

# data was checked
return True

# tile class
class tile():
# init
def __init__(self, x, y):
# value
self.value = data[y][x]

# surrounding lines
self.top    = 0
self.right  = 0
self.bottom = 0
self.left   = 0

# get value
def getvalue(self):
return self.value

# get side
def get(self, direction):
if direction == "top":
return self.top
elif direction == "right":
return self.right
elif direction == "bottom":
return self.bottom
elif direction == "left":
return self.left

# set side
def set(self, direction, value):
if direction == "top":
self.top = value
elif direction == "right":
self.right = value
elif direction == "bottom":
self.bottom = value
elif direction == "left":
self.left = value

# slither class
class Slither():
# init
def __init__(self):
# data
self.data = []
for y in range(h):
d = []
for x in range(w):
d.append(tile(x, y))
self.data.append(d)

# error variable
self.error = False

# find links until there is nothing more to find
id = -1
while id != self.getidentifier() and not self.error:
id = self.getidentifier()

# check loops
self.getloops()

# status message
def statusmessage(self, active):
# get known
known = 0
for x in range(w):
for y in range(h):
for _ in ("top", "right", "bottom", "left"):
if self.get(x, y, _) != 0:
known += 1

# write
sys.stdout.write("\r\033[KSolving... (%d%% known, %d active)" % ((100 * known // (4*w*h)), active))
sys.stdout.flush()

# generate guesses (possible versions, altered at one line)
def guess(self):
# look for unknown segment, set it
for y in range(h):
for x in range(w):
for d in ("top", "right", "bottom", "left"):
if self.get(x, y, d) == 0:
C = []
for _ in (1, -1):
c = copy.deepcopy(self)
c.set(x, y, d, _)
if not c.error:
C.append(c)
return C

# a solution was found
SOLUTIONS.append(self)

# nothing to guess, it's a solution!
return []

# loop through field
for x in range(-1, w+1):
for y in range(-1, h+1):
# a 0
if self.getvalue(x, y) == "0":
self.set(x, y, "top", -1)
self.set(x, y, "right", -1)
self.set(x, y, "bottom", -1)
self.set(x, y, "left", -1)

if self.getvalue(x, y) == "3":
# diagonal
if self.getvalue(x+1, y+1) == "3":
self.set(x, y, "top", 1)
self.set(x, y, "left", 1)
self.set(x+1, y+1, "right", 1)
self.set(x+1, y+1, "bottom", 1)
if self.getvalue(x+1, y-1) == "3":
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
self.set(x+1, y-1, "top", 1)
self.set(x+1, y-1, "right", 1)

# straight
if self.getvalue(x+1, y) == "3":
self.set(x, y, "left", 1)
self.set(x, y, "right", 1)
self.set(x+1, y, "right", 1)
self.set(x, y-1, "right", -1)
self.set(x, y+1, "right", -1)
if self.getvalue(x, y+1) == "3":
self.set(x, y, "top", 1)
self.set(x, y, "bottom", 1)
self.set(x, y+1, "bottom", 1)
self.set(x-1, y, "bottom", -1)
self.set(x+1, y, "bottom", -1)

# a 3, 2*, 3 diagonally (really, any number of 2's can seperate the 3's)
X, Y = x+1, y+1
while self.getvalue(X, Y) == "2":
X += 1
Y += 1
if self.getvalue(X, Y) == "3":
self.set(x, y, "top", 1)
self.set(x, y, "left", 1)
self.set(X, Y, "right", 1)
self.set(X, Y, "bottom", 1)
X, Y = x+1, y-1
while self.getvalue(X, Y) == "2":
X += 1
Y -= 1
if self.getvalue(X, Y) == "3":
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
self.set(X, Y, "top", 1)
self.set(X, Y, "right", 1)

# a 3 or 1 in a corner
n = (None, "3", "1")
for _ in (1, -1):
if self.getvalue(0, 0) == n[_]:
self.set(0, 0, "top", _)
self.set(0, 0, "left", _)
if self.getvalue(w-1, 0) == n[_]:
self.set(w-1, 0, "top", _)
self.set(w-1, 0, "right", _)
if self.getvalue(0, h-1) == n[_]:
self.set(0, h-1, "bottom", _)
self.set(0, h-1, "left", _)
if self.getvalue(w-1, h-1) == n[_]:
self.set(w-1, h-1, "right", _)
self.set(w-1, h-1, "bottom", _)

# a 2 in a corner
if self.getvalue(0, 0) == "2":
self.set(0, 1, "left", 1)
self.set(1, 0, "top", 1)
if self.getvalue(w-1, 0) == "2":
self.set(w-2, 0, "top", 1)
self.set(w-1, 1, "right", 1)
if self.getvalue(0, h-1) == "2":
self.set(1, h-1, "bottom", 1)
self.set(0, h-2, "left", 1)
if self.getvalue(w-1, h-1) == "2":
self.set(w-2, h-1, "bottom", 1)
self.set(w-1, h-2, "right", 1)

if self.error:
return

# loop through
for x in range(-1, w+1):
for y in range(-1, h+1):
# 1's
if self.getvalue(x, y) == "1":
# one marked
if self.get(x, y, "top") == 1:
self.set(x, y, "right", -1)
self.set(x, y, "bottom", -1)
self.set(x, y, "left", -1)
if self.get(x, y, "right") == 1:
self.set(x, y, "bottom", -1)
self.set(x, y, "left", -1)
self.set(x, y, "top", -1)
if self.get(x, y, "bottom") == 1:
self.set(x, y, "left", -1)
self.set(x, y, "top", -1)
self.set(x, y, "right", -1)
if self.get(x, y, "left") == 1:
self.set(x, y, "top", -1)
self.set(x, y, "right", -1)
self.set(x, y, "bottom", -1)

# three x'd -> mark the other one
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
self.set(x, y, "top", 1)
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1 and self.get(x, y, "top") == -1:
self.set(x, y, "right", 1)
if self.get(x, y, "left") == -1 and self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
self.set(x, y, "bottom", 1)
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
self.set(x, y, "left", 1)

# a line running into a 1 and an x'd one -> opposite lines get x'd
if (self.get(x-1, y-1, "right") == 1 and self.get(x-1, y-1, "bottom") == -1) or (self.get(x-1, y-1, "bottom") == 1 and self.get(x-1, y-1, "right") == -1):
self.set(x, y, "right", -1)
self.set(x, y, "bottom", -1)

if (self.get(x+1, y-1, "bottom") == 1 and self.get(x+1, y-1, "left") == -1) or (self.get(x+1, y-1, "left") == 1 and self.get(x+1, y-1, "bottom") == -1):
self.set(x, y, "bottom", -1)
self.set(x, y, "left", -1)

if (self.get(x+1, y+1, "left") == 1 and self.get(x+1, y+1, "top") == -1) or (self.get(x+1, y+1, "top") == 1 and self.get(x+1, y+1, "left") == -1):
self.set(x, y, "left", -1)
self.set(x, y, "top", -1)

if (self.get(x-1, y+1, "top") == 1 and self.get(x-1, y+1, "right") == -1) or (self.get(x-1, y+1, "right") == 1 and self.get(x-1, y+1, "top") == -1):
self.set(x, y, "top", -1)
self.set(x, y, "right", -1)

if self.getvalue(x+1, y+1) == "1":
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
self.set(x+1, y+1, "top", -1)
self.set(x+1, y+1, "left", -1)
if self.get(x, y, "top") == -1 and self.get(x, y, "left") == -1:
self.set(x+1, y+1, "right", -1)
self.set(x+1, y+1, "bottom", -1)
if self.getvalue(x+1, y-1) == "1":
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
self.set(x+1, y-1, "bottom", -1)
self.set(x+1, y-1, "left", -1)
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
self.set(x+1, y-1, "top", -1)
self.set(x+1, y-1, "right", -1)

# a 1 and a 3 diagonally
if self.getvalue(x+1, y-1) == "3":
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
self.set(x+1, y-1, "top", 1)
self.set(x+1, y-1, "right", 1)
if self.getvalue(x+1, y+1) == "3":
if self.get(x, y, "top") == -1 and self.get(x, y, "left") == -1:
self.set(x+1, y+1, "right", 1)
self.set(x+1, y+1, "bottom", 1)
if self.getvalue(x-1, y+1) == "3":
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
self.set(x-1, y+1, "bottom", 1)
self.set(x-1, y+1, "left", 1)
if self.getvalue(x-1, y-1) == "3":
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
self.set(x-1, y-1, "top", 1)
self.set(x-1, y-1, "left", 1)

# 2's
if self.getvalue(x, y) == "2":
# two x'd -> mark the other two
if self.get(x, y, "top") == -1 and self.get(x, y, "bottom") == -1:
self.set(x, y, "right", 1)
self.set(x, y, "left", 1)
if self.get(x, y, "left") == -1 and self.get(x, y, "right") == -1:
self.set(x, y, "top", 1)
self.set(x, y, "bottom", 1)

# two corner lines
if self.get(x, y, "top") == 1 and self.get(x, y, "right") == 1:
self.set(x, y, "bottom", -1)
self.set(x, y, "left", -1)
if self.get(x, y, "right") == 1 and self.get(x, y, "bottom") == 1:
self.set(x, y, "left", -1)
self.set(x, y, "top", -1)
if self.get(x, y, "bottom") == 1 and self.get(x, y, "left") == 1:
self.set(x, y, "top", -1)
self.set(x, y, "right", -1)
if self.get(x, y, "left") == 1 and self.get(x, y, "top") == 1:
self.set(x, y, "right", -1)
self.set(x, y, "bottom", -1)

# two x'd corner lines
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
self.set(x, y, "left", 1)
self.set(x, y, "top", 1)
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)
if self.get(x, y, "left") == -1 and self.get(x, y, "top") == -1:
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)

# a line running into a 2 when one is x'd
if self.get(x, y, "top") == -1:
if self.get(x-1, y+1, "top") == 1:
self.set(x, y, "right", 1)
self.set(x-1, y+1, "right", -1)
if self.get(x-1, y+1, "right") == 1:
self.set(x, y, "right", 1)
self.set(x-1, y+1, "top", -1)
if self.get(x, y, "right") == -1:
if self.get(x-1, y-1, "right") == 1:
self.set(x, y, "bottom", 1)
self.set(x-1, y-1, "bottom", -1)
if self.get(x-1, y-1, "bottom") == 1:
self.set(x, y, "bottom", 1)
self.set(x-1, y-1, "right", -1)
if self.get(x, y, "bottom") == -1:
if self.get(x+1, y-1, "left") == 1:
self.set(x, y, "left", 1)
self.set(x+1, y-1, "bottom", -1)
if self.get(x+1, y-1, "bottom") == 1:
self.set(x, y, "left", 1)
self.set(x+1, y-1, "left", -1)
if self.get(x, y, "left") == -1:
if self.get(x+1, y+1, "left") == 1:
self.set(x, y, "top", 1)
self.set(x+1, y+1, "top", -1)
if self.get(x+1, y+1, "top") == 1:
self.set(x, y, "top", 1)
self.set(x+1, y+1, "left", -1)

# 3's
if self.getvalue(x, y) == "3":
# a 3 with one x'd line
if self.get(x, y, "top") == -1:
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
if self.get(x, y, "right") == -1:
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
self.set(x, y, "top", 1)
if self.get(x, y, "bottom") == -1:
self.set(x, y, "left", 1)
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)
if self.get(x, y, "left") == -1:
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)

# two x'd adjacent to a 3 -> two lines building a cross with the x'd ones
if self.get(x-1, y, "top") == -1 and self.get(x, y-1, "left") == -1:
self.set(x, y, "top", 1)
self.set(x, y, "left", 1)
if self.get(x+1, y, "top") == -1 and self.get(x, y-1, "right") == -1:
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)
if self.get(x+1, y, "bottom") == -1 and self.get(x, y+1, "right") == -1:
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)
if self.get(x-1, y, "bottom") == -1 and self.get(x, y+1, "left") == -1:
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)

# one line running into a 3 -> set opposite lines
if self.get(x-1, y-1, "right") == 1:
self.set(x-1, y-1, "bottom", -1)
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)
if self.get(x-1, y-1, "bottom") == 1:
self.set(x-1, y-1, "right", -1)
self.set(x, y, "right", 1)
self.set(x, y, "bottom", 1)
if self.get(x+1, y-1, "bottom") == 1:
self.set(x+1, y-1, "left", -1)
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
if self.get(x+1, y-1, "left") == 1:
self.set(x+1, y-1, "bottom", -1)
self.set(x, y, "bottom", 1)
self.set(x, y, "left", 1)
if self.get(x+1, y+1, "left") == 1:
self.set(x+1, y+1, "top", -1)
self.set(x, y, "left", 1)
self.set(x, y, "top", 1)
if self.get(x+1, y+1, "top") == 1:
self.set(x+1, y+1, "left", -1)
self.set(x, y, "left", 1)
self.set(x, y, "top", 1)
if self.get(x-1, y+1, "top") == 1:
self.set(x-1, y+1, "right", -1)
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)
if self.get(x-1, y+1, "right") == 1:
self.set(x-1, y+1, "top", -1)
self.set(x, y, "top", 1)
self.set(x, y, "right", 1)

# a 3 with two lines diagonally to a 1 -> x the corner at the 1
if self.getvalue(x-1, y+1) == "1":
if self.get(x, y, "top") == 1 and self.get(x, y, "right") == 1:
self.set(x-1, y+1, "bottom", -1)
self.set(x-1, y+1, "left", -1)
if self.getvalue(x-1, y-1) == "1":
if self.get(x, y, "right") == 1 and self.get(x, y, "bottom") == 1:
self.set(x-1, y-1, "left", -1)
self.set(x-1, y-1, "top", -1)
if self.getvalue(x+1, y-1) == "1":
if self.get(x, y, "bottom") == 1 and self.get(x, y, "left") == 1:
self.set(x+1, y-1, "top", -1)
self.set(x+1, y-1, "right", -1)
if self.getvalue(x+1, y+1) == "1":
if self.get(x, y, "left") == 1 and self.get(x, y, "top") == 1:
self.set(x+1, y+1, "right", -1)
self.set(x+1, y+1, "bottom", -1)

# set a line that only has one way to go
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
if self.get(x, y-1, "right") == 1:
self.set(x+1, y, "top", 1)
if self.get(x+1, y, "top") == 1:
self.set(x, y-1, "right", 1)
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
if self.get(x+1, y, "bottom") == 1:
self.set(x, y+1, "right", 1)
if self.get(x, y+1, "right") == 1:
self.set(x+1, y, "bottom", 1)
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
if self.get(x-1, y, "bottom") == 1:
self.set(x, y+1, "left", 1)
if self.get(x, y+1, "left") == 1:
self.set(x-1, y, "bottom", 1)
if self.get(x, y, "left") == -1 and self.get(x, y, "top") == -1:
if self.get(x-1, y, "top") == 1:
self.set(x, y-1, "left", 1)
if self.get(x, y-1, "left") == 1:
self.set(x-1, y, "top", 1)

# vertically or horizontically x'd
if self.get(x, y, "bottom") == -1 and self.get(x+1, y, "bottom") == -1:
if self.get(x, y, "right") == 1:
self.set(x, y+1, "right", 1)
if self.get(x, y+1, "right") == 1:
self.set(x, y, "right", 1)
if self.get(x, y, "right") == -1 and self.get(x, y+1, "right") == -1:
if self.get(x, y, "bottom") == 1:
self.set(x+1, y, "bottom", 1)
if self.get(x+1, y, "bottom") == 1:
self.set(x, y, "bottom", 1)

# x any lines that are near a junction
if self.get(x, y, "top") == 1 and self.get(x, y, "right") == 1:
self.set(x+1, y-1, "bottom", -1)
self.set(x+1, y-1, "left", -1)
if self.get(x, y, "right") == 1 and self.get(x, y, "bottom") == 1:
self.set(x+1, y+1, "left", -1)
self.set(x+1, y+1, "top", -1)
if self.get(x, y, "bottom") == 1 and self.get(x, y, "left") == 1:
self.set(x-1, y+1, "top", -1)
self.set(x-1, y+1, "right", -1)
if self.get(x, y, "left") == 1 and self.get(x, y, "top") == 1:
self.set(x-1, y-1, "right", -1)
self.set(x-1, y-1, "bottom", -1)

# two x'd, one known -> set other one
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1:
if self.get(x+1, y-1, "bottom") == 1:
self.set(x+1, y-1, "left", 1)
if self.get(x+1, y-1, "left") == 1:
self.set(x+1, y-1, "bottom", 1)
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1:
if self.get(x+1, y+1, "top") == 1:
self.set(x+1, y+1, "left", 1)
if self.get(x+1, y+1, "left") == 1:
self.set(x+1, y+1, "top", 1)
if self.get(x, y, "bottom") == -1 and self.get(x, y, "left") == -1:
if self.get(x-1, y+1, "right") == 1:
self.set(x-1, y+1, "top", 1)
if self.get(x-1, y+1, "top") == 1:
self.set(x-1, y+1, "right", 1)
if self.get(x, y, "left") == -1 and self.get(x, y, "top") == -1:
if self.get(x-1, y-1, "bottom") == 1:
self.set(x-1, y-1, "right", 1)
if self.get(x-1, y-1, "right") == 1:
self.set(x-1, y-1, "bottom", 1)

# similiar to above
if self.get(x, y, "left") == 1:
if self.get(x-1, y, "top") == -1 and self.get(x, y, "top") == -1:
self.set(x, y-1, "left", 1)
if self.get(x, y, "top") == 1:
if self.get(x, y-1, "right") == -1 and self.get(x, y, "right") == -1:
self.set(x+1, y, "top", 1)

# two lines -> x the other ones
if self.get(x, y, "top") == 1 and self.get(x+1, y, "top") == 1:
self.set(x, y, "right", -1)
self.set(x, y-1, "right", -1)
if self.get(x, y, "right") == 1 and self.get(x, y-1, "right") == 1:
self.set(x, y, "top", -1)
self.set(x+1, y, "top", -1)

# three x'd ones -> four x'd ones
if self.get(x, y, "top") == -1 and self.get(x, y, "right") == -1 and self.get(x+1, y, "top") == -1:
self.set(x, y-1, "right", -1)
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1 and self.get(x, y+1, "right") == -1:
self.set(x+1, y, "bottom", -1)
if self.get(x, y, "right") == -1 and self.get(x, y, "bottom") == -1 and self.get(x+1, y, "bottom") == -1:
self.set(x, y+1, "right", -1)
if self.get(x, y, "right") == -1 and self.get(x+1, y, "bottom") == -1 and self.get(x, y+1, "right") == -1:
self.set(x, y, "bottom", -1)

# calculates the number of joined and partial (not joined) loops and sets the error flag to true if it finds an error
def getloops(self):
# copy the slither
slither = copy.deepcopy(self)

# set x's to nothing
for x in range(w):
for y in range(h):
for _ in ("top", "right", "bottom", "left"):
if slither.get(x, y, _) == -1:
slither.set(x, y, _, 0)

# partial loops and joined loops
partialloops = 0
loops = 0

# find a line to go along and check the loop
for X in range(w):
for Y in range(h):
for DIR in ("top", "right", "bottom", "left"):
if slither.get(X, Y, DIR) == 1:
# start a new loop
partialloops += 1

# assume it is a loop, may later turn out as a false assumption
isloop = True

# go through adjacent lines, check them
P = [(X, Y, DIR)]
while len(P) > 0:
for p in P:
x, y, dir = p
P.remove(p)
n = 0
if dir == "top":
for _ in ((x-1, y, "top"), (x+1, y, "top"), (x, y, "left"), (x, y, "right"), (x, y-1, "left"), (x, y-1, "right")):
if slither.get(_, _, _) == 1:
P.append(_)
n += 1
elif slither.exists(_, _, _) and slither.get(_, _, _) == -1:
n += 1
slither.set(x, y, "top", -1)
elif dir == "right":
for _ in ((x, y, "top"), (x, y, "bottom"), (x+1, y, "top"), (x+1, y, "bottom"), (x, y-1, "right"), (x, y+1, "right")):
if slither.get(_, _, _) == 1:
P.append(_)
n += 1
elif slither.exists(_, _, _) and slither.get(_, _, _) == -1:
n += 1
slither.set(x, y, "right", -1)
elif dir == "bottom":
for _ in ((x, y, "left"), (x, y, "right"), (x, y+1, "left"), (x, y+1, "right"), (x-1, y, "bottom"), (x+1, y, "bottom")):
if slither.get(_, _, _) == 1:
P.append(_)
n += 1
elif slither.exists(_, _, _) and slither.get(_, _, _) == -1:
n += 1
slither.set(x, y, "bottom", -1)
elif dir == "left":
for _ in ((x, y, "top"), (x, y, "bottom"), (x-1, y, "top"), (x-1, y, "bottom"), (x, y+1, "left"), (x, y-1, "left")):
if slither.get(_, _, _) == 1:
P.append(_)
n += 1
elif slither.exists(_, _, _) and slither.get(_, _, _) == -1:
n += 1
slither.set(x, y, "left", -1)

# a joined loop has only 2 lines at one junction
if n != 2:
isloop = False

# this loop is a joined loop
if isloop:
partialloops -= 1
loops += 1

# one loop, must not have any other loops
if loops == 1:
if partialloops > 0:
self.error = True

# more than one loop cannot be correct
elif loops > 1:
self.error = True

# return partial and full loops
return partialloops, loops

# to check if something happened, identify the data and compare with other identified data
def getidentifier(self):
trits = ""
for y in self.data:
for x in y:
for dir in ("top", "right", "bottom", "left"):
trits += ("0", "1", "2")[x.get(dir)]
trits += str(int(self.error))
return int(trits, 3)

# test if given tile (or tile's side) exists
def exists(self, x, y, direction = None):
if direction is None:
return (x >= 0 and y >= 0 and x < w and y < h)
else:
if (x == w and y == h) or (x == -1 and y == -1) or (x == w and y == -1) or (x == -1 and y == h):
return False
if x == w:
return direction == "left"
if y == h:
return direction == "top"
if x == -1:
return direction == "right"
if y == -1:
return direction == "bottom"

return (x >= 0 and y >= 0 and x < w and y < h)

# get a tile's value
def getvalue(self, x, y):
if self.exists(x, y):
return self.data[y][x].getvalue()
return "/"

# get a tile's side
def get(self, x, y, direction):
# every tile not in the slither has automatically all sides x'd, except those touching the slither
if (x == w and y == h) or (x == -1 and y == -1) or (x == w and y == -1) or (x == -1 and y == h):
return -1
if x == w:
if direction == "left":
return self.get(x-1, y, "right")
return -1
if y == h:
if direction == "top":
return self.get(x, y-1, "bottom")
return -1
if x == -1:
if direction == "right":
return self.get(x+1, y, "left")
return -1
if y == -1:
if direction == "bottom":
return self.get(x, y+1, "top")
return -1

# tile has to exist
if self.exists(x, y):
return self.data[y][x].get(direction)

# tile does not exist
return -1

# set a tile's side (and the neighbouring tile's)
def set(self, x, y, direction, value):
# every tile not in the slither has automatically all sides x'd, except those touching the slither
if (x >= w and y >= h) or (x <= -1 and y <= -1) or (x >= w and y <= -1) or (x <= -1 and y >= h):
return
if x == w:
if direction == "left":
self.set(x-1, y, "right", value)
return
if y == h:
if direction == "top":
self.set(x, y-1, "bottom", value)
return
if x == -1:
if direction == "right":
self.set(x+1, y, "left", value)
return
if y == -1:
if direction == "bottom":
self.set(x, y+1, "top", value)
return

# cannot set something if it is already set
if self.get(x, y, direction) != 0 and self.get(x, y, direction) != value:
self.error = True
# must not return due to current loop checking algorithm!

# set
if self.exists(x, y):
self.data[y][x].set(direction, value)
else:
return

if direction == "left":
if x > 0:
self.data[y][x-1].set("right", value)
elif direction == "right":
if x < w-1:
self.data[y][x+1].set("left", value)
elif direction == "top":
if y > 0:
self.data[y-1][x].set("bottom", value)
elif direction == "bottom":
if y < h-1:
self.data[y+1][x].set("top", value)

# get a string representing the slither
def __str__(self):
# show x'd lines with an x
showX = False

# symbols
hig = "\033[1;34;40m" #"\033[36m"
hig += "\033[1m" # bold
low = "\033[90m"
end = "\033[0m"
if showX:
symx = ["  ", hig + "--" + end, low + "xx" + end]
symy = [" ", hig + "|" + end, low + "x" + end]
else:
symx = ["  ", hig + "--" + end, "  "]
symy = [" ", hig + "|" + end, " "]
nil = ""

# stars mean the junction points
higstar = hig + "*" + end
lowstar = low + "*" + end

# message m
m = ""

# go through data
for y in range(h):
s1 = ""
s2 = ""
for x in range(w):
if self.get(x, y, "top") == 1 or self.get(x, y, "left") == 1 or self.get(x-1, y-1, "bottom") == 1 or self.get(x-1, y-1, "right") == 1:
s1 += higstar
else:
s1 += lowstar
s1 += symx[self.get(x, y, "top")]
s2 += symy[self.get(x, y, "left")] + " " + self.getvalue(x, y)
if self.get(w-1, y, "top") == 1 or self.get(w-1, y, "right") == 1 or self.get(w-1, y-1, "right") == 1:
s1 += higstar
else:
s1 += lowstar
s2 += symy[self.get(w-1, y, "right")]
m += s1 + "\n" + s2 + "\n"

for x in range(w):
if self.get(x, h-1, "left") == 1 or self.get(x, h-1, "bottom") == 1 or self.get(x-1, h-1, "bottom") == 1:
m += higstar
else:
m += lowstar
m += symx[self.get(x, h-1, "bottom")]
if self.get(w-1, h-1, "right") == 1 or self.get(w-1, h-1, "bottom") == 1:
m += [higstar, hig + "+" + end][self.error]
else:
m += [lowstar, low + "+" + end][self.error]

# return
return m

# solve the slither
def solve():
global SOLUTIONS

# remember when solver started solving
t0 = time.time()

# check the data
if checkdata():
# initialize a slither
slither = Slither()
S = [slither]

SOLUTIONS = []

# loop until a solution is found
while True:
# get guesses
new = []
for s in S:
for _ in s.guess():
new.append(_)

# status message
_.statusmessage(len(S))
S = new[:]

# nothing guessed, hopefully a solution was found!
if len(S) <= 0:
break

# clear status message
sys.stdout.write("\r\033[K")
sys.stdout.flush()

# one solution, yay
if len(SOLUTIONS) == 1:
print SOLUTIONS

# no solution
elif len(SOLUTIONS) < 1:
print "Found no solution."
print Slither()

# multiple solutions
else:
print "Found %d solutions." % len(SOLUTIONS)
for _ in range(len(SOLUTIONS)):
if _ != 0:
raw_input()
print SOLUTIONS[_]

# calculate elapsed time
t1 = time.time()
dt = t1-t0

# print elapsed time
print "Took %f seconds." % dt

# handle the possible user interaction (this solver occasionally may be too slow)
try:
# solve the slither
solve()

# CTRL-C
except KeyboardInterrupt:
print ", Calculation canceled."

This site uses Akismet to reduce spam. Learn how your comment data is processed.