Appendix C.2 — multi-bucket initiator and terminator state transitions
ProvedTetrisHard.Rows.Padded.padded_initiator_and_terminator_stepcomplexity-theorytetris
Let be a reasonable rotation model and let and . Under strictly fillable zero-waste bucket play:
- Initiator transition. Starting from a board in state , any play of reaching an board places all three pieces into a single bucket and transitions to an overflat state of height :
- Terminator transition. Starting from , any play of reaching an board places both squares in bucket and restores all buckets to unprepped state with replaced by :
This formalizes the initiator and terminator transitions of Appendix C.2 via Propositions C.1-C.8, C.17-C.18, C.20, and C.23.
Preamble
import Definitions.Def_TetrisHard_Rows_PaddedSoundness
Formal statement
namespace TetrisHard.Rows.Padded
theorem padded_initiator_and_terminator_step
(R : Rotation) (hReason : Reasonable R) (s s' H' : ℕ) (hs_le : s ≤ s') :
(∀ (U U' : Board) (us : List PieceState) (h : Fin s → ℕ),
AllUnpreppedHeights U s H' h →
NoRGSeqPlay R s s' H' U initiator us U' →
AllFillableStrict R s s' H' U' →
∃ j₀ : Fin s, OneOverflatState U' s H' j₀ (h j₀ + 2) h) ∧
(∀ (U U' : Board) (us : List PieceState) (j₀ : Fin s) (h₀ : ℕ) (h : Fin s → ℕ),
OneOverflatState U s H' j₀ h₀ h →
NoRGSeqPlay R s s' H' U terminator us U' →
AllFillableStrict R s s' H' U' →
AllUnpreppedHeights U' s H' (Function.update h j₀ (h₀ + 4))) := 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