Slitherlink Solver

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 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]) <= 0:
		print "Please enter data."
		return False
	
	# determine width and height
	w, h = len(data[0]), 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
	
	# link the slither!	
	def link(self):
		# find links until there is nothing more to find
		id = -1
		while id != self.getidentifier() and not self.error:
			id = self.getidentifier()
			self.repeatedlinks()
		
		# 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, _)
							c.link()
							if not c.error:
								C.append(c)
						return C
		
		# a solution was found
		SOLUTIONS.append(self)
		
		# nothing to guess, it's a solution!
		return []
	
	# initial links
	def initiallink(self):
		# 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)
				
				# two adjacent 3's
				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)
		
	# repeated links
	def repeatedlinks(self):
		# no point in linking if there already is an error
		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)
					
					# diagonally adjacent 1's
					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(_[0], _[1], _[2]) == 1:
											P.append(_)
											n += 1
										elif slither.exists(_[0], _[1], _[2]) and slither.get(_[0], _[1], _[2]) == -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(_[0], _[1], _[2]) == 1:
											P.append(_)
											n += 1
										elif slither.exists(_[0], _[1], _[2]) and slither.get(_[0], _[1], _[2]) == -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(_[0], _[1], _[2]) == 1:
											P.append(_)
											n += 1
										elif slither.exists(_[0], _[1], _[2]) and slither.get(_[0], _[1], _[2]) == -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(_[0], _[1], _[2]) == 1:
											P.append(_)
											n += 1
										elif slither.exists(_[0], _[1], _[2]) and slither.get(_[0], _[1], _[2]) == -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
		
		# set adjacent
		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"
		
		# add finishing line
		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()
		slither.initiallink()
		slither.link()
		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[0]
		
		# 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."
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s