壁の穴をレンガで覆う — 上から下へ流す 1 本のビームサーチ

構成した配置は常に条件を満たし、探索は「どこにどの幅を置くか」の一本道の決定列になる。

1. 支えの条件が向きを決める

レンガは中央の真下が埋まっていないと置けない。裏を返せば、レンガを 1 つ置くたびに「中央の真下のマスを覆う」義務が新しく生まれ、それが床まで連鎖する。覆うべき穴も同じ形の義務なので、 壁を上の行から下の行へ順に処理するのが自然な向きになる。

このとき、ある行の処理を終えた時点で次に持ち越すべき情報は、 その行に置いたレンガの中央の列と1 つ下の行にある穴の列を合わせた「覆う義務のある列の集合」だけである。上の行がどんな形だったかは以後まったく効いてこない。これを状態として持って下へ流していく。

2. 行の中は左から右へ、1 列ずつ決める

各行は左端から右へ走査する。走査位置の列に義務が無ければ何も置かずに次へ進んでよい（あえて置くのも許す）。義務があれば、その列を左端とするレンガを必ず 1 つ置く。左から順に決めている以上、その列を覆えるのは左端がそこにあるレンガだけだからである。置いたら覆った幅のぶん走査位置を飛ばし、覆った範囲の義務を消して、中央の列に下の行への義務を立てる。

この手順だと、重なりが起きないこと・すべてのレンガが中央で支えられること・穴がすべて覆われることが、途中でどう選んでも構成上自動的に成り立つ。探索中のどの状態も必ず正しい配置に行き着くので、実行可能性の判定は要らない。

3. 列を同期点にしたビームサーチ

1 列あたりの選択肢は「素通り」と 5 種類の幅で最大 6 通りあり、全探索はできない。そこで走査位置の列を同期点にしたビームサーチを行う。幅の違うレンガでは進む距離が異なるが、「同じ列まで来た状態どうし」を突き合わせれば公平に比較でき、レンガ 1 個を置くごとに枝刈りが効く。各状態の優劣は次の値で測る。

第 2 項は「義務 1 つを最後まで面倒みるのにかかる代金」のおおまかな見積もりで、これが無いと「まだ何も置いていないだけ」の状態が上位を独占してしまう。第 3 項は義務が左右に散らばった状態を嫌う項で、同じ代金・同じ義務数なら義務どうしが近い状態を残す。近ければ後で 1 本の幅広レンガでまとめて回収できるからである。

同じ義務の集合を持つ状態は代金が最小の 1 つだけ残す。ビーム幅は数千で、復元用に「どの状態からどのレンガを置いたか」を親へのリンクで記録しておく。最下段まで流し終えると義務はすべて解消済みなので、代金が最小の状態をそのまま出力する。焼きなましなどの後段の改善は行わず、この 1 パス（数秒）だけで終わり。

4. 出来上がる形：斜めに合流する階段

幅の広いレンガは 1 マスあたりの単価が安いだけでなく、9 マス覆っても下の行に残す義務はたった 1 つという性質を持つ。つまり幅広のレンガは、上から下りてきた複数の柱を 1 本に束ねる合流器として働く。さらに支持点が中央にあるおかげで、幅 9 のレンガは義務の列を最大 4 列だけ横へずらせる。この 2 つを合わせると、離れた穴から下りてきた柱を斜めに寄せて合流させ、床に着くまでに本数を減らしていける。

実際に得られる配置は下図のようになる。各穴から斜めの階段が伸び、途中で次々と合流して、床に届くころには少数の柱にまとまっている。評価値の第 3 項（広がりへのペナルティ）は、この合流をできるだけ上の行で起こさせるための誘導になっている。