Appendix C.2 — filler prefix [LG, LS] transition from one-overflat to trigger-happy
ProvedTetrisHard.Rows.Padded.padded_filler_lg_ls_stepcomplexity-theorytetris
Let be a reasonable rotation model and let and . Starting from a board in state , every zero-waste bucket play of the two-piece filler prefix that reaches an board must place both pieces in bucket , advancing to a trigger-happy configuration at height while leaving every other bucket unprepped at height :
Any alternative placement of into an unprepped bucket or a non-canonical overflat position produces an unfillable bucket by Propositions C.2, C.4, C.9, C.21-C.22, and C.24-C.27.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedSoundness
Formal statement
namespace TetrisHard.Rows.Padded
theorem padded_filler_lg_ls_step
(R : Rotation) (hReason : Reasonable R) (s s' H' : ℕ) (hs_le : s ≤ s')
(U U₂ : Board) (us : List PieceState) (j₀ : Fin s) (h₀ : ℕ) (h : Fin s → ℕ)
(hof : OneOverflatState U s H' j₀ h₀ h)
(hp : NoRGSeqPlay R s s' H' U [.LG, .LS] us U₂)
(hall : AllFillableStrict R s s' H' U₂) :
TriggerHappyAt U₂ j₀.val H' (h₀ + 4) ∧ ∀ k : Fin s, k ≠ j₀ → UnpreppedAt U₂ k.val H' (h k) := 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