Advent Of Code 2025 Day 12

Intro

I am writing this while still solving the puzzle, so I do not yet know where it will lead me.

Part 1

In part 1, the problem is to check whether it is possible to pack a set of polyomino shapes into rectangles of a fixed size.

For example, we can have 2 C shapes, 1 T shape, and 3 H shapes:

...............
.###..###..#.#.
.#.....#...###.
.###...#...#.#.
...............

Our goal is to check if we can fit them into a 10×8 rectangle.
It is allowed to rotate and flip the shapes.

I also noticed that all shapes are 3×3: the bounding box of each shape is 3×3, and the shapes are connected. This means that some shapes are impossible, such as:

...................
.###.. # ..#.#.....
.......#...#.#..###
.###...#...#.#.....
...............

Maybe this can be used for some optimizations.

General Approach

I believe this is an NP-hard problem, so there is no algorithm that avoids exploring all possible variants. Our main goal is to avoid exploring duplicate configurations and to implement the search efficiently.

A naive implementation could look like this:

search {
    if all shapes placed -> return success
    take one shape from unplaced shapes
    for every position/rotation/flip {
        if can place shape at this position {
            place the shape
            recursively call search
            if success -> return success
            remove shape so it can be placed elsewhere
        }
    }
    return shape to unplaced
    return failure
}

In my implementation, I generated the list of unplaced shapes like this:

For every shape type {
    for count of shapes of this type {
        add shape to list
    }
}

Even for small test examples, exploring all variants can take time with this approach. What can we do to improve it?

Ideas for Optimization

Only Explore Adjacent Positions

Right now, we try placing shapes anywhere they can fit. Instead, we can restrict placements to positions adjacent to already-placed shapes. This reduces the number of variants from approximately N² to about N, where N is the grid dimension.

This optimization reduced the runtime on test data from ~30 seconds to ~5 seconds on my machine. Not bad, but still not enough.

Memoization

We might attempt to place different instances of the same shape into the same position. For example, if we have several identical shapes unplaced, and we reach a state from which it is impossible to place all remaining shapes, we would still try each identical shape in each possible placement, exploring the same subtrees repeatedly.

To avoid this, we can remember visited grid states and exit early if we encounter one again. This brings the runtime down to about ~2 seconds for the test data.

Count the Number of Needed Cells

There is one very simple idea: count the number of filled cells required by all shapes. If the rectangle does not have enough empty cells, there is no point in attempting the search at all.

Even though this optimization is trivial, it alone would have allowed me to get the answer for Part 1.

That is a bit unfortunate, because I had already started thinking about Donald Knuth’s Dancing Links. I’ve never implemented it myself before, so I was looking forward to doing it. Who knows — maybe I would have needed it in Part 2?

Part 2

Oh no! I totally forgot! It is the last day of Advent of Code this year. There are no second parts on the last day of Advent of Code.

So this ended much faster than I expected — both the event and this blog post.

Hope you enjoyed reading it.

Source Code

The source code can be found on my GitHub.