Solving https://puzzling.stackexchange.com/questions/63731/covering-an-8%C3%978-grid-with-trominoes

triverifier.py

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)