Skip to content

Instantly share code, notes, and snippets.

# phenomist/triverifier.py Created May 22, 2018

 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)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.