Appendix C.2 — filler suffix [LG, LG, Sq] transition from trigger-happy state
ProvedTetrisHard.Rows.Padded.padded_filler_lg_lg_sq_stepcomplexity-theorytetris
Let be a reasonable rotation model and let and . Suppose bucket of satisfies and every satisfies . Then any zero-waste bucket play of the three-piece filler suffix reaching an board satisfies
Either all three pieces land in and complete a height increment on the active overflat bucket, or all three land in a single other bucket and create a dead plateau alongside the unresolved trigger-happy bucket (Propositions C.2-C.3, C.8, C.10-C.12, C.17-C.18, C.20, C.28-C.29, C.31, and C.33-C.34).
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedSoundness
Formal statement
namespace TetrisHard.Rows.Padded
theorem padded_filler_lg_lg_sq_step
(R : Rotation) (hReason : Reasonable R) (s s' H' : ℕ) (hs_le : s ≤ s')
(U₂ U' : Board) (us : List PieceState) (j₀ : Fin s) (h_th : ℕ) (h : Fin s → ℕ)
(hth0 : TriggerHappyAt U₂ j₀.val H' h_th)
(hunp0 : ∀ k : Fin s, k ≠ j₀ → UnpreppedAt U₂ k.val H' (h k))
(hp : NoRGSeqPlay R s s' H' U₂ [.LG, .LG, .Sq] us U')
(hall : AllFillableStrict R s s' H' U') :
OneOverflatState U' s H' j₀ (h_th + 2) h ∨
∃ j_dp : Fin s, DeadTriggerState U' s H' j_dp j₀ h_th h := 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