Survo Puzzle

Bei Survo-Puzzles handelt es sich um Zahlrätsel in einer Matrix (typischerweise in der Form 3×4, 3×5, 4×4 oder 4×5). Veröffentlicht werden diese Rätsel seit September 2006 regelmäßig in der zweitgrößten finnischen Zeitung Ilta-Sanomat und im Journal der Universität Helsinki (Scientific Journal of the University of Helsinki, Yliopisto-lehti), welches Leser in ganz Finnland hat.

Beschreibung

Das Survo Puzzle, oder Survo-Rätsel ist ein Rätsel, welches von Seppo Mustonen erforscht wird und im April 2006 von ihm erstmals vorgestellt wurde. Der Name des Rätsels leitet sich von Mustonen’s Survo-System ab, welches eine integrierte Umgebung für statistische Analysen und damit verbundene Anwendungen ist.

Bei einem Survo-Rätsel ist es die Aufgabe, die Zahlen 1, 2, …, mn so in eine m×n-Matrix einzutragen, dass jede von diesen Zahlen nur einmal verwendet wird und, dass die Zeilen- und Spaltensummen den Zahlen entsprechen, welche unterhalb und auf der rechten Seite der Matrix gegeben sind, entsprechen. Oft werden manche der Zahlen zu Beginn bereits in der Matrix eingetragen sein, um eine eindeutige Lösung zu garantieren und/oder die Lösung zu erleichtern.

Das Survo-Rätsel weist gewisse Parallelen zu Sudoku- and Kakuro-Rätseln auf. Jedoch sind die Zahlen zum Lösen des Rätsels nicht auf 1, 2, …, 9 beschränkt und die Matrixgröße ist typischerweise sehr klein. Das Lösen von Survo-Rätseln ähnelt außerdem dem von Magischen Quadraten.

Der Schwierigkeitsgrad der Lösung eines Survo-Rätseln variiert stark. Einfache Rätsel, welche vor allem für Schulkinder gedacht sind, dienen als Übungen für Addition und Subtraktion, während die anspruchsvolleren auch logisches Denken erfordern. Die schwersten Survo-Rätsel können nur mit Hilfe von Computern gelöst werden.

Bestimmte Eigenschaften des Survo-Systems, wie das editorial computing und das COMB operation making, wie z. B. das beschränkte Zerlegen von natürlichen Zahlen in Summanden, unterstützen das Lösen von Survo-Rätseln.

Ein Beispiel

Hier sehen Sie ein einfaches Survo-Rätsel mit 3 Reihen und 4 Spalten:

	A	B	C	D
1		6			30
2	8				18
3			3		30
	27	16	10	25

Von den 3 × 4 = 12 Zahlen in der Matrix (wofür die Zahlen 1–12 zu verwenden sind) sind die Zahlenwerte 3, 6 und 8 bereits vorplatziert. Die Aufgabe ist es nun, die verbleibenden Zahlen aus 1–12 an der richtigen Stelle zu platzieren, sodass die Summen korrekt sind.

Das Rätsel hat eine eindeutige Lösung, welche schrittweise wie folgt gefunden werden kann: Die fehlenden Zahlen sind: 1, 2, 4, 5, 7, 9, 10, 11, 12. In der Regel ist es am besten, in einer Zeile oder Spalte zu beginnen, in der die wenigsten Zahlen fehlen. In diesem Fall sind dies die Spalten A, B und C.

Die Spalte A ist nicht geeignet als Startspalte, da die Summe 19 der fehlenden Zahlen auf verschiedenen Wegen entsprechend den Regeln berechnet werden kann (zum Beispiel 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). In Spalte B ist die Summe der fehlenden Zahlen gleich 10, wobei diese nur durch eine verbleibende Möglichkeit 10 = 1 + 9 berechnet werden kann, da die anderen Alternativen 10 = 2 + 8 = 3 + 7 = 4 + 6 nicht mehr möglich sind, aufgrund der sich bereits in der Matrix befindlichen Zahlen. Die Zahl 9 kann nicht in Reihe 2 platziert werden, da sonst die Zeilensumme den Wert 18 übersteigen würde. Daher ist die einzig verbleibende Möglichkeit, mit der Lösung zu beginnen:

	A	B	C	D
1		6			30
2	8	1			18
3		9	3		30
	27	16	10	25

Jetzt gibt es für Spalte A nur noch die Alternative 27 − 8 = 19 = 7 + 12 = 12 + 7. Die Zahl 7 kann nicht in Reihe 1 platziert werden, da die Summe der noch fehlenden Zahlen in dieser Reihe 30 − 7 − 6 = 17 ist und 17 keine erlaubte Aufteilung mehr ermöglicht. Daher ergibt sich:

	A	B	C	D
1	12	6			30
2	8	1			18
3	7	9	3		30
	27	16	10	25

und daher auch automatisch für die letzte Reihe 30 − 7 − 9 − 3 = 11:

	A	B	C	D
1	12	6			30
2	8	1			18
3	7	9	3	11	30
	27	16	10	25

In der ersten Reihe ist die Summe der noch fehlenden Zahlen 30 − 12 − 6 = 12. Die einzig noch erlaubte Aufteilung ist 12 = 2 + 10, wobei nur die Zahl 2 in Spalte C platziert werden kann, da 10 in dieser Position zu hoch für die Spaltensumme wäre.

	A	B	C	D
1	12	6	2	10	30
2	8	1			18
3	7	9	3	11	30
	27	16	10	25

Die Lösung kann nun einfach vervollständigt werden durch:

	A	B	C	D
1	12	6	2	10	30
2	8	1	5	4	18
3	7	9	3	11	30
	27	16	10	25

Dieses Beispielrätsel war also durch einfaches Rechnen und Nachdenken eindeutig lösbar.

Eigenschaften von Survo-Rätseln

Die Regeln von Survo-Rätseln sind einfacher als die von Sudoku. Die Zahlenmatrix ist immer rechteckig oder quadratisch und meistens kleiner als in Sudoku oder Kakuro.

Die Lösungsstrategien sind unterschiedlich und hängen vom Schwierigkeitsgrad des Rätsels ab. In seiner einfachsten Form, wie im folgenden 2×3-Fall (Schwierigkeitsgrad 0):

		3	9
	6		12
9	7	5

sind Survo-Rätsel geeignete Additions- und Subtraktionsübungen.

Das offene 3×4-Survo-Rätsel (Schwierigkeitsgrad 150):

				24
				15
				39
21	10	18	29

bei dem zu Beginn keine der Zahlen bereits vorgegeben sind, ist schwerer zu lösen. Es hat auch nur eine Lösung.

Das Problem kann vereinfacht werden, wenn einige der Zahlen bereits eingetragen sind, beispielsweise:

7		5		24
	1		8	15
		11		39
21	10	18	29

was die Aufgabe fast zu leicht macht (Schwierigkeitsgrad 0).

Schätzen des Schwierigkeitsgrades

Das Messen des Schwierigkeitsgrades basiert auf der Anzahl der Mutationen, welche vom ersten Lösungsprogramm von Mustonen (im April 2006) benötigt wurden. Dieses Programm arbeitet mit einem teilweise randomisierten Algorithmus.

Das Programm startet damit, dass die fehlenden Zahlen zufällig in die Matrix eingetragen werden. Danach versucht das Programm, mit den berechneten Zeilen- und Spaltensummen so dicht wie möglich an die tatsächlichen heranzureichen, indem es Zahlen in der Matrix systematisch austauscht. Diese Versuche führen entweder zu einer korrekten Lösung, oder (wie in den meisten Fällen) zu keiner Lösung, wenn die Differenz zwischen den berechneten und tatsächlichen Summen nicht systematisch minimiert werden kann. Im letzteren Fall wird eine Mutation durchgeführt, indem zwei oder mehr Zahlen zufällig ausgetauscht werden. Die systematische Vorgehensweise plus Mutation wird so lange wiederholt, bis eine wahre Lösung gefunden wurde. In den meisten Fällen kann die durchschnittliche Anzahl an Mutationen als ungefähres Maß für den Schwierigkeitsgrad eines Survo-Rätsels angesehen werden. Dieses Maß (MD) wird berechnet aus der durchschnittlichen Anzahl an Mutationen, wenn das Rätsel 1000-mal gelöst wird, ausgehend von einer randomisierten Matrix. Die Verteilung der Anzahl an benötigten Mutationen nähert eine geometrische Verteilung an.

Die numerischen MD-Werte können in eine 5-Stern-Skala übertragen werden:

MD

0–30	*
31–150	**
151–600	***
601–1500	****
1500–	*****

Der MD-Wert als Maß für den Schwierigkeitsgrad ist jedoch etwas ungenau und kann sogar irreführend sein, wenn die Lösung durch clevere Überlegungen und kreatives Raten gefunden wird. Das Maß funktioniert jedoch gut, wenn die Person, die das Rätsel löst, auch beweisen soll, dass die Lösung eindeutig ist.

Offene Survo-Rätsel

Ein Survo-Rätsel wird offen genannt, wenn zu Beginn nur die Zeilen- und Spaltensummen gegeben sind. Zwei offene m×n-Rätsel sind essentiell verschieden, wenn eins nicht in das andere überführt werden kann durch einen gegenseitigen Austausch von Zeilen und Spalten oder durch ein Transponieren, wenn m = n. In diesen Rätseln sind die Zeilen- und Spaltensummen eindeutig. Die Anzahl der essentiell verschiedenen und eindeutig lösbaren m×n-Survo-Rätseln wird durch S(m, n) abgebildet.

Reijo Sund hat sich als Erster der Bestimmung der Anzahl offener Survo-Rätsel gewidmet. Er errechnete S(3, 3) = 38, indem er alle 9! = 362880 möglichen 3×3-Matrizen mit den standardisierten Kombinatorik- und Datenverarbeitungsmodulen des Survo-Systems untersuchte. Danach fand Mustonen S(3, 4) = 583, indem er von allen möglichen Aufteilungen der Randsummen ausging und das erste Lösungsprogramm anwendete. Petteri Kaski bestimmte S(4, 4) = 5327, indem er die Lösungsaufgabe in ein Problem der exakten Überdeckung umwandelte.

Im Sommer 2007 hat Mustonen ein neues Lösungsprogramm erschaffen, welches die vorherigen Ergebnisse bestätigt hat. Die folgenden S(m, n)-Werte wurden durch dieses neue Programm bestimmt:

m/n	2	3	4	5	6	7	8	9	10
2	1	18	62	278	1146	5706	28707	154587	843476
3	18	38	583	5337	55815	617658
4	62	583	5327	257773
5	278	5337	257773
6	1146	55815
7	5706	617658
8	28707
9	154587
10	843476

Schon das Berechnen von S(5, 5) erscheint nach heutigem Wissensstand als eine schwierige Aufgabe.

Die Tauschmethode

Die Tauschmethode für das Lösen von Survo-Rätseln wurde aus der Kombination der Idee des ursprünglichen Lösungsprogramms mit der Beobachtung, dass die Produkte der Randsummen in etwa die Position der korrekten Zahlen in der finalen Lösung anzeigen, geboren. Der Lösungsprozess startet durch das Ausfüllen der Originalmatrix mit den Zahlen 1, 2, …, mn entsprechend der Größe dieser Produkte und durch das Berechnen der Zeilen- und Spaltensumme entsprechend diese initialen Anordnung. In Abhängigkeit davon, wie diese Summen von den tatsächlichen Summen abweichen, wird die Lösung durch einen Austausch von jeweils zwei Zahlen. Wenn die Austauschmethode angewandt wird, ähnelt das Lösen des Survo-Rätsels dem von Schachproblemen. Durch diese Methode kann die Eindeutigkeit der Lösung nur schwer verifiziert werden.

Ein Beispiel: Ein sehr anspruchsvolles 4×4-Rätsel (MD = 2050):

				51
				36
				32
				17
51	42	26	17

wird durch 5-mal Tauschen gelöst. Die initiale Anordnung ist:

					Summe	OK	Fehler
	16	15	10	8	49	51	−2
	14	12	9	4	39	36	3
	13	11	6	3	33	32	1
	7	5	2	1	15	17	−2
Summe	50	43	27	16
OK	51	42	26	17
Fehler	−1	1	1	−1

und die Lösung wir gefunden durch das Tauschen von (7, 9) (10, 12) (10, 11) (15, 16) (1, 2). Im Survo-System sorgt ein sucro/SP_SWAP für die Verrechnung, welche bei der Tauschmethode benötigt wird.

Kurze Spiele

Das Lösen eines schweren Survo-Rätsels kann mehrere Stunden in Anspruch nehmen. Sie als kurze Spiele zu lösen bietet eine weitere Herausforderung. Die anspruchsvollste Art von kurzen Spielen ist im Internet als Java-Applet verfügbar.

In diesen kurzen Spielen werden 5×5-Rätsel durch das Auswählen (oder Raten) der Zahlen durch Maus-Klicks gelöst. Das falsche Platzieren einer Zahl löst eine melodische Tonfolge aus. Ihre Länge und die Tonrichtung zeigen die Qualität des Fehlers an. Der Punktestand steigt bei richtigen Entscheidungen und wird reduziert, durch falsche Positionierungen und durch die Zeit, welche für die Lösung benötigt wird.

Weblinks

• Survo puzzles
• Enumeration of Survo puzzles (PDF-Datei; 494 kB)
• Swapping method
• Quick game