# 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", "     ", "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."