Appendix C.2 — elimination of simultaneous dead-plateau and trigger-happy configurations
ProvedTetrisHard.Rows.Padded.padded_dead_trigger_eliminatorcomplexity-theorytetris
Let be a reasonable rotation model and let and . From any board in (containing a dead plateau in bucket , a trigger-happy configuration in bucket , and unprepped configurations in all remaining buckets), neither a terminator prefix nor a subsequent filler prefix admits a zero-waste bucket play to an board:
and analogously for .
Consequently, the dead-plateau branch of a filler block can never survive the next two pieces of integerBlock, forcing every filler block in a valid Phase-1 play to remain in the active bucket .
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedSoundness
Formal statement
namespace TetrisHard.Rows.Padded
theorem padded_dead_trigger_eliminator
(R : Rotation) (hReason : Reasonable R) (s s' H' : ℕ) (hs_le : s ≤ s') :
(∀ (U U' : Board) (ts_tail : List Piece) (us : List PieceState)
(j_dp j_th : Fin s) (h_th : ℕ) (h : Fin s → ℕ),
DeadTriggerState U s H' j_dp j_th h_th h →
NoRGSeqPlay R s s' H' U (.Sq :: .Sq :: ts_tail) us U' →
AllFillableStrict R s s' H' U' → False) ∧
(∀ (U U' : Board) (ts_tail : List Piece) (us : List PieceState)
(j_dp j_th : Fin s) (h_th : ℕ) (h : Fin s → ℕ),
DeadTriggerState U s H' j_dp j_th h_th h →
NoRGSeqPlay R s s' H' U (.LG :: .LS :: ts_tail) us U' →
AllFillableStrict R s s' H' U' → False) := 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