Quilt of squares

A quilting studio charges by the seam, so the fewest patches wins. The patches are all squares, and the greedy cut is not the cheap one.

The problem

A commission comes in for a plain quilt, width inches across and height inches tall. The studio cuts patches only as squares with whole-inch sides, any side from 1 inch up, and the top must be covered exactly: no overlaps, no gaps, nothing hanging over an edge. Sizes may repeat, and a patch may sit anywhere as long as its edges line up with the inch grid.

Every patch is another seam to sew, so the studio wants the fewest squares that cover the quilt.

Input. width and height — integers, the quilt's size in inches.

Output. The fewest square patches that cover it exactly.

Example.

width = 4, height = 6   ->  3

One 4x4 patch across the bottom, then two 2x2 patches side by side above it: 16 + 4 + 4 = 24 square inches, which is the whole quilt.

A second example, where cutting the largest square first is wrong:

width = 11, height = 13  ->  6

Cutting an 11x11 patch leaves an 11x2 strip, which needs five 2x2 patches and two 1x1 patches — eight in all. Six is possible, and no arrangement that starts with the biggest square finds it.

Constraints.

• 1 <= width <= 13
• 1 <= height <= 13

Hints

Approach

Brute force

Try every patch in every position in every order. A 13x13 quilt has 169 cells and up to 13 sizes at each, and the orderings multiply out past anything countable.

The insight

Always cover the lowest, leftmost exposed inch next, and the only thing left to choose is the size of the patch that starts there.

The cell below it is covered, since it is the lowest exposed inch in its column, and the cell to its left is covered, since it is the leftmost column at that height. So whichever patch covers it has its bottom-left corner exactly there. Ordering drops out of the search, and the branching factor falls to the patch sizes that fit inside the flat run and under the top edge — at most 13.

Algorithm

1. Keep a skyline array: covered inches per column, all zero at the start.
2. Hold the best count so far, starting at width * height.
3. Abandon the branch once the count so far matches the best.
4. If every column reaches height, record the count.
5. Otherwise take the leftmost lowest column and the flat run to its right.
6. For each side from the widest that fits down to 1: raise those columns, recurse, lower them again.

Complexity

Time is exponential in principle. The pruning does the work: with sides capped at 13, the search settles in a few thousand placements. Space O(width) for the skyline, plus recursion at most width * height deep.

Solution

"""Quilt of squares — exhaustive search over the sewn edge, pruned by the best count so far."""


def solve(width, height):
    """Fewest square patches, all with whole-inch sides, that fill a width x height quilt."""
    if width == height:
        return 1

    # skyline[c] = how many inches of column c are already covered, measured
    # from the bottom edge. A partial quilt is fully described by this profile.
    skyline = [0] * width
    best = [width * height]          # all one-inch patches: always legal, never good

    def place(used):
        if used >= best[0]:          # this branch cannot beat what we already hold
            return
        low = min(skyline)
        if low == height:
            best[0] = used
            return
        # Invariant: the leftmost lowest column must be covered by some patch,
        # and that patch's bottom-left corner sits exactly there. Nothing is lost
        # by committing to it now, so the only choice left is the patch's size.
        left = skyline.index(low)
        right = left
        while right < width and skyline[right] == low:
            right += 1
        widest = min(right - left, height - low)
        for side in range(widest, 0, -1):
            for column in range(left, left + side):
                skyline[column] += side
            place(used + 1)
            for column in range(left, left + side):
                skyline[column] -= side

    place(0)
    return best[0]

TESTS = [
    ((11, 13), 6),
    ((5, 8), 5),
    ((4, 6), 3),
    ((2, 3), 3),
    ((6, 9), 3),
    ((1, 7), 7),
    ((13, 13), 1),
    ((1, 1), 1),
]

Pitfalls

• Cutting the largest square that fits, then repeating. On 11x13 that gives eight patches; the answer is six. Greedy is a good first bound, not a solution.
• Capping the patch side by the flat run only. The run may be 5 columns wide with 2 inches left below the top edge; a 5x5 patch then hangs off the quilt. Cap by both, and 2x3 stops reporting 2 instead of 3.
• Forgetting to lower the skyline after the recursive call. Later branches inherit phantom coverage and the count comes back too small.

Variants

• Splitting the ripening shelf — also a search over choices, but there the states repeat and a table replaces the pruning.
• Starting the ridge relay — the moves are forced, not chosen, which turns the search into a two-row scan.