Can You Solve a High Schooler’s Favorite Puzzle?

You have an unlimited supply of $3\times3$ tiles and $5\times5$ tiles. You want to tile a square of integer side length exactly, with no overlaps and no overhang, using at least one tile of each kind. What is the smallest square you can tile this way?

The Fiddler, Zach Wissner-Gross, May 10, 2024(original post)

Solution

Matching areas is necessary but nowhere near sufficient. A side $n$ needs $n^2=9a+25b$ with $a,b\ge1$, and the smallest sides clearing that hurdle are $13,14,16,17$, and $18$. Yet the area can balance while the tiles refuse to fit: a complete search (cover the first empty cell with a $5$ or a $3$, recurse, backtrack) shows that $13,14,16$, and $17$ admit no tiling at all, the $3$s and $5$s never reconciling along the edges. The first side that genuinely tiles with both sizes present is $$\boxed{18},$$ which packs as a border of $3$s around a central block of $5$s.

The computation

The search is exact, not heuristic: because the first empty cell (scanning top to bottom, left to right) must be the top-left corner of whatever tile covers it, trying both tiles there and backtracking enumerates every tiling. Returning to the smallest side that admits one with both kinds present gives $18$.

def tileable_mixed(n):
    grid = [[0] * n for _ in range(n)]
    def first_empty():
        for r in range(n):
            for c in range(n):
                if not grid[r][c]: return r, c
        return None
    def fits(r, c, s):
        return r + s <= n and c + s <= n and all(
            not grid[i][j] for i in range(r, r+s) for j in range(c, c+s))
    def fill(r, c, s, v):
        for i in range(r, r+s):
            for j in range(c, c+s): grid[i][j] = v
    def solve(n3, n5):
        p = first_empty()
        if p is None: return n3 >= 1 and n5 >= 1
        r, c = p
        for s, nxt in [(5, (n3, n5+1)), (3, (n3+1, n5))]:
            if fits(r, c, s):
                fill(r, c, s, s)
                if solve(*nxt): return True
                fill(r, c, s, 0)
        return False
    return solve(0, 0)
print(next(n for n in range(3, 30) if tileable_mixed(n)))    # 18

Extra Credit

Now you have tiles of every odd side length greater than $1$ ($3,5,7,9,\dots$). What is the largest $N$ for which an $N\times N$ square cannot be tiled?

Solution

Any odd $N\ge3$ is a single tile, so only even sides are ever in doubt. Searching each even side in turn, the ones that cannot be broken into odd squares at all are exactly $1,2,4,8$, and $16$, while $6,10,12,14$ and every side from $18$ upward can. The largest impossible square therefore has side $$\boxed{16}.$$ It is the last even side too cramped to split into odd squares; $18$ and every larger even side go through.

The computation

The same exact backtracking search, now with every odd tile up to side $n$, lists the sides that admit no tiling.

def tileable(n):
    grid = [[0] * n for _ in range(n)]
    odds = [s for s in range(n, 2, -1) if s % 2]      # odd sizes, largest first
    def solve():
        p = next(((r, c) for r in range(n) for c in range(n) if not grid[r][c]), None)
        if p is None: return True
        r, c = p
        for s in odds:
            if r+s <= n and c+s <= n and all(not grid[i][j]
                    for i in range(r, r+s) for j in range(c, c+s)):
                for i in range(r, r+s):
                    for j in range(c, c+s): grid[i][j] = s
                if solve(): return True
                for i in range(r, r+s):
                    for j in range(c, c+s): grid[i][j] = 0
        return False
    return solve()
print([n for n in range(1, 33) if not tileable(n)])          # [1, 2, 4, 8, 16]