Kodierung von Puzzleteilen

How to translate

1. Motivation
2. Puzzleteile handlicher kodieren
3. Puzzleteile verschieben
4. Zwei Puzzleteile zusammenfügen
5. Ein kompletter Somawürfel
6. Epilog



1. Motivation

Um Puzzleteile schnell in ein (JavaScript-) Programm zur räumlichen Darstellung (in X3D) einzugeben, habe ich nach einer Kodierung gesucht, die kurz, wenig fehleranfällig und leicht korrigierbar ist. Für die im Folgenden beschriebe Kodierung benötigt man 2 bis maximal 9 Zeichen (plus eventuell 2 Kommata) statt 27 Zeichen (plus eventuell Leerzeichen und Zeilenumbrüche).

Der 3x3x3-Somawürfel mit seinen 7 Puzzleteilen V, L, T, Z, A, B und P wird in der Regel in 3 Schichten folgendermaßen dargestellt (hier der Würfel aus dem 2. Beispiel zur Somap, der bei gedrückter Maustaste gedreht und untersucht werden kann):

oben	B B T V B T V P T B Z Z V P T A P P Z Z L A A L A L L	=
mitte
unten

Diese Schreibweise ist für den kompletten Somawürfel sehr übersichtlich und intuitiv. Interessiere ich mich jedoch nur für ein einzelnes Puzzleteil, ist diese Schreibweise nicht sehr handlich, vor allem, wenn man das Puzzleteil in ein Programm eingeben will (im folgenden Beispiel das A-Teil):

· · · · · · · · · · · · · · · A · · · · · A A · A · ·

bzw.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0

=

2. Puzzleteile handlicher kodieren

Schaut man von oben auf das Puzzleteil, so hat man in der hinteren (bzw. ersten) Reihe 2 einzelne Würfel (1 und 1) und links davor (in der 2. Reihe) zwei Würfel übereinander (11):

1	1
11

Ersetzt man die Dualzahlen durch Dezimalziffern und schreibt die einzelnen Reihen durch Kommata getrennt nebeneinander, wobei die Dezimalzahlen nicht durch Leerzeichen getrennt werden müssen, da nur Ziffern zur Verwendung kommen, erhält man die kurze Kodierung dieses A-Teils:

1	1	= 11,3
3

Hier noch 2 weitere Beispiele(L-Teil):

=

01  01  11

= 01,01,11

= 100 111

= 47

Die Kodierung mit Dezimalziffern, um keine Leerzeichen zu verwenden, funktioniert nur, wenn die Puzzleteile nicht höher als 3 sind. In diesem Fall reichen die Ziffern 0 - 7. Bei Puzzleteilen der Höhe 4, die in 3x3x3-Würfeln allerdings keine Rolle spielen, reichen die Hexadezimalziffern 0 - 9 und A - F. Bei Puzzleteilen der Höhe 5 könnte man das Hexadezimalsystem noch um die Ziffern G - V erweitern. Für noch höhere Teile (die Breite und Tiefe spielt übrigens keine Rolle) ist der Phantasie keine Grenze gesetzt, oder man greift doch auf mehrstellige Dezimalzahlen zurück und verwendet Leerzeichen ...


3. Puzzleteile verschieben

Bisher lagen alle Puzzleteile unten, vorne und links. Um sie an die richtige Stelle im Puzzle zu schieben, könnte man zusätzlich Angaben für die x-, y- und z-Verschiebung machen. Man kann die Verschiebung aber auch direkt in die Kodierung integrieren:

3.1. Verschiebung nach rechts in die x-Richtung:

Dazu setzt man vor jede, durch Kommata getrennte Reihe, eine "0". So wird aus dem A-Teil 11,3 von oben 011,03. Weiter sollte man nicht schieben (z.B. 0011,003), da das Puzzleteil sonst rechts aus dem Somawürfel ragt.

3.2. Verschiebung nach oben in die y-Richtung:

Dazu werden alle Zahlen der Kodierung mit 2 multipliziert. So wird aus dem A-Teil 11,3 dann 22,6.

3.3. Verschiebung nach hinten in die (negative) z-Richtung:

Dazu setzt man hinter die Kodierung ein ",0". So wird aus dem A-Teil 11,3 dann 11,3,0.


4. Zwei Puzzleteile zusammenfügen

Bisher ging es nur darum, eine kurze, handliche Kodierung zu finden. Aber läßt sich aus dieser Kodierung noch mehr herauslesen, bzw. läßt sich z.B. das A-Teil 11,3 aus dem Beispiel oben mit dem V-Teil 3,2 zusammenfügen? Dazu werden die beiden Teile linksbündig addiert:

1	1	,	3	oder als Dualzahlen:	1	1	,	11
3		,	2		11		,	10
4	1	,	5		100	1	,	101

Falls beim Addieren der Dualzahlen irgendwo ein Übertrag notwendig ist bzw. irgendwo zwei Einsen übereinander stehen, passen die Teile nicht zusammen, was beim obigen Beispiel auch der Fall ist, weil dort das V-Teil zwar links und vorne liegt, aber nicht unten. Das Teil 3,2 muss also um einen Schritt nach oben geschoben werden und wird dann zu 6,4:

1 1 , 3      oder als Dualzahlen:      1 1 , 11 6 , 4 110 , 100 7 1 , 7 111 1 , 111

Doch auch ohne Dualzahlen hätte man überprüfen können, ob die beiden Puzzleteile sich überschneiden oder nicht:

Zwei Zahlen a und b (mit a > b > 0) ergeben als Dualzahlen keinen Übertrag, wenn der Binomialkoeffizient

$$\left(\begin{array}{c}a+b\\ b\end{array}\right)=\frac{(a+b)!}{a!·b!}=\begin{array}{c}b\\ \prod \\ i=1\end{array}\frac{a+b+1-i}{i}$$

eine ungerade Zahl ist. Falls a = b ist, überschneiden sich die Puzzleteile an der entsprechenden Stelle, falls a oder b = 0 ist, überschneiden sich die Puzzleteile an der entsprechenden Stelle nicht.

Überprüfen wir nun die beiden Stellen a = 3 und b = 1 sowie a = 3 und b = 2, an denen das A- und das V-Teil sich überschnitten:

$$\frac{(3+1)!}{3!·1!}=\frac{4}{1}=4$$ (gerade)

$$\frac{(3+2)!}{3!·2!}=\frac{5·4}{1·2}=10$$ (gerade)

Überprüfen wir jetzt die beiden Stellen a = 6 und b = 1 sowie a = 4 und b = 3, an denen das A- und das V-Teil sich zusammenfügen ließen:

$$\frac{(6+1)!}{6!·1!}=\frac{7}{1}=7$$ (ungerade)

$$\frac{(4+3)!}{4!·3!}=\frac{7·6·5}{1·2·3}=35$$ (ungerade)


5. Ein kompletter Somawürfel

Nun sollen alle 7 Puzzleteile des Somawürfels (s.o.) an ihre richtige Position geschoben werden:

A-Teil = 11,3 (liegt bereits unten, links und vorne)
V-Teil = 3,2 → 6,4 (nach oben verschoben)
L-Teil = 01,01,11 → 001,001,011 (nach rechts verschoben)
P-Teil = 1,31 → 01,031 (nach rechts verschoben) → 02,062 (nach oben verschoben)
T-Teil = 2,3,2 → 002,003,002 (2 mal nach rechts verschoben) → 004,006,004 (nach oben verschoben)
B-Teil = 32,02 → 32,02,0 (nach hinten verschoben) → 64,04,0 (nach oben verschoben)
Z-Teil = 132 → 132,0,0 (2 mal nach hinten verschoben)

Zum Schluss werden alle (verschobenen) Teile zusammengefügt, wobei keine der übereinander stehenden Ziffern der Puzzleteile als Dualzahl eine 1 an der gleichen Stelle haben:

	hinten		mitte		vorne
	l m r		l m r		l m r
A-Teil:			1 1	,	3
V-Teil:			6	,	4
L-Teil:	0 0 1	,	0 0 1	,	0 1 1
P-Teil:			0 2	,	0 6 2
T-Teil:	0 0 4	,	0 0 6	,	0 0 4
B-Teil:	6 4	,	0 4	,	0
Z-Teil:	1 3 2	,	0	,	0
Somawürfel:	7 7 7	,	7 7 7	,	7 7 7

Während die Kodierung der einzelnen Puzzleteile noch recht handlich war, ist die Kodierung des kompletten Würfels zugegebenermaßen eher unübersichtlich und wenig intuitiv. Der Vorteil ist jedoch, dass die einzelnen Puzzleteile jetzt deutlicher herausgehoben sind. Nun lassen sich einzelne Puzzleteile aus dem Somawürfel (wie im 2. Beispiel zur Somap veranschaulicht) leicht herausnehmen und neu anordnen, um zu einer neuen Zusammensetzung bzw. Lösung des Somapuzzles zu kommen, wobei die Summe der einzelnen Puzzleteile jeweils die Form der 3 Teile zusammen kodiert:

	hinten		mitte		vorne
A-Teil:			1 1	,	3
V-Teil:			6	,	4
P-Teil:			0 2	,	0 6 2
Summe:			7 3	,	7 6 2

wird zu:

	hinten		mitte		vorne
A-Teil:			0 3	,	0 2 2
V-Teil:			3	,	1
P-Teil:			4	,	6 4
Summe:			7 3	,	7 6 2

6. Epilog

Das folgende Labyrinth (das mit gedrückter Maustaste drehbar ist) wurde mit "nlt1v,g000g,n0Z5l,l000l,t1tll" kodiert (a = 10, A = 36, s. Seitenquelltext):



Manfred Arens
arens@muart.de




← Zurück zur 2. Somap-Seite
← Zurück zur Startseite