Covering the Holes in a Wall with Bricks — a Single Beam Search Flowing from Top to Bottom

Every arrangement we build satisfies the conditions by construction, and the search reduces to a single straight sequence of decisions: which width to place where.

1. The support condition fixes the direction

A brick cannot be placed unless the cell directly below its center is filled. Turned around, this means that every time we place a brick, a new obligation is created — “cover the cell directly below its center” — and it keeps propagating down to the floor. A hole that has to be covered is an obligation of exactly the same shape, so processing the wall row by row from the top down is the natural direction.

With this direction, once a row has been processed, the only information that must be carried over is the set of columns under an obligation to be covered, namely the center columns of the bricks placed in that row together with the columns of the holes in the row one below. Nothing about the shape of the rows above has any effect from then on. We keep this set as the state and let it flow downward.

this row one row below two rows below width 9 Covering a hole → a new obligationappears directly below its center The obligation and a hole arecleared together by one brick Only one obligation is left below,shifted 4 columns to the right
A brick of width 9 covers 9 cells, yet the only obligation it leaves for the row below is the single cell at its center. Red circles are holes, the orange frame is the newly created obligation. In the row below, that obligation and another hole can be cleared together by one brick, and the obligation shifts 4 columns to the right.

2. Within a row, decide column by column from left to right

Each row is scanned from its left end to the right. If the column at the scan position carries no obligation, we may move on without placing anything (placing one anyway is also allowed). If it does carry one, we must place exactly one brick whose left end is at that column: since we are deciding from left to right, only a brick with its left end there can still cover that column. After placing it, we skip the scan position ahead by the width covered, erase the obligations inside the covered range, and raise an obligation for the row below at the center column.

Under this procedure, the facts that no two bricks overlap, that every brick is supported at its center, and that every hole is covered hold automatically by construction, no matter which choices are made along the way. Every state in the search is bound to end up as a valid arrangement, so no feasibility check is needed.

scan position obligations for the row below still to cover in this row 60 column flags kept in one integer
Columns to the left of the scan position stand for “obligations to be covered in the row one below”, columns to the right for “columns still to be covered in this row”. The two never overlap, so the state can be represented by a single bit string as wide as the wall.

3. A beam search synchronized on columns

Each column offers at most six choices — “pass through” plus the five widths — so an exhaustive search is impossible. Instead we run a beam search that uses the scan position column as the synchronization point. Bricks of different widths advance by different distances, but matching up “states that have come as far as the same column” makes the comparison fair, and pruning takes effect once for every brick placed. States are ranked by the following value.

cost spent so far + number of remaining obligations × 10 + horizontal spread of the obligations

The second term is a rough estimate of “the cost of looking after one obligation all the way down”; without it, states that have simply not placed anything yet would monopolize the top of the beam. The third term is there to dislike states whose obligations are scattered left and right: among states with the same cost and the same number of obligations, it keeps the ones whose obligations are close to each other, because close obligations can later be cleared together by a single wide brick.

Among states holding the same set of obligations, only the one with the smallest cost is kept. The beam width is a few thousand, and for reconstruction we record “which brick was placed from which state” as a link to the parent. Once the flow reaches the bottom row every obligation has been resolved, so we simply output the state with the smallest cost. No later improvement stage such as simulated annealing is applied: this single pass (a few seconds) is all there is.

4. The resulting shape: staircases merging diagonally

A wide brick is not only cheaper per cell; it also has the property that even covering 9 cells, it leaves just one obligation for the row below. In other words, wide bricks act as mergers that bundle several pillars coming down from above into one. On top of that, because the support point is at the center, a brick of width 9 can shift an obligation column sideways by up to 4 columns. Putting the two together, pillars descending from distant holes can be drawn together diagonally and merged, reducing their number before they reach the floor.

The arrangement actually obtained looks like the figure below. A diagonal staircase extends from each hole, merging with others one after another on the way, so that by the time they reach the floor they have been gathered into a small number of pillars. The third term of the evaluation value (the penalty on spread) is what steers these merges to happen in rows as high up as possible.

width 1width 3width 5width 7width 9hole
An actual output (width 60 × height 40, 120 holes). Diagonal staircases come down from the holes and head for the floor while merging. The cost of this example is a little over one tenth of the cost of covering the whole wall with bricks of width 1.