Section 6.2 — chimney barrier dichotomy and zero-waste Phase-1 bucket lifting
ProvedTetrisHard.Rows.Padded.paddedReservoir_chimney_reductioncomplexity-theorytetris
Let be an admissible reasonable rotation model of radius , let be a valid normalized 3-Partition instance with , and let , , , and . For every cleared-row count attainable in , let and . Then either
or has every bucket unprepped at initial height and the Phase-1 piece sequence lifts to a zero-waste bucket play on that fills all buckets up to height :
If no prefix of the pre-square pieces clears all chimney rows and upper rows, the surviving one-wide chimney blocks squares from entering the reservoir and row-occupancy parity bounds square row clears above row . Otherwise, modulo-4 empty-cell invariance eliminates the 4 slack cells of the final key, forcing zero waste across all Phase-1 pieces.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedSoundness
Formal statement
namespace TetrisHard.Rows.Padded
theorem paddedReservoir_chimney_reduction
(R : Rotation) (hR : R.Admissible) (hReason : Reasonable R)
(P : ThreePartition) (hP : P.Valid) (hN : P.Normalized) (hs : 0 < P.s)
(pad K st r : ℕ)
(hpad : max R.radius 2 + 2 ≤ pad)
(hK : maxJump R + 2 ≤ K)
(hst : 5 * max R.radius 2 + 12 ≤ st)
(v : ℕ) (hatt : Attainable R (paddedReservoirGame P pad K st r) v) :
v ≤ paddedNoBound P pad K st ∨
(AllUnpreppedHeights (dropRows (paddedReservoirBoard P pad K st r) (r + 2 + 4 * K))
P.s (12 * pad + baseHeight P) (fun _ => 12 * pad + 4) ∧
∃ us us_I U_num U_end,
NoRGSeqPlay R P.s (P.s + pad) (12 * pad + baseHeight P)
(dropRows (paddedReservoirBoard P pad K st r) (r + 2 + 4 * K))
(numberPieces P) us U_num ∧
NoRGSeqPlay R P.s (P.s + pad) (12 * pad + baseHeight P)
U_num (List.replicate P.s .I) us_I U_end ∧
∀ j : Fin P.s, BucketFull U_end j.val (12 * pad + baseHeight P)) := by sorry
end TetrisHard.Rows.Padded
Source
Demaine, Hohenberger and Liben-Nowell, Tetris is Hard, Even to Approximate, arXiv:cs/0210020v1, Section 5.3-5.4 (pp. 12-18), Section 6.2 (pp. 19-21), and Appendix C.1-C.2 (pp. 25-33), https://arxiv.org/abs/cs/0210020v1