Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import copy
f = open("ltri8x8-34.psv")
a = f.read().split("\n")
orient_list = (((0,0),(0,1),(1,1)),((1,0),(0,1),(1,1)),((0,0),(1,0),(1,1)),((0,0),(0,1),(1,0)))
def boardgen(s):
board = [[0 for i in range(8)] for j in range(8)]
piece = 1
for e in s.split("(")[2:]:
orientation = int(e[4])
x_coord = int(e[0])
y_coord = int(e[2])
for i in orient_list[orientation]:
board[x_coord+i[0]][y_coord+i[1]] = piece
piece += 1
return board
def verify(b):
#easiest check - at most 1 junction point - each junction point requires at least one "bridge", so you can have at most 1 junction
#performing this check before actually doing the coloring saves us quite a bit of work, I think
jct = 0
for i in range(7):
for j in range(7):
junction = set([b[i][j],b[i+1][j],b[i][j+1],b[i+1][j+1]])
if len(junction) == 4 and min(junction) != 0:
jct += 1
if jct > 1:
return False
#check 2 - 3 colorability
edgelist = [set() for i in range(21)]
for i in range(7):
for j in range(8):
if b[i][j] != b[i+1][j] and b[i][j] != 0 and b[i+1][j] != 0:
edgelist[b[i][j]-1].add(b[i+1][j])
edgelist[b[i+1][j]-1].add(b[i][j])
for i in range(8):
for j in range(7):
if b[i][j] != b[i][j+1] and b[i][j] != 0 and b[i][j+1] != 0:
edgelist[b[i][j]-1].add(b[i][j+1])
edgelist[b[i][j+1]-1].add(b[i][j])
vertexset = {i for i in range(1,22)}
colors = [0 for i in range(21)]
colorset = [{1,2,3} for i in range(21)]
res = backtracker(edgelist, vertexset, colors, colorset, 1)
if res == []:
return False
#check 3 - 7 of each color
newres = []
for coloring in res:
counts = [0,0,0]
for i in coloring:
counts[i-1] += 1
if counts == [7,7,7]:
newres.append(coloring)
if newres == []:
return False
#check 4 - 21 or 22 "diagonal branches" (each L tetromino naturally has 1. We are allowed 1 more)
newnewres = []
for coloring in newres:
count = 0
for i in range(7):
for j in range(7):
if b[i][j+1] != 0 and b[i+1][j] != 0 and coloring[b[i][j+1]-1] == coloring[b[i+1][j]-1]:
count += 1
if b[i+1][j+1] != 0 and b[i][j] != 0 and coloring[b[i+1][j+1]-1] == coloring[b[i][j]-1]:
count += 1
if count <= 22:
newnewres.append(coloring)
if newnewres == []:
return False
return newnewres
def backtracker(edgelist, vertexset, colors, colorset, depth):
if len(vertexset) == 0:
return [copy.copy(colors)]
ret = []
easiestvertex = 1
mincolors = 3
for i in vertexset:
if len(colorset[i-1]) < mincolors:
easiestvertex = i
mincolors = len(colorset[i-1])
colorsetcopy = copy.deepcopy(colorset)
for c in colorsetcopy[easiestvertex-1]:
if (depth == 1 and c == 1) or (depth == 2 and c == 2) or depth > 2: # cuts some possibilities away, should be 6x speedup
for v in edgelist[easiestvertex-1]:
colorset[v-1].discard(c)
vertexset.remove(easiestvertex)
colors[easiestvertex-1] = c
ret.extend(backtracker(edgelist, vertexset, colors, colorset, depth+1))
#reset state
vertexset.add(easiestvertex)
colors[easiestvertex-1] = 0
colorset = copy.deepcopy(colorsetcopy)
return ret
def printboard(b):
for i in range(8):
for j in range(8):
print(b[i][j],end='\t')
print()
print()
s = a[6:-1]
count = 0
for e in s:
b = boardgen(e)
v = verify(b)
if v:
print(v)
count += 1
printboard(b)
print(count)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.