Tetris

Tetris ist ein beliebtes Computerspiel erstmals veröffentlicht in 1984^[1]. Das Ziel des Spiels ist es nacheinander von oben nach unten fallende Spielsteine so zu verschieben und platzieren, dass möglichst viele horizontale Reihen gefüllt werden. Eine vollständig gefüllte Reihe wird gelöscht und die spielende Person erhält Punkte. Das Spiel endet, falls die Spielsteine zu hoch gestapelt werden und einer den oberen Spielfeldrand berührt.

Spielablauf

In Tetris erscheinen Spielsteine, auch Tetrominos genannt, in verschiedenen Formen, wobei stets nur ein Spielstein nach dem anderen erscheint.

Abb. 1: Alle Tetris Spielsteine mit beigefügten Namen (eigene Darstellung, Namen und Orientierungen adaptiert aus Tetris is hard, even to approximate^[2])

In den meisten Versionen des Spiels ist die Reihenfolge dieser Spielsteine zufällig. Die spielende Person steuert aktiv den neuen Spielstein, der kontinuierlich von oben nach unten fällt, bis dieser entweder auf den unteren Rand den Spielfeldes oder von oben auf einen zuvor platzierten Spielstein stößt. Der fallende Spielstein kann beliebig oft nach links oder nach rechts verschoben oder um 90º rotiert werden. Die einzige Begrenzung hierbei ist, dass der Spielstein hierbei aber nicht durch andere Spielsteine wandern darf. Sobald eine Reihe vollständig gefüllt ist, verschwindet sie, die Reihen über der freigeräumten Reihe werden um eins nach unten verschoben und man erhält Punkte. Es können auch mehrere Reihen gleichzeitig freigeräumt werden. Werden mit Hilfe eines "I"-Steins vier Reihen gleichzeitig geräumt, bezeichnet man dies als Tetris. Das Ziel des Spiels ist es möglichst viele Reihen zu füllen und löschen. In Tetris kann meist nicht gewonnen werden, da das Spiel einfach so lange weiter geht, bis ein Spielstein den oberen Spielfeldrand berührt.

Die "Offline Version" von Tetris

Um den späteren Beweis für die NP-Vollständigkeit zu vereinfachen, verwenden wir eine sog. offline Version von Tetris. Diese offline Version unterscheidet sich vom herkömmlichen Tetris hauptsächlich in einem Aspekt. Die Reihenfolge der Spielsteine ist vollständig deterministisch und endlich, im Vergleich zur probabilistischen und unendlichen Spielsteinreihenfolge des üblichen Spiels. Da die Schwierigkeit von offline Tetris grundlegend einfacher ist als die des herkömmlichen Tetris, können wir somit die Komplexität des herkömmlichen Tetris erahnen.

Komplexität von Tetris-Spielzielen

Viele verschiedene Ziele sind in (offline) Tetris NP-Vollständig^[2:1], darunter:

1. Das Maximieren der Anzahl von freigeräumten Reihen bei einer gegeben Spielsteinreihenfolge
2. Das Maximieren der Anzahl an platzierten Spielsteinen bevor das Spiel zu Ende geht
3. Das Maximieren der Anzahl an Tetrisen
4. Das Minimieren der maximal erreichten Höhe bei einer gegeben Spielsteinreihenfolge

Formalisierung des gesamten Spielablaufs

Für die Formulierung unseres \mathrm{TETRIS}-Problems benötigen wir klare Definitionen unseres Spielzustandes

Das Spielfeld

Unser Spielfeld B besteht aus m Reihen und n Spalten. Die Felder sind dabei von unten nach oben und links nach rechts indiziert, wobei für jedes Feld \langle i,j \rangle mit i \in \{ 1,...,m \} und j \in \{ 1,...,n \} gilt, dass es entweder gefüllt oder nicht gefüllt ist. Außerdem können keine gefüllten Reihen existieren, da diese sofort geräumt werden und es existieren keine vollständig leeren Reihen unter gefüllten Feldern.

Die Spielsteine

Abb. 2 Spielsteine mit markiertem Zentrum (eigene Darstellung, adaptiert aus Tetris is hard, even to approximate^[2:2])

Wir können den Zustand jedes unserer sieben Spielsteine mit Hilfe eines 4-Tupels P = \langle t,o, \langle i,j \rangle , f \rangle darstellen.

• t \in \{ \text{Sq, LG, RG, LS, RS, I, T} \} beschreibt hierbei um welche Art Spielstein es sich handlet
• o \in \{0^{\circ},90^{\circ},180^{\circ},270^{\circ} \} beschreibt die Orientierungen ausgehend von dem Urzustand des Spielsteins
• \langle i,j \rangle die Position des Zentrums des Spielsteins (s. Abb. 2) auf unserem Spielfeld
• f \in \{ fixed,unfixed \} beschreibt ob der Spielstein sich noch bewegen kann oder nicht

Zum Beispiel wird der Zustand des folgenden Spielsteins mit dem Tupel P= \langle T, 180^{\circ}, \langle 1,2 \rangle , fixed \rangle beschrieben:

Abb. 3: T auf dem Spielfeld (eigene Darstellung)

Rotieren

Unser Rotationsmodell ist eine berechenbare Funktion R: \langle P, \theta , B \rangle \mapsto P', wobei P und P' Zustände sind, \theta \in \{-90^{\circ}, 90^{\circ}\} der Rotationswinkel und B unser Spielfeld.

Breukelaar et al formulierten für R folgende Bedingungen:^[2:3]

1. Falls die Rotation legal ist, dann gilt für ein P = \langle t,o, \langle i,j \rangle , f \rangle, P'= \langle t,(o +\theta) \mod 360^{\circ}, \langle i',j' \rangle , f \rangle wobei i' und j' die neue Position des Zentrums nach der Rotation sind. Falls die Rotation nicht legal ist, gilt P' = P
2. Die Legalität hängt nur von der O(1)-großen Nachbarschaft des Spielsteins ab
3. Für eine "leere" Nachbarschaft gilt also, dass die Rotation legal ist
4. Falls eine Rotation legal ist, dann belegt P' kein Feld was bereits in B belegt ist
5. Die Funktion R muss "angemessen" sein:
   5.1 Ein Spielstein kann nicht von einer Region des Spielfelds zu einer anderen springen. Es muss ein Pfad von leeren Feldern von P zu P' in B existieren
   5.2 Ein Spielstein kann nicht an einer übermäßig eingeengten Stelle des Spielfelds vorbeikommen. In anderen Worten, wenn eine ein Feld breite Lücke existiert, darf keiner unserer Steine außer möglicherweise ein I-Stein hindurchkommen

Der Spielablauf

Jetzt können wir also den Spielablauf an sich beschreiben. Unsere legalen Spielzüge für ein Spielstein P = \langle t,o, \langle i,j \rangle , unfixed \rangle und einem Spielfeld B sind also:

1. Eine Rotationen mit P' = R(P,\pm 90^{\circ}, B)
2. Eine Verschiebung um eine Spalte, sofern die benachbarten Felder von P in B hinreichend frei sind und keine Blockaden oder anderen Spielsteine die Bewegung verhindern. Hier ist unser neuer Zustand P' = \langle t,o, \langle i,j \pm 1 \rangle , unfixed \rangle
3. Unseren Spielstein um eine Reihe fallen lassen, falls alle Felder direkt unterhalb unseres Spielsteins frei sind in B. Der neue Zustand ist P' = \langle t,o, \langle i-1,j \rangle , unfixed \rangle
4. Eine Fixierung, falls unser Spielstein den unteren Spielfeldrand oder einen anderen Speilstein unter sich berührt. P' = \langle t,o, \langle i,j \rangle , fixed \rangle

Für einen fixierten Spielstein gibt es logischerweise keinen legalen Zug, da wir immer nur unseren einen nicht fixierten Spielstein kontrollieren.

Wir definieren uns außerdem noch einen Ablauf (trajectory) \sigma eines Spielsteins P auf unserem Spielfeld B, was einfach eine Reihe von legalen Zügen ist, die in einer Fixierung enden. Nach eines solchen Ablaufs erhalten wir ein neues Spielfeld B'. Z.B. haben wir das leere Spielfeld B. Wir rotieren unseren Spielstein zweimal um 90^{\circ} im Uhrzeigersinn und bewegen ihn in das linksuntere Eck des Spielfelds. Dies ist unser Ablauf \sigma, der zum Spielfeld B' (vgl. Abb. 3) führt.

Da in unserer offline Version von Tetris, alle Spielsteine im vorhinein bekannt sind. Definieren wir unser Tetris Spiel \mathcal{G} = \langle B,P_1,...,P_p \rangle. In anderen Worten, unser Spielfeld zu Beginn und unsere p Spielsteine die folgen werden.

Unser Spielablauf kann somit also mit Hilfe einer Ablaufssequenz (trajectory sequence) \Sigma beschrieben werden. \Sigma ist einfach eine Sequenz B_0,\sigma_1, B_1,...,\sigma_p, B_p für unser Spiel \mathcal{G}, wo der Ablauf \sigma_i eines Spielsteins P_i auf dem Spielfeld B_{i-1} für das neue Spielfeld B_i verantwortlich ist.

Die NP-Vollständigkeit von Tetris

Tetris liegt in NP

Wie zuvor erwähnt, gibt es in Tetris mehrere Ziele welche wir betrachten können. Formal definieren wir also unser \text{TETRIS} Problem für ein Ziel \Phi wie folgt:

Eingabe: Ein Tetris Spiel \mathcal{G}=\langle B,P_1,...,P_p \rangle
Frage: Existiert eine Ablaufssequenz \Sigma, so dass \Phi(\mathcal{G},\Sigma) erfüllt ist?

Breukelaar et al zeigen, dass für jedes azyklische Ziel \Phi gilt, dass \text{TETRIS} \in \mathrm{NP}^[2:4]. Ein Ziel \Phi ist azyklisch, falls für alle Spiele \mathcal{G} eine Ablaufssequenz \Sigma existiert, in der keine Spielsteinzustände wiederholt werden, wie bspw. unseren Spielstein 4-mal im Uhrzeigersinn um 90^{\circ} rotieren. Die Ziele die wir betrachten sind azyklisch, da sie nur davon abhängig sind wo letztenendes der Spielstein platziert wird. Indem wir die Zustände einzelnd abprüfen, können wir also den Wahrheitswert von \Phi(\mathcal{G},\Sigma) in polynomieller Zeit \mathrm{poly}(|\mathcal{G}|,|\Sigma|) überprüfen^[2:5].
Angenommen wir haben also ein Spiel \mathcal{G} = \langle B, P_1, \dots, P_p \rangle, gesucht ist ein \mathrm{NP} Algorithmus. Wir raten zunächst eine azyklische Ablaufssequenz \Sigma. Das Überprüfen ob \Sigma legal ist erfolgt erneut in polynomieller Zeit \mathrm{poly}(|\Sigma|), in dem wir die einzelnen Züge bei den gegebenen Spielfeldern überprüfen. Da wir uns eben auf azyklische \Sigma beschränken, ist die Anzahl an Zuständen P in den p Abläufen \sigma auf 4 \cdot |B| + 1 begrenzt. Der Grund dafür ist, dass unser Spielstein maximal in jeder Position \langle i,j \rangle in seinen 4 Orientierungen auftauchen kann und zuletzt noch in einer fixierten Position. Somit gilt |\Sigma| = \mathrm{poly}(|\mathcal{G}|). Wir können also in \mathrm{poly}(|\mathcal{G}| , |\Sigma|) = \mathrm{poly}(|\mathcal{G}|) überprüfen ob \Phi(\mathcal{G},\Sigma) erfüllt ist und da wir azyklische \Phi betrachten, genügt es azyklische \Sigma zu erraten.

Reduktionsbeweis

3-PARTITION

In diesem Reduktionsbeweis reduzieren Breukelaar et al von \text{3-PARTITION} auf das \text{TETRIS} Problem. Das \text{3-PARTITION} Problem ist nach Garey und Johnson NP-vollständig^[3] und ist dabei wie folgt definiert:

Eingabe: Eine Reihe von nicht-negativen, ganzen Zahlen a_1,...,a_{3s} und eine nicht-negative, ganze Zahl T, wobei für jede Zahl a_i gilt T/4 < a_i < T/2
Frage: Existiert eine Partitionierung in Dreiermengen A_1,...,A_s, so dass für alle A_j gilt, \sum_{a_i \in A_j} a_i = T?

Aufgrund der späteren Konstruktion unseres Spielfelds, wollen wir nur ein T erlauben, welches durch 4 teilbar ist. Dafür können wir einfach unsere bestehende Partitionsinstanz nehmen und alle Zahlen, also a_1,...,a_{3s} und T, mit 4 multiplizieren.

Konstruktion des Spielfelds

Hier beginnen wir zuerst mit dem Ziel "Maximieren der Anzahl an freigeräumten Reihen", auf mehr Ziele wird später eingegangen. Die Höhe und Breite unseres Spielfelds ist immer abhängig von unserer Partitionsinstanz und es gibt mehrere Wege es aufzubauen. Eine Methode wurde von Demaine et al in 2003 vorgestellt^[4]. Hier konzentrieren wir uns aber auf die überarbeitete, vereinfachte Methode aus 2004, nach der Zusammenführung der Paper von Demaine et al und Breukelaar et al^[2:6]. Die Idee ist hierbei, dass unser Spielfeld s sogenannte "Buckets" besitzt, welche die s Dreiergruppen unser Partition repräsentieren. Die Breite dieser Buckets beträgt dabei immer 4, die Höhe der Buckets ist jedoch mit 5T+18 abhängig von unserer Partitionsinstanz. Der Aufbau der Buckets folgt hierbei einem periodischen Muster:

• Die erste Spalte ist leer bis auf die letzten zwei Reihen
• Die zweite Spalte ist vollkommen leer
• In der dritten Spalte, sind immer abwechselnd drei Reihen gefüllt und zwei Reihen leer
• Die vierte Spalte ist vollkommen gefüllt

Was zu diesem Ergebnis führt:

Abb. 4: Ein Bucket, bearbeitet^[2:7]

Zusätzlich benötigen wir für die spätere Vollständigkeit und Korrektheit unseres Tetris Ziels eine sogenannte Lock. Diese ist 5T + 18 Blöcke hoch und 3 Blöcke breit, jedoch verwenden wir nur eine. Für die Lock gilt:

• Die erste Spalte ist gefüllt, bis auf die oberste Reihe
• Die zweite Spalte ist gefüllt, bis auf die obersten zwei Reihen
• Die dritte Spalte ist leer, bis auf die zweitoberste Reihe

Abb. 5: Die Lock, bearbeitet^[2:8]

Wie bereits erwähnt repräsentieren unsere Buckets die Dreiermengen, weshalb wir s Buckets benötigen, welche allesamt jeweils 4 Blöcke breit sind. Zusätzlich haben wir unsere 3 Block breite Lock, was zu einer Spielfeldbreite von 4s + 3 führt. Da die Buckets und die Lock beide 5T+18 Blöcke hoch sind, muss unser Spielfeld ebenfalls mindestens so hoch sein. Um aber der spielenden Person die Möglichkeit zu geben die Spielsteine zu bewegen und um später zu ermöglichen gewisse Einschränkungen einzuführen, wie bpsw. die Begrenzung an maximalen Drehungen oder Verschiebungen, fügen wir ein paar zusätzliche Reihen hinzu auf die später näher eingegangen wird. Unser gesamtes Spielfeld sieht dann also wie folgt aus:

Abb. 6: Das Spielfeld^[2:9]

Idee und Ablauf

Um nun von unserer \text{3-PARTITION} Instanz auf unser \text{TETRIS} Problem zu reduzieren, erhalten wir abhängig von unseren Zahlen eine unterschiedliche Anzahl an Spielsteinen. Wir gehen nach und nach unsere Menge an 3s Zahlen durch und erhalten für jede Zahl a_i:

1. Den sog. Initiator, welcher aus einem \text{RG}-Stein besteht
2. Den Filler, wo wir a_i mal die Sequenz \langle \text{Sq, LG, Sq}\rangle erhalten
3. Den Terminator, welcher aus einem \text{Sq}-Stein und einem \text{I}-Stein besteht.

Sei z.B. unsere erste Zahl die wir abarbeiten a_1 \vcentcolon = 4, wir erhalten dann somit der Reihe nach die Sequenz:

1. \langle \text{RG} \rangle
2. \langle\text{Sq, LG, Sq, Sq, LG, Sq, Sq, LG, Sq, Sq, LG, Sq}\rangle
3. \langle \text{Sq, I} \rangle

Abb. 7: Füllen eines Buckets mit a_1 = 4 (eigene Darstellung)

Das Ziel der spielenden Person ist es, alle Buckets auf die gleiche Höhe zu füllen. Intuitiv finden wir dabei die Dreiermengen, repräsentiert durch die Buckets, in die die Zahlen gehören. Genau dann wenn wir eine "Ja"-Instanz unseres \text{3-PARTITION}-Problems haben und die Steine richtig zusammensetzen sieht unser Spielfeld so aus:

(Abb. 8: Alle Buckets gefüllt^[2:10])

Nun erhalten wir zum Abschluss noch folgende Spielsteine:

1. s-mal ein RG-Stein
2. Ein T-Stein
3. \frac{5T+16}{4}-mal ein I-Stein

Wir benötigen die s \text{ RG}-Steine, um unsere Buckets vollständig zu füllen. Nachdem alle Buckets gefüllt sind, öffnen wir unsere Lock mit dem \text{T}, da dies nun die oberen 2 Reihen räumt. Dies ermöglicht uns, unsere letzte Spalte mit \frac{5T+16}{4} \text{ I}-Steinen zu füllen und die 5T+16 Reihen zu räumen. Da wir in unserer Partitionsinstanz nur ein T erlauben, welches durch 4 teilbar ist, erhalten wir eine ganze Zahl an \text{I}-Steinen.

Vollständigkeit und Korrektheit

Breukelaar et al beginnen hierbei zuerst mit der Annahme, dass wir eine "Ja"-Instanz unseres \text{3-PARTITION} Problems haben^[2:11].
Da wir eine "Ja"-Instanz vor uns haben, können unsere Zahlen a_1,\dots,a_{3s} in die Dreiermengen A_1,\dots,A_s so aufgeteilt werden, dass \sum_{a_i \in A_j} a_i = T. Um zu zeigen, dass alle Buckets somit gefüllt werden können, betrachte A_j = \{ a_x,a_y,a_z \}. Für jede Zahl gilt nach unserem vorher beschlossenen Spielablauf, dass wir zuerst unseren Initiator erhalten, dann a_i mal unsere Filler-Sequenz und zuletzt einmal unseren Terminator. Füllen wir unseren leeren Bucket j nach dem Muster, welches zuvor genannt wurde, füllen wir mit dem Initiator die ersten 3 Reihen. Mit dem wiederholenden Muster unseres Fillers füllen wir 5 Reihen a_x-mal. Mit unserem Terminator füllen wir weitere 2 Reihen vollständig. D.h. nachdem wir a_x bearbeitet haben, sind 3 + 5a_x + 2 Reihen gefüllt, was bedeutet nach unserer gesamten Dreiermenge A_j haben wir 3 + 5a_x + 2 + 3 + 5a_y + 2 + 3 + 5a_z + 2 = 5a_x + 5a_y + 5a_z + 15 = 5(a_x+a_y+a_z) + 15 = 5T + 15 Reihen vollständig gefüllt.
Danach folgt unsere "Abschlusssequenz". Mit unseren s \text{ RG}-Steinen füllen wir unsere Buckets bis zu 5T+18. Öffnen die Lock mit unserem \text{T}-Stein, was Reihen 5T+18 und 5T+17 freiräumt und füllen den Rest mit unseren \frac{5T+16}{4} \text{ I}-Steinen. D.h. das gesamte Spielfeld wird geräumt und somit die Anzahl an freigeräumten Reihen maximiert, falls wir eine "Ja"-Instanz besitzen.

Um zu sehen, dass der genannte Ablauf der einzig valide ist, genügt es die Kombinationen zu betrachten, welche der spielenden Person zur Verfügung stehen.

Abb. 9: Initiator Stellung, alle nicht-Initiator Spielsteine^[2:12]

Betrachten wir einen Bucket der einen Initiator erwartet, führen die \text{Sq-, LG-} und \text{I}-Steine immer dazu, dass bestimmte Bereiche unseres Spielfelds für zukünftige Teile blockiert sind. Dies läuft für die anderen Möglichkeiten analog ab. Es ist auch leicht zu sehen, warum wir keinen Spielstein über der Reihe 5T+18 platzieren sollten, um die Anzahl an freigeräumten Reihen zu maximieren. Wir bekommen nämlich genau so viele Steine, um die Felder die in den teilsgefüllten Reihen 1 bis 5T+18 sind, zu füllen. Um also 5T+18 Reihen zu räumen, müssen wir unsere Spielsteine genau in diese Felder der teilsgefüllten Reihen legen.

Haben wir eine "Nein"-Instanz, können wir keine Dreiermengen bilden, wo alle Elemente immer zu T auf summieren. Intuitiv, können wir also nicht alle Buckets zur gleichen Höhe füllen. Um die Anzahl an freigeräumten Reihen zu maximieren müssen wir aber, wie man sieht, der Sequenz folgen, aber dürfen ebenso keinen Spielstein über der Reihe 5T+18 platzieren. Somit können wir also nicht die Anzahl an freigeräumten Reihen maximieren.

Andere Ziele und Begrenzungen

Für andere Ziele wird der Ablauf der Reduktion von Breukelaar et al lediglich leicht angepasst.

Maximieren der Anzahl an platzierten Spielsteinen bevor das Spiel zu Ende geht

Die Idee hinter der Modifikation des Spielfelds für das Ziel der Maximierung der Anzahl bevor das Spiel zu Ende geht ist, dass wir eine Niederlage für eine "Nein"-Instanz erzwingen wollen. Wir erweitern unser Spielfeld um 4 Spalten, wobei die obersten 5T+18 Reihen gefüllt sind. Außerdem fügen wir r Reihen unter unserem Spielfeld hinzu. Zuerst zwei gefüllte Reihen, welche aber eine \mathrm{T}-förmige Lock besitzt in den letzten 3 Spalten, ähnlich wie unser originales Feld. Die restlichen Reihen sind leer bis auf die erste Spalte.

Abb. 10: Das Spielfeld für das Maximieren der Anzahl an platzierten Spielsteinen^[2:13], bearbeitet

Zusätzlichlich erhalten wir nach unser originalen Spielsteinsequenz noch ein \mathrm{T} und \frac{R}{4}-mal ein \mathrm{Sq}, wobei R = r(4s+6). Wenn unser r groß genug ist, heißt so dass R \geq 2(O((T+s)s)) + 4, erzwingen wir eine Niederlage für eine "Nein"-Instanz, da unser Spielfeld mit 4s + 7 Spalten ungerade ist und somit nur mit \mathrm{Sq}-Steinen keine Reihe geräumt werden kann. Nur genau dann wenn, wir eine "Ja"-Instanz besitzen, können die 5T+18 Reihen wie gewohnt geräumt werden und wir können somit den unteren Bereich problemlos mit unseren \mathrm{Sq}-Steinen füllen.

Maximieren der Anzahl an Tetrisen

Hierfür wird unser Spielfeld nur leicht angepasst. Wir fügen einfach 4 weitere Reihen unterhalb unseres Spielfelds hinzu, welche komplett gefüllt sind bis auf die vierte Spalte und erhalten am Ende unsere bisherigen Spielsteinesequenz noch einen weiteren \text{I}-Stein. Der Grund dafür ist, da zwar mit einer "Nein"-Instanz nicht 5T+18 Reihen geräumt werden können, kann dennoch die Anzahl an Tetrisen bei dem vorherigen Spielfeld gleich sein, da wenn die spielende Person 5T+16 Reihen freiräumt somit trotzdem \frac{5T+16}{4} Tetrise erzielen könnte. Das neue Feld sorgt dafür, dass somit das letzte Tetris nur erzielt werden kann, falls alle 5T+18 Reihen geräumt wurden, was nur bei einer "Ja"-Instanz geschieht.

Abb. 11: Modifiziertes Feld für das Maximieren der Anzahl an Tetrisen^[2:14], bearbeitet

Oberer Bereich unseres Spielfelds

Der Grund warum wir unser originales Spielfeld so definierten, dass die Höhe 5T+18 + 2s + O(1) beträgt, hängt mit der Einschränkung zusammen wie wir unsere spielende Person in Tetris die Spielsteine bewegen lassen. In herkömmlichen Versionen von Tetris, kann bspw. nur eine begrenzte Anzahl von Verschiebungen und Rotationen vollendet werden, bevor der Spielstein um eine Reihe sinkt. Die Reduktion von Breukelaar et al. erfordert lediglich, dass im Spiel nur eine Verschiebung gemacht werden muss, bevor unser Spielstein um eine Reihe fällt oder fixiert wird. Da ein Spielstein um höchstens 2s Spalten verschoben und 2-mal rotiert werden muss, besitzen wir 2s + O(1) zusätzliche Reihen für die Verschiebungen und Rotationen, da letzteres eine freie O(1)-Nachbarschaft benötigt^[2:15].

Referenzen