Packing tetraminos

tetraminos.py

import collections
from ortools.linear_solver import pywraplp

# xy format
tetras = [
        # Up downs
        ((0,0),(0,1),(1,1),(1,2)),
        ((0,0),(0,1),(-1,1),(-1,2)),
        # left rights
        ((0,0),(1,0),(1,-1),(2,-1)),
        ((0,0),(1,0),(1,1),(2,1))
        ]

def solve(n, low):
    solver = pywraplp.Solver.CreateSolver('GLOP')
    vs = [[solver.NumVar(0, solver.infinity(), f'{i} {j}')
        for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            for t in tetras:
                if all(0 <= i+di < n and 0 <= j+dj < n for di,dj in t):
                    c = solver.Constraint(low, solver.infinity())
                    for di, dj in t:
                        c.SetCoefficient(vs[i+di][j+dj], 1)

    objective = solver.Objective()
    for i in range(n):
        for j in range(n):
            objective.SetCoefficient(vs[i][j], 1)
    objective.SetMinimization()

    solver.Solve()
    s = sum(vs[i][j].solution_value() for i in range(n) for j in range(n))
    return s, vs

for n in range(20):
    if n**2 % 4 != 0: continue
    print(n)
    for low in range(1,10):
        s, vs = solve(n, low)
        blanks = n**2 - 4*int(s / low)
        print(f'low: {low}, sum: {s}, blanks: {blanks}')