Lade Daten...
22.02.2012
Schrift:
-
+

Lösung des Vierfarbenrätsels

Drei Ecken dürft ihr bilden

Von
SPIEGEL ONLINE

Mit Computerhilfe haben zwei deutsche Forscher ein mit Sudoku verwandtes Rätsel geknackt: Sie verteilten vier Farben über eine quadratische Fläche bestehend aus 17 mal 17 Feldern. Dabei durfte kein Rechteck mit vier gleichfarbigen Eckpunkten entstehen.

Es gibt Probleme, die auch die schnellsten Computer der Welt überfordern. Vor allem, wenn die Anzahl der zu untersuchenden Varianten schier ins Unendliche steigt, sind selbst Supercomputer mit ihrem Latein am Ende. Ein solches Problem haben nun die beiden deutschen Informatiker Bernd Steinbach und Christian Posthoff gemeistert. Mathematiker bezeichnen es als Vierfarbengitter.

Die Aufgabe erscheint auf den ersten Blick nicht mal besonders schwierig: Ausgangspunkt ist ein quadratisches Spielfeld bestehend aus 17x17 Feldern. Jedes dieser 289 Felder wird mit einer von vier Farben eingefärbt. Dabei muss eine Bedingung erfüllt sein: Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe sein - siehe Fotostrecke.

Die Schwierigkeit der Aufgabe besteht in der riesig großen Zahl der möglichen Farbverteilungen: Es sind vier Farben und 289 Felder, was 4289 Möglichkeiten entspricht - eine aus 174 Ziffern bestehende Zahl.

All diese Färbungen systematisch zu probieren kommt aufgrund der riesig großen Zahl nicht in Frage. Zumal man dann in jedem einzelnen Fall alle möglichen Rechtecke daraufhin untersuchen müsste, ob vier Ecken gleichfarbig sind. Pro Färbung existieren genau 18.496 solche zu untersuchende Rechtecke. Die Zahl ergibt sich als Quadrat des sogenannten Binomialkoeffizienten 17 über 2 = 17x16/2 = 17x8 - eine elementare Funktion aus der Kombinatorik.

In den letzten Jahren haben sich viele Mathematiker und Informatiker mit dem Vierfarbengitter beschäftigt. So war bekannt, dass es für Quadrate bis zu einer Größe von 16 mal 16 auf jeden Fall Lösungen gibt und das ab einer Größe von 19 mal 19 keine Lösungen mehr existieren. Was aber ist mit den Gittern 17x17 und 18x18?

Um das Rätsel endlich zu lüften, lobte William Gasarch von der University of Maryland Ende 2009 in seinem Blog die Summe von 289 US-Dollar für eine Lösung aus. Der überschaubare Betrag dürfte kaum einen Mathematiker oder Informatiker motiviert haben. Doch die Auslobung eines Preisgeldes sorgte für große Aufmerksamkeit in Mathe- und Informatik-Blogs weltweit - und so wurde auch der Freiberger Informatiker Steinbach auf das Problem aufmerksam. "Das Geld war sekundär", sagt er im Gespräch mit SPIEGEL ONLINE. Für ihn und seinen Kollegen Christian Posthoff habe allein die "einzigartige Herausforderung" gezählt.

Die Fahndung nach dem Minimum

Es gibt verschiedene Möglichkeiten, mit Computerhilfe nach einer Lösung für das Vierfarbengitter zu suchen. Zum Beispiel kann man bei einer zufälligen Farbverteilung beginnen und versuchen, diese Schritt für Schritt zu verbessern. Zunächst zählt die Software die Zahl der in der Zufallsverteilung enthaltenen Rechtecke mit vier gleichfarbigen Ecken. Dann wird an einem dieser Rechtecke bei einem Eckpunkt die Färbung geändert. Dadurch verschwindet mindestens ein Rechteck mit vier gleichfarbigen Ecken. Aber Obacht: Es können durch den Farbwechsel auch neue Rechtecke hinzukommen.

Wenn sich die Zahl der Rechtecke durch die Farbänderung eines Eckpunkts nicht verringert hat, wird die Farbänderung verworfen und ein anderer Eckpunkt umgefärbt. Sinkt hingegen die Zahl der Rechtecke mit vier gleichfarbigen Ecken, behält man diese Änderung bei und widmet sich dem Eckpunkt eines noch verbliebenen Rechtecks. So wird die Zahl der Rechtecke immer kleiner. Die Methode führt zu einem Minimum - aber dies muss nicht das absolute Minimum sein.

Steinbach und Posthoff verfolgten bei ihrer Lösung eine andere Strategie. Sie suchten zunächst nach einer Lösung für eine Farbe, bei der nur ein Viertel der Felder eine Färbung bekommt. Dann erweiterten sie diese Lösung auf vier Farben. Statt mit 17x17 Feldern arbeiteten sie außerdem gleich mit 18x18 Feldern, denn hier ist die Summer der Felder (324) durch vier teilbar (324/4=81).

"Mir hat das richtig Spaß gemacht"

Wenn man eine Lösung sucht, in der jede der vier Farben gleich häufig vorkommt, dann taucht jede genau 81 Mal auf. Zunächst suchten die Informatiker also nach einer Verteilung von 81 Feldern einer Farbe, die die Bedingungen der Aufgabe erfüllt. "Das an sich ist schon ein schwieriges Problem", erklärt Steinbach. Man habe nach einer Verteilung für eine Farbe gesucht, die so beschaffen war, dass sie auf die anderen drei Farben übertragen werden konnte. Die Details ihres Lösungswegs wollen die Forscher im Mai auf dem International Symposium on Multiple-Valued Logic in Kanada vorstellen.

Statt sämtliche theoretisch denkbaren Varianten zu berücksichtigen, suchten die Forscher von Vornherein nach sehr speziellen Lösungen. Und sie wurden tatsächlich fündig. Der Computer, ein zwei Jahre alter PC mit I7-Prozessor und 12 Giga-Bytes RAM, brauchte etwa sieben Stunden für die Lösung.

Aus der gefundenen Lösung für 18x18 Felder lässt sich dann leicht auch eine für 17x17 konstruieren: Man lässt einfach eine Spalte und eine Zeile weg. Nun sind der Freiberger Professor und Posthoff um 289 US-Dollar reicher. "Mir hat das richtig Spaß gemacht", sagt Steinbach im Gespräch mit SPIEGEL ONLINE.

William Gasarch, der mit seinem Preisgeld den Anstoß gegeben hatte, freut sich über die endlich gefundene Lösung: "Ich bin hoch erfreut, die 289 Dollar auszahlen zu können", schreibt er in seinem Blog. Einige sehr gute Leute hätten sich an der Sache versucht - vergeblich. "Ich habe immer mehr Zweifel bekommen, ob es überhaupt eine Färbung für das 17x17-Gitter gibt."

Auf den ersten Blick erscheint das Problem des Vierfarbengitters sehr theoretisch. Es gehört zur Graphentheorie - und ist sogar mit dem populären Zahlenrätsel Sudoku verwandt. Ersetzt man die neun Zahlen von 1 bis 9 durch neun Farben, dann müssen beim Sudoku 9x9=81 Felder gefärbt werden, allerdings mit anderen Nebenbedingungen: Jede Farbe darf in jeder Zeile, jeder Spalte und in jedem der neun 3x3 Quadrate nur einmal auftauchen.

"Färbungsprobleme haben viele Anwendungen", erklärt Steinbach. Meist löse man damit typische Optimierungsprobleme wie zum Beispiel die Frequenzzuweisung in Funkzellen. Die Methoden, mit denen das Vierfarbengitter gelöst wurde, könnten womöglich auch bei anderen Problemen hilfreich sein, hoffen die Informatiker. In Berlin haben Mathematiker mithilfe der Graphentheorie bereits vielen U-Bahn-Fahrern die Wartezeiten verkürzt: Sie optimierten damit den Fahrplan der inzwischen zehn Linien.

Fotostrecke

Optimierter Fahrplan: Schneller warten

Soeben erschienen ist das neue Buch von Holger Dambeck "Je mehr Löcher, desto weniger Käse - Mathematik verblüffend einfach" (Kiepenheuer & Witsch, 256 Seiten, 8,99 Euro).

Forum

Diskutieren Sie über diesen Artikel
insgesamt 25 Beiträge
1. Fehler?
justus0jonas 22.02.2012
Meiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit [...]
Zitat von sysopMit Computerhilfe haben zwei deutsche Forscher ein mit Sudoku verwandtes Rätsel geknackt: Sie verteilten vier Farben über eine quadratische Fläche bestehend aus 17 mal 17 Feldern. Dabei durfte kein Rechteck mit vier gleichfarbigen Eckpunkten entstehen. Lösung des Vierfarbenrätsels: Drei Ecken dürft ihr bilden - SPIEGEL ONLINE - Nachrichten - Wissenschaft (http://www.spiegel.de/wissenschaft/mensch/0,1518,816497,00.html)
Meiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit der - OE - horizontalen Grundseite mit (17 über 2) Möglichkeiten ist bereits die Länge der vertikalen Seite festgelegt, da es sich um Quadrate handeln soll - die Zahl der zu untersuchenden Rechtecke müsste demnach kleiner sein.
2. ...
phboerker 22.02.2012
Das Problem ist unzureichend definiert: "Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe [...]
Das Problem ist unzureichend definiert: "Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe sein" Ein solches "beliebiges Rechteck" kann ich für die 18x18 Lösung leicht präsentieren: Matherätsel geknackt: Verrücktes Sudoku mit vier Farben - SPIEGEL ONLINE - Nachrichten - Wissenschaft (http://www.spiegel.de/fotostrecke/fotostrecke-78910-6.html) Man betrachte die gelb-orangen Farbpunkte an den Koordinaten (5, 12), (4, 13), (8,15) und (7,16). Wenn das kein Rechteck mit gleichfarbigen Eckpunkten ist, weiß ich auch nicht. Das Problem oder vielmehr seine Lösung ist also auf Rechtecke, die parallele Kanten zu dem Feld aufweisen, beschränkt.
3.
heikoprasse 22.02.2012
Ich verstehe Sie nicht ganz - gehen Sie jetzt von der Bildung von allgemeinen Rechtecken oder von Quadraten aus? Beides wird in ihrem Kommentar sogar im gleichen Satz angenommen. Jedenfalls sollen laut Artikel + Bebilderung [...]
Zitat von justus0jonasMeiner Meinung nach - zumindest auf den ersten Blick - sind im Beitrag einige quantitative Fehler enthalten, oder? So beträgt die Anzahl der zu untersuchenden Rechtecke nicht (17 über 2)^2, denn durch die freie Wählbarkeit der - OE - horizontalen Grundseite mit (17 über 2) Möglichkeiten ist bereits die Länge der vertikalen Seite festgelegt, da es sich um Quadrate handeln soll - die Zahl der zu untersuchenden Rechtecke müsste demnach kleiner sein.
Ich verstehe Sie nicht ganz - gehen Sie jetzt von der Bildung von allgemeinen Rechtecken oder von Quadraten aus? Beides wird in ihrem Kommentar sogar im gleichen Satz angenommen. Jedenfalls sollen laut Artikel + Bebilderung ausdrücklich allgemeine Rechtecke gebildet werden, und damit ist die vertikale Seite keineswegs durch die Wahl der horizontalen festgelegt. Quadratisch ist nur die Grundfläche (17*17), auf der die Rechtecke gewählt werden, das Quadrat findet sich nur in der Quadrierung des Binomialkeffizienten wieder.
4. Nicht-Mathematiker-Frage
horstma 22.02.2012
Ich bin zwar kein Mathematiker, hatte aber im Rahmen meines E-Technik-Studiums zumindest ein paar Semester Vorlesungen. Was ich mich frage: Warum ist es nicht möglich, die Bedingungen für die Lösung in ein irgendwie geartetes [...]
Ich bin zwar kein Mathematiker, hatte aber im Rahmen meines E-Technik-Studiums zumindest ein paar Semester Vorlesungen. Was ich mich frage: Warum ist es nicht möglich, die Bedingungen für die Lösung in ein irgendwie geartetes Gleichungssystem zu packen? Natürlich wäre dieses Gleichungssystem sehr groß. Vermutlich eine Gleichung für jedes Rechteck, das in den 17er oder 18er Würfel passt, und die ausdrückt, daß die 4 Eckpunkte keine gleichen Werte aufweisen. Die Lösung dieses Systems würde zwar auch vermutlich sehr umfangreich sein, aber es wäre ein systematischer Ansatz, der nicht auf probieren beruht. Vielleicht kann ein Mathematiker dazu etwas sagen.
5. Unzureichend definiert
swenlechte 22.02.2012
Im Original ist die Aufgabe diesbezueglich zureichend definiert.
Zitat von phboerkerDas Problem ist unzureichend definiert: "Bei einem beliebig ausgewählten Rechteck aus diesem 17x17-Quadrat, zum Beispiel einem der Größe vier mal fünf Felder, dürfen die vier Eckpunkte nicht sämtlich von derselben Farbe sein" Ein solches "beliebiges Rechteck" kann ich für die 18x18 Lösung leicht präsentieren: Matherätsel geknackt: Verrücktes Sudoku mit vier Farben - SPIEGEL ONLINE - Nachrichten - Wissenschaft (http://www.spiegel.de/fotostrecke/fotostrecke-78910-6.html) Man betrachte die gelb-orangen Farbpunkte an den Koordinaten (5, 12), (4, 13), (8,15) und (7,16). Wenn das kein Rechteck mit gleichfarbigen Eckpunkten ist, weiß ich auch nicht. Das Problem oder vielmehr seine Lösung ist also auf Rechtecke, die parallele Kanten zu dem Feld aufweisen, beschränkt.
Im Original ist die Aufgabe diesbezueglich zureichend definiert.

Empfehlen

MEHR AUF SPIEGEL ONLINE

MEHR IM INTERNET

Verwandte Themen

Buchtipp

Buchtipp

Fotostrecke

Fotostrecke

Video

Artikel

News verfolgen

Lassen Sie sich mit kostenlosen Diensten auf dem Laufenden halten:

alles aus der Rubrik Wissenschaft
Twitter RSS
alles zum Thema Numerator
RSS

© SPIEGEL ONLINE 2014 Alle Rechte vorbehalten