Processing Tetris queues with hold slots
2026-11-07
I really should have written this 1-2 years ago, but now I am here writing it after publishing the initial version of a tool implementing the algorithm. If (1) there are enough readers and (2) there are enough complaints about the lack of rigour/detail, I may write a follow-up article. I am also open to anyone showing me my work is completely wrong and dumb.
Context
Consider a Tetris piece sequence, like the classic 7-bag IJLOSTZ. Now, imagine we have access to a hold slot (as we do in modern Tetris) and we can use it to permute the sequence. For instance, we can hold the J piece until the T piece arrives, and subsequently hold the T piece until the end.
IJLOSTZ _
I_LOSTZ J
I_LOSJZ TOur sequence becomes ILOSJZT.
Problem
Given sequences and , letβs define that is reachable from iff can be permuted with the hold slot into . Let for a piece sequence .
Suppose we are given a set of sequences with the same length . We can assume that these are given as strings in some form. We would like to compute the set , which is the set of all sequences that are reachable with hold by some .
Note. It should be noted that (unless stated otherwise) I am assuming a constant-size alphabet and that integer/pointer/word operations run in time. I believe most of this analysis can be extended, though.
An obvious method
We can compute βliterallyβ. For each , we will compute , and somehow compute their union over all . Given , we can simulate the hold sequences: so long as there is a subsequent piece, we can choose (not) to press the hold key, so there are possibilities. This yields an upper bound of distinct queues, which can be less than with duplicate symbols in . We output each as a string of length , so at best we can compute and output these queues in time each. We thus obtain a running time of for each and total. To compute the union of all strings, we can insert them into a trie in time, matching the preceding phase and achieving an overall running time of .
Alternative formulation of holding
Above, we described the process of holding as choosing (not) to press the hold key. We can instead think of it as choosing whether to place the held piece before or after the current one. The hold slot is initially empty, so we consider the first piece held (this has no effect on what sequences are reachable). Now, our decisions line up: the current piece is held iff the held piece is put before it.
At each step we optionally swap the symbols at positions and to model our before/after choice. Consider the initial example IJLOSTZ, aligned to our current model (I is held). Recall that we held J and T, so with our new formulation we would perform the following procedure:
IJLOSTZ
IJLOSTZ dont swap I,J = hold J
ILJOSTZ swap J,L = dont hold L
ILOJSTZ swap J,O = dont hold O
ILOSJTZ swap J,S = dont hold S
ILOSJTZ dont swap J,T = hold T
ILOSJZT swap T,Z = dont hold ZUsing the alternative
Our observation immediately yields a nice method for actually computing given .
let f(s):
let T = {s}
for i = 1, 2, ..., n-1:
let T_swap =
{t with i, i+1 swapped | t in T}
T = T union T_swap
return TItβs also obvious that the running time is since the set does not more than double in size every iteration, giving us a geometric series. Then, to compute :
let f(S):
let T = {}
for s in S:
T = T union f(s)
return TAn improved method
Itβs not immediate to me the properties that make it correct (I may not even know them), but I think it should be relatively obvious that we can avoid computing all and taking their union. Instead, we let the initial value of be itself to process all βin parallelβ.
let f(S):
let T = S
for i = 1, 2, ..., n-1:
let T_swap =
{t with i, i+1 swapped | t in T}
T = T union T_swap
return TRunning time
We can obtain a (generally) loose upper bound on running time using the number of reachable sequences . Clearly, the size of is non-decreasing across iterations, so it always holds that . Each iteration, we produce new strings in time and perform a union, giving us either an expected with hashing or a worst-case running time with various methods (ordered set, sort + unique). Thus, the overall running time over all iterations is .
This is already an improvement to the worst case over the initial method. Let and consider when is near saturation i.e. . The initial method runs in , while the new method runs in . While can be rather large, should be linearithmic in . So the extra factor on top of is a polynomial vs exponential .
Using a better data structure
Since we eliminated the concept of a hold slot by using swaps instead, itβs easy to pick a different data structure for storing sets of strings. From a trie , we can produce also as a trie; this happens in linear time and it can be shown the number of nodes in is linear to that of . Then, we can take their union in linear time as well. Similarly to before, the number of nodes in is non-decreasing since and a subset certainly does not need more nodes. If we let be the number of nodes in the resulting trie , then our algorithm for computing runs in time per iteration for overall running time.
The value of can fluctuate as . However, if we consider some worst-case, very saturated sets :
- contains (nearly) all permutations of a string with many distinct symbols
- contains (nearly) all possible strings
β¦then is closer to because the trie is dense.
Donβt we accept/return a set of strings?
If we get a set of strings, we can construct a trie for this set in time. Streaming the final set of strings runs in time. Since , the overall running time is , including computing .
Brief running time comparison
Letβs assume contains all permutations of a string that has distinct symbols (all distinct). We have and , and it turns out that the number of nodes in a trie storing these strings is also .
- Initial:
- Improved: or expected
- Improved + trie:
Alternatively, letβs assume contains all possible strings, and the alphabet is the 7 tetrominoes. we have and . The trie has nodes.
- Initial:
- Improved: or expected
- Improved + trie:
So, I think we did a good job.
Actual performance
I wrote up a serial trie implementation that packs nodes as a contiguous pre-order traversal. Random access isnβt needed, so itβs optimized for setwise operations and streaming. Iβll write another article about that if I want to. Itβs quite fast on my machine: given as all permutations of IIJJLLOOSSTZ, it builds the trie in about 700ms. You can check its performance.
Conclusion
I had fun designing this algorithm and engineering its Rust implementation. This section will answer small questions that donβt warrant a separate post, and I might add to it.
What if I want to compute the reverse?
Let , and . To compute , we follow a similar procedure to but perform the swaps in reverse order:
let g(S):
let T = S
for i = n-1, n-2, ..., 1:
let T_swap =
{t with i, i+1 swapped | t in T}
T = T union T_swap
return TCombining and is a nice workflow for research. Given the set of queues , we would like to determine which ones can stack a specific shape, but we also want to consider hold slots. We compute and run our solver on the queues in to get , those that can stack the shape. Then, we compute to get all queues that can stack the shape using a hold slot, and we take the intersection to restrict it to the input queues.
What if I have multiple hold slots?
The tool I wrote generalizes to any number of slots, but I think it requires a more involved correctness argument even when hand-waved. I can write about it in another post, because this one is already quite long despite the lack of detail and rigour.
@2026 bzy.