16-Punkte-Problem

Das 16-Punkte-Problem ist eine Aufgabenstellung aus dem Bereich des praktischen Problemlösens in der Denkpsychologie, eine Erweiterung des Neun-Punkte-Problems.

Aufgabe

4 mal 4 Punkte

Es soll auf ein Punkteraster aus 4 mal 4, also 16 Punkten ein Linienzug aus 6 Linien so gelegt werden, dass jeder Punkt mindestens einmal von einer Linie berührt wird.

Das Problem ist eine Erweiterung des Neun-Punkte-Problems, das selbst mit der Kenntnis, dass das Punkteraster verlassen werden muss, nicht leicht zu lösen ist.

Die Lösungen außerhalb der euklidischen Geometrie sind beim Neun-Punkte-Problem erörtert.

Geschichte

Das Neun-Punkte-Problem wurde schon 1914 in einem Buch von Sam Loyd beschrieben, und die Erweiterung auf größere Raster ist naheliegend.

Im Buch Denkspiele der Welt von 1985 ist die Erweiterung von Neun auf 16 Punkte dargestellt und eine Lösung angegeben.

Das 16-Punkte Problem wurde 2009 in Psychology Today beschrieben. 2013 wurde von Marco Ribà präsentiert, dass das Rätsel von jedem Punkt aus gelöst werden kann.

Die Aufgabe wurde im Mai 2019 als Rätsel der Woche in der Online-Ausgabe von Der Spiegel gestellt und dort in der Artikeldiskussion und nachfolgend im Forum Matheplanet gelöst.

Symmetrie

Zu einer Lösung können durch Drehung um 90°, 180°, 270° und Spiegelung und Umdrehen der Lösungsrichtung oder Kombinationen davon zusätzliche Lösungen erzeugt werden. Diese gelten hier nicht als eigenständige Lösungen und werden in der Tabelle daher nicht zusätzlich aufgeführt. Ebenso werden zusätzliche Lösungen, die durch das Verlängern von Anfangs- oder Endlinie erzeugt werden, nicht separat gezählt. Wegen der letzten Bedingung beginnen und enden alle hier aufgezählten Linienzüge an Punkten, die nur von einer Linie erreicht werden. Alle Lösungen des 4 mal 4 Problems beginnen bei einem der Punkte A1 (Lösungen 1–26), A2 (Lösungen 27–39) oder B3 (Lösungen 40–42), da alle anderen Rasterpunkte durch Drehung oder Spiegelung auf diese drei Punkte abgebildet werden können.

Notation, Reihenfolge

Benennung der Punkte

Zur Benennung der Punkte werden die Reihen von oben nach unten mit den Buchstaben A–D bezeichnet, die Spalten mit Zahlen 1–4 von links nach rechts. Der Punkt A1 ist der Eckpunkt links oben. Eine Lösung besteht aus einer Sequenz von mindestens 16 Punkten. Die Linien innerhalb des Linienzuges sind mit einem Komma getrennt. Ein Knickpunkt wird doppelt aufgeführt, als Endpunkt der ankommenden Linie und als Anfangspunkt der abgehenden. Im Bild ist eine entsprechende Notation für das Neun-Punkte-Problem dargestellt.

Alternative Notationen:

• Auch für die Reihen können Ziffern verwendet werden, so dass die Bezeichnung der von Punkten in der Ebene in der Analytischen Geometrie entspricht. Der Punkt A1 kann dabei als (0,0) oder (1,1) gewählt werden.
• Benennung der 16 Punkte mit Hexadezimalziffern 0...9,a...f
• Angabe von genau zwei Rasterpunkten, erster und letzter Punkt, für jede Linie. Jede Lösung ist damit durch 12 Punkte gegeben. Knickpunkte sind doppelt angegeben, als Endpunkt der vorangegangenen und Anfangspunkt der nächsten Linie. Diese Notation hat den Vorteil, dass alle Lösungen gleich lang sind.

Die Lösungen werden hier sortiert nach den Spalten und Reihen der berührten Punkte. Also zuerst die Lösungen, die beim Punkt A1 beginnen und da das mehrere sind, nachfolgend die, die beim Punkt A2 weitergehen usw.

Eine Lösung, die sich aus einer vorangegangenen Lösung durch eine Symmetrieoperation (siehe oben) ergibt, wird nicht aufgezählt.

Kategorien

Lösungskategorien

Um ähnliche Lösungen zu gruppieren, können die Linien zu Geraden verlängert werden. Lösungen mit dem gleichen Geradensatz können einer gemeinsamen Kategorie zugeordnet werden. Es ergeben sich nach dieser Festlegung 12 Kategorien, mit je 6 Linien. Sie sind in der Tabelle mit K1...K12 gekennzeichnet. Für die Nummerierung der Kategorien wird hier die Reihenfolge der Lösungen in der Diskussion des Spiegelartikels beibehalten.

Eine Gruppierung der Ergebnisse ist auch nach weiteren Kriterien möglich. Einige sind in der unten stehenden Tabelle genannt. Daneben wurde auch das weiteste Verlassen des Punkterasters betrachtet und ähnlich, welcher maximaler Wert für Nenner oder Zähler in der Darstellung der Liniensteigungen als ganzzahliger Bruch vorkommt.

Besondere Lösungen

• Die Lösungen 19 und 36, der Kategorie K4 sind sowohl schließbar, jeder Punkt wird nur einfach, ohne Abknicken am Punkt, berührt und sie haben zwei Spiegelsymmetrien entlang der waagrechten und senkrechten Mittelachsen und sind durch eine Drehung von 180° auf sich selbst abbildbar. Sie werden von vielen als besonderes elegant empfunden.
• Die Lösungen zur Kategorie K1 werden häufig als erste gefunden. Zu dieser Kategorie gehören auch die kürzesten Lösungen und die Lösung 14, die die kleinste Fläche außerhalb des Rasters einschließt.

Betrachtungen für andere Quadratgrößen

Ab 3 mal 3 Punkten ist die benötigte Linienzahl durch die Formel $2(n-1)$ gegeben, wenn $n$ die Anzahl der Punkte entlang einer Seite darstellt.

Dies ist eine Linie weniger, als es eine einfache Lösung „Kreisen nach innen“ oder das parallele Abstreichen aller Reihen und Verbinden dieser Linien benötigt.

Für das 3 mal 3 Problem gibt es unter den oben genannten Einschränkungen genau eine Lösung, die unten in der Tabelle dargestellt ist. Mit den hier gewählten Symmetriebedingungen gibt es für das 4 mal 4 Problem 42 Lösungen. Für noch größere Quadrate steigt die Zahl der Lösungen stark an.

Vollständige Lösungssätze können mit Computerhilfe berechnet werden. Ein Ansatz ist es, die Rasterpunkte zu verbinden und den Versuch beim Überschreiten der maximalen Linienzahl abzubrechen und beim Abbruch vom Ende des Versuchs andere Punkte zu wählen (Backtracking). Ein anderer Ansatz ist, die vorgegebene Zahl an Linien so zu platzieren, dass alle Punkte abgedeckt sind und die Linien zu einem Linienzug verbunden werden können.

Ein Beweis, dass für jedes quadratische Punkteraster keine Lösung mit weniger Linien geben wurde von Marco Ripá auf ViXra angegeben. Dass es mit $2(n-1)$ Linien möglich ist, ist durch die Konstruktionsregeln unten gezeigt.

Bei allen Lösungen berührt jede Linie mindestens zwei Punkte und mindestens eine Linie n Punkte, was die höchstmögliche Zahl ist. Es wird vermutet, dass dies auch für größere Raster gilt.

Allgemeine Lösung für n mal n

Allgemeine Lösung für n >= 3

Die 3 mal 3 Lösung hat ein waagrechtes Linienende an einer Ecke. Eine solche Lösung kann durch Hinzufügen von zwei Linien außen von einer n mal n auf eine (n+1) mal (n+1) Lösung erweitert werden. Im Bild ist die Erweiterung auf 4 mal 4 durch die dunkelblauen Punkte rechts und oben dargestellt (in der Tabelle die Nummer 14), die dann nach der gleichen Methode links und unten auf 5 mal 5 erweitert wird, mit den zusätzlichen Punkten in lila. Ab dieser 5 mal 5 Lösung kommen zu den orange markierten Punkten keine weiteren doppelten erreichten Punkte hinzu und das Raster wird für die Lösung nicht mehr verlassen, was eine Besonderheit der kleineren Lösungen war und im englischen namensgebend: thinking outside the box

Die abgebildete 5 mal 5 Lösung kann weiter durch Anfügen eines Linienzuges rechts und oben zu einer 6 mal 6 Lösung erweitert werden usw. Für große n befindet sich die abgebildete Lösung in der Mitte und wird umkreist.

Lösung für n mal n, ohne doppelte Punkte

Lösung ohne doppelte Punkte

Es gibt eine Konstruktionsvorschrift, die für viele große $n$ eine Lösung ohne Mehrfachpunkte ergibt. Dazu werden zuerst zwei separate Linienzüge erstellt und dann verbunden. (Zur Benennung: N ist der zu n gehörende Buchstabe also z. B. für n=26 ist für N Z einzusetzen):

• Erster Linienzug:
  • Bei Eckpunkt rechts unten Nn (im Bild F6, blau) nach oben startend bis zum Eckpunkt rechts oben: An (im Bild A6)
  • links abbiegend die Diagonale nach links unten bis zum Eckpunkt links unten: N1 (im Bild F1)
  • weiter links abbiegend, jeweils bevor ein besetzter Punkt erreicht wird, bis nur noch ein Punkt (im Bild orange, E4) frei ist

• Um 180 gedreht, das gleiche für das verbleibende Dreieck links oben, als zweiter Linienzug:
  • Startend bei A1 (im Bild grün) nach unten bis zum Punkt (N-1)1 (im Bild E1)
  • links abbiegend die erste obere Nebendiagonale nach rechts oben bis A(n-1) (im Bild A5)
  • weiter links abbiegend, jeweils bevor ein besetzter Punkt erreicht wird, bis nur noch ein Punkt (im Bild orange, B3) frei ist

• Verbindung der beiden Linienzüge
  • Die beiden übrigen freien Punkte verbinden und diese Linie bis zu den Verlängerungen der senkrechten Startstrecken rechts Nn An (im Bild F6 A6) und links A1 (N-1)1 (im Bild A1 E1) fortsetzen.

Die Verbindungslinie hat dabei, wenn n nicht mit Rest 3 durch 6 teilbar ist, keine Kreuzung mit anderen, bereits erreichen Gitterpunkten. Die nach dieser Vorschrift konstruierte Lösung für das 4 mal 4 Raster ist in der Tabelle als Nummer 28 enthalten. Für das 3 mal 3 Raster ergibt die Vorschrift keine Lösung: die verbleibenden Punkte sind senkrecht übereinander, so dass die Verbindungslinie nicht mit den beiden Startlinien verbunden werden kann.

Erläuterungen zu den Tabellen

• Die Länge gibt die Länge des Linienzuges an in der Einheit des Rasterabstands. Die Verbindung A1 A2 hat demnach die Länge 1, die diagonale Verbindung A1 B2 die Länge 1.41.
• Die Drehsymmetrie gibt an, mit wie vielen Drehungen die Lösung auf sich selbst abgebildet werden kann. Der Maximalwert wäre der Wert für das Raster, also 4 bzw. Symmetrie bei Drehung um 90°. Eine Symmetrie wird auch dann gezählt, wenn sie nach Verlängerung der Endlinien zustande kommt.
• Die Spiegelsymmetrie gibt an ob die Lösung durch Spiegelung an der Diagonalen, den senkrechten oder waagrechten Mittelachsen auf sich selbst abgebildet werden kann.
• Bei Mehrfachpunkte wird angegeben, wie viele Punkte von mehr als einer Linie berührt werden.
• Eine Lösung wird als schließbar markiert, wenn sich die Verlängerung von Anfangs- und Endlinie schneiden. Solche Lösungen haben mehrere ähnliche Lösungen der gleichen Kategorie in der Tabelle, weil der Linienzug an jeder Ecke, die aus dem Rasterquadrat herausragt, aufgetrennt werden kann.
• Aus der Spalte Linksabbieger kann abgelesen werden, wie häufig der Linienzug beim Durchfahren die Abbiegerichtung wechselt. Von der Diagonalen A1 B2 C3 kommend wäre die Fortsetzung C2 C1 links abgebogen, die Fortsetzung B3 A3 rechts. Jeder Linienzug hat 5 Richtungswechsel. Eine Spiegelung oder Richtungsumkehr wandelt jedes Linksabbiegen in ein Rechtsabbiegen und umgekehrt.
• Als Knickpunkt wird gezählt, wenn eine Linie einen Punkt nicht gerade durchläuft, sondern am Punkt die Richtung ändert. In der Sequenz aus der 3 mal 3 Lösung: A1 B2 C3, C3 B3 A3 ist C3 ein Knickpunkt. In der Sequenz A2 B1, C1 C2 werden die Punkte gerade durchfahren, der Knick liegt nicht auf dem Punkteraster, sondern bei C0 also links des Rasters.

Tabelle aller Lösungen des 3 x 3 Problems

Num­mer	Bild	Punktsequenz	Länge	Dreh­sym­metrie	Spiegel­sym­metrie	Mehrfach­punkte	schließ­bar	Links­ab­bieger	Knick­punkte
1		A1 B2 C3, C3 B3 A3, A2 B1, C1 C2	12,07	0	1	0	nein	3	1

Tabelle aller Lösungen des 4 x 4 Problems

Num­mer	Bild	Punkt­sequenz	Kate­gorie	Länge	Dreh­sym­metrie	Spiegel­sym­metrie	Mehr­fach­punkte	schließ­bar	Links­ab­bieger	Knick­punkte
1		A1 A2 A3 A4, B3 C1, D1 D2 D3 D4, C4 B2, B1 C2, C3 B4	K8	30,07	0	1	0	nein	4	0
2		A1 A2 A3 A4, A4 B3 C2 D1, D1 C1 B1, B2 C4, D4 D3 D2, D2 C3 B4	K2	22,16	0	0	0	nein	0	3
3		A1 A2 A3 A4, A4 B3 C2 D1, D2 C4, B4 B3 B2 B1, C1 D3, D4 C3	K11	31,90	0	1	1	ja	4	1
4		A1 A2 A3 A4, A4 B3 C2 D1, D1 D2 D3 D4, C4 B2, B1 C1 D1, D2 C3 B4	K2	25,58	0	0	2	nein	4	2
5		A1 A2 A3 A4, B4 C1, D1 D2 D3 D4, C4 B2, B1 C2 D3, D3 C3 B3	K10	36,44	0	0	1	nein	4	1
6		A1 A2 A3 A4, B4 C3, C2 B1, B2 C4, D4 D3 D2 D1, C1 B3	K8	29,25	0	1	0	nein	0	0
7		A1 A2 A3 A4, B4 C3 D2, D2 C2 B2 A2, A2 B3 C4, D4 D3 D2 D1, D1 C1 B1	K1	21,49	0	1	2	ja	0	3
8		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B1 B2 B3 B4, B4 C4 D4, D3 C2	K1	21,49	0	1	1	ja	0	2
9		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B2 C4, D4 D3 D2 D1, D1 C2 B3	K2	26,58	0	0	2	nein	0	1
10		A1 A2 A3 A4, B4 C3 D2, D1 C1 B1, B1 C2 D3, D4 C4 B4, B4 B3 B2	K1	21,90	0	0	1	nein	2	2
11		A1 A2 A3 A4, B4 C3 D2, D2 D3 D4, C4 B2, B1 C1 D1, D1 C2 B3	K2	23,16	0	0	0	nein	4	2
12		A1 A2 A3 A4, A4 B4 C4 D4, D3 C2 B1, B1 B2 B3 B4, B4 C3 D2, D1 C1	K1	20,49	0	1	1	ja	0	3
13		A1 A2 A3 A4, A4 B4 C4 D4, D3 C2 B1, B1 C1 D1, D2 C3 B4, B4 B3 B2	K1	20,49	0	0	1	nein	3	3
14		A1 A2 A3 A4, A4 B4 C4 D4, D4 D3 D2 D1, C1 B2 A3, A3 B3 C3 D3, D3 C2 B1	K1	20,07	0	1	2	ja	0	4
15		A1 A2 A3 A4, C4 D2, D1 C2, C3 D4, D3 C1, B1 B2 B3 B4	K11	34,72	0	0	0	nein	0	0
16		A1 A2 A3, A3 B3 C3 D3, D3 D2 D1, C1 B2 A3, A4 B4 C4 D4, D3 C2 B1	K1	22,90	0	1	2	ja	0	2
17		A1 B2 C3 D4, C4 A3, A2 B1, C1 D2, D3 B4, A4 B3 C2 D1	K12	27,88	0	1	0	nein	5	0
18		A1 B2 C3 D4, C4 A3, A2 B2 C2 D2, D3 B4, A4 B3 C2 D1, D1 C1 B1	K11	33,73	0	1	2	ja	4	1
19		A1 B2 C3 D4, C4 A3, A2 C1, D1 C2 B3 A4, B4 D3, D2 B1	K4	32,85	2	2	0	ja	5	0
20		A1 B2 C3 D4, D4 C4 B4 A4, A2 C1, D1 C2 B3 A4, A3 B1, D1 D2 D3	K5	42,20	0	1	2	nein	5	1
21		A1 B2 C3 D4, D4 D3 D2 D1, D1 C2 B3 A4, A3 B1, C1 C2 C3 C4, B4 A2	K11	31,08	0	1	2	ja	2	2
22		A1 B3, C4 C3 C2 C1, B1 A2, A3 B4, D4 D3 D2 D1, B2 A4	K9	32,67	0	0	0	nein	0	0
23		A1 B3, C4 C3 C2 C1, B1 A2, A4 B4 C4 D4, D4 D3 D2 D1, C1 B2 A3	K3	28,37	0	0	2	nein	0	1
24		A1 B3, C4 C3 C2 C1, C1 B2 A3, A4 B4 C4 D4, D4 D3 D2 D1, B1 A2	K3	25,96	0	0	1	nein	0	2
25		A1 B3, D4 D3 D2 D1, B1 A2, A4 B4 C4, C4 C3 C2 C1, C1 B2 A3	K3	31,61	0	0	0	nein	0	2
26		A1 B3, D4 D3 D2 D1, C1 B2 A3, A4 B4 C4, C4 C3 C2 C1, B1 A2	K3	29,19	0	0	1	nein	0	1
27		A2 A1, B1 C2 D3, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3, D3 C3 B3	K1	23,31	0	1	1	ja	5	1
28		A2 A3 A4, A4 B3 C2 D1, D1 C1 B1 A1, B2 D3, D4 C4 B4, B4 C3 D2	K2	23,78	0	0	0	nein	2	3
29		A2 A3 A4, B4 C3 D2, D1 C1 B1 A1, B2 D3, D4 C4 B4 A4, A4 B3 C2	K2	28,19	0	0	2	nein	2	1
30		A2 A3 A4, B4 C3 D2, D1 C1 B1 A1, B3 D4, D3 C2 B1, B2 C4	K6	36,14	0	0	1	nein	0	0
31		A2 B2 C2 D2, D3 B4, A4 C3 B2 D1, D1 C1 B1 A1, A3 C4, D4 C3	K11	36,14	0	0	1	nein	2	1
32		A2 B2 C2 D2, D3 B4, A4 C3 B2 D1, D1 C1 B1 A1, A1 B2 C3 D4, C4 A3	K11	30,49	0	1	2	ja	3	2
33		A2 B3, C3 D2, D1 C1 B1 A1, B2 D3, D4 C4 B4 A4, A3 C2	K8	28,84	0	1	0	nein	3	0
34		A2 B3 C4, D4 D3 D2 D1, C1 B2 A3, A4 D3, D2 B1, A1 B4	K7	30,75	0	0	0	nein	0	0
35		A2 B3 C4, D4 D3 D2 D1, D1 C1 B1 A1, A1 B2 C3 D4, D4 C4 B4 A1, A3 C2	K2	24,96	0	0	2	nein	2	3
36		A2 C1, D1 C2 B3 A4, B4 D3, D2 B1, A1 B2 C3 D4, C4 A3	K4	34,27	2	2	0	ja	5	0
37		A2 C1, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3, D3 C2 B1, A1 B3	K9	28,26	0	0	0	nein	4	1
38		A2 C3, D3 D2 D1, C1 B2 A3, A1 B4 C4 D4, D3 C2 B1, A1 B3	K9	29,05	0	0	1	nein	0	0
39		A2 C3, D4 C4 B4 A4, A3 B2 C1, D1 D2 D3 D4, B3 A1, B1 C2	K9	35,32	0	0	1	nein	5	0
40		B2 C1, D1 D2 D3 D4, D4 C4 B4 A4, A4 A3 A2 A1, B1 C2 D3, D3 C3 B3	K1	20,07	0	1	1	ja	0	3
41		B2 C2 D2, D1 C3 B4, A4 A3 A2 A1, B2 C4, D4 D3 D2 D1, C1 B3	K10	35,20	0	0	1	nein	3	1
42		B2 C3 D4, D4 C4 B4 A4, A4 A3 A2 A1, B1 C2 D3, D3 D2 D1, C1 B3	K2	22,54	0	0	0	nein	3	3