Dissection of a square into n similar rectangles via guillotine cuts

sim-rect-diss.sage

from dataclasses import dataclass
from typing import Any
from sage.all import *

n = 4

# A guillotine partition is a binary tree of horizontal and vertical cuts.
# In our problem each leaf node is a horizontal or vertical rectangle.
# For example, 3 vertical cuts and 4 vertical rectangles produce [ | | | ]

@dataclass
class CH:
    c0: Any
    c1: Any

@dataclass
class CV:
    c0: Any
    c1: Any

@dataclass
class RH:
    pass

@dataclass
class RV:
    pass

# First we generate the partitions.
# At the root, due to symmetry we only need one of CH or CV.

def guillotine(n, root=False):
    if n <= 1:
        yield RH()
        yield RV()
    else:
        for i in range(1, n//2 + 1):
            for c0 in guillotine(i):
                for c1 in guillotine(n-i):
                    yield CH(c0, c1)
                    if not root:
                        yield CV(c0, c1)

# Then, we find the aspect ratios of the partitions,
# assuming the aspect ratios of the leaves are 1:u,
# and solve for the values of u that yield squares.

u = QQ['u'].0

def simplify(p0, p1):
    q = p0.gcd(p1)
    return (p0//q, p1//q)

def aspect(t):
    if isinstance(t, RH):
        return (u,1)
    elif isinstance(t, RV):
        return (1,u)
    elif isinstance(t, CH):
        (w0,h0) = aspect(t.c0)
        (w1,h1) = aspect(t.c1)
        return simplify(w0*w1, w0*h1 + w1*h0)
    elif isinstance(t, CV):
        (w0,h0) = aspect(t.c0)
        (w1,h1) = aspect(t.c1)
        return simplify(w0*h1 + w1*h0, h0*h1)

d = {aspect(t):t for t in guillotine(n, True)}

def genroots(d):
    for a, t in d.items():
        rs = (a[0]-a[1]).roots(ring=RR)
        for r in rs:
            if r[0] >= 1:
                yield(1/r[0], r[0], a, t)

l = sorted(list(genroots(d)), key=lambda i: i[0])
for i in l:
    print(i)

-u^2 + 4u - 4 = -(u - 2)^2
u^3 - 3u^2 + 4u - 4 = (u - 2)(u^2 - u + 2)
2u^3 - 6u^2 + 2u - 2 = 2(u^3 - 3*u^2 + u - 1)