Startseite
Sie sind hier: Home > Spiele > Tests & Previews >

Rätsel der 3D-Sudokus gelöst

...
t-online.de ist ein Angebot der Ströer Content Group

Zahlenforschung  

Rätsel der 3D-Sudokus gelöst

26.02.2009, 17:58 Uhr | Spiegel Online (Holger Dambeck / vb)

Sudoku, Kakuro & Friends (Bild: Cerasus)Sudoku, Kakuro & Friends (Bild: Cerasus)Es gibt Berechnungen, die sind so umfangreich, dass selbst die mächtigsten Computer der Welt kapitulieren. Jetzt haben Forscher einen neuen Algorithmus gefunden, der komplexe Zählprobleme radikal vereinfacht - und herausfindet, wie viele Lösungen ein dreidimensionales Sudoku besitzt.

Marc Timme wusste schon seit Jahren, dass der rasante Geschwindigkeitszuwachs bei Prozessoren ihm nie und nimmer helfen würde. Das Problem, welches den Physiker vom Göttinger Max-Planck-Institut für Dynamik und Selbstorganisation umtreibt, war mehrere Nummern zu groß für die Rechenpower der modernsten Computer. Letztlich will Timme einfach nur wissen, wie viele verschiedene Lösungen ein dreidimensionales Sudoku besitzt. Die Zahlenrätsel, mit denen sein Team arbeitet, sind verblüffend klein. Das 3D-Sudoku hat beispielsweise eine Größe von 4x4x4 - besteht also aus genau 64 Zellen. Die Regeln sind im Vergleich zu herkömmlichen, zweidimensionalen Sudokus sogar noch vereinfacht. Erlaubt sind beispielsweise nur die Zahlen 1, 2, 3 oder 4. Und nur in direkt benachbarten Zellen müssen jeweils unterschiedliche Zahlen stehen. Die strengere Sudoku-Vorschrift, dass in jeder ganzen Spalte und Zeile jede Zahl nur einmal auftreten darf, gilt hier nicht.

Foto-Show Sudokus lösen und Karten färben mit der Graphentheorie

Rechenzeit von Milliarden Jahren

Multiplayer Sudoku OnlinespielMultiplayer Sudoku (Bild: T-Online)Was zunächst wie eine simple und überschaubare Aufgabe erscheint, ist mit den dafür bislang üblichen Lösungstechniken nicht zu schaffen. "Der bisherige Algorithmus kopiert bei jedem Rechenschritt das gesamte Netz und ändert dabei jeweils nur einen Aspekt", sagt Timmes Kollege Frank van Bussel. Mit zunehmender Zellenzahl nehme die Rechenzeit exponentiell - und damit dramatisch - zu. Für ein quadratisches Gitter von der Größe eines Schachbretts (8x8) etwa beträgt sie nach van Bussels Aussage "viele Milliarden Jahre". Sudokus sind eine spezielle Anwendung aus der sogenannten Graphentheorie. Das Problem gleicht verblüffenderweise der Fragestellung, in wie vielen Varianten man die Länder einer Landkarte einfärben kann, so dass aneinander grenzende Länder stets verschiedenfarbig sind. Auch die Zuteilung von Frequenzen in Funkzellen, die sich teils überlappen, ist mathematisch gesehen das gleiche Problem.

Download Das fieseste Spiel der Welt
Download Das schwierigste Spiel der Welt

Sekunden statt Milliarden Jahre

Sudoku (Bild: T-Online)Sudoku (Bild: T-Online)In der Graphentheorie wandeln Mathematiker Sudokus, Landkarten und Funkzellen in ein Netz aus Linien und Knoten um. Dann reduzieren sich die Probleme auf eine Frage: Auf wie viele Weisen kann man die Knoten einfärben, wenn eine bestimmte Anzahl von Farben vorgegeben ist? Einzige Bedingung: Knoten, die durch eine Linie verbunden sind, dürfen nicht gleich gefärbt sein. Je nach Anwendung hat die Farbe eines Knotens verschiedene Bedeutungen. Im Fall der Landkarte ist mit Farbe tatsächlich eine Farbe gemeint, beim Sudoku entsprechen den Farben verschiedene Ziffern, bei den Funkzellen sind es verschiedene Frequenzen. Der neue Algorithmus, den die Wissenschaftler aus Göttingen entwickelt haben, ist deutlich schneller als das bisher genutzte Abzählverfahren. Die Rechnung für das Schachbrett-Gitter dauert damit beispielsweise nur sieben Sekunden - und nicht Milliarden Jahre.

Ergebnis der Zählung: 53.781.962.033.661.857.237.868

Sudoku-WM 2008 (Bild: Hubert Wagner)Sudoku-WM 2008 (Bild: Hubert Wagner)Der Trick der Forscher: Statt bei jedem Rechenschritt das gesamte Sudoku zu berücksichtigen, hangelt sich der Algorithmus von Knoten zu Knoten durch das Netz. Als sei das Computerprogramm kurzsichtig, betrachtet es stets nur den nächsten Knotenpunkt und nicht das gesamte Gitter. Dies reduziere den Rechenaufwand enorm, schreiben die Forscher im Fachblatt "New Journal of Physics". Erst wenn das Programm am letzten Knotenpunkt angekommen ist, kennt es das gesamte Netz. Und wie viele Lösungen besitzt nun das 3D-Sudoku der Größe 4x4x4? "Es geht um eine gigantische Zahl", sagt Timme im Gespräch mit "Spiegel Online". Sie liege in der Größenordnung 1022. "Diese Zahl können wir jetzt exakt ausrechnen." Sie lautet: 53.781.962.033.661.857.237.868.

Downloads Die besten Freeware-Spiele

Spielen nur am Rande

Timmes Team geht es bei dem Mammutzählprojekt jedoch nicht wirklich um Sudokus. Die Forscher wollen vielmehr ein Phänomen aus der Festkörperphysik untersuchen: den Antiferromagnetismus. "Das Grundmodell dafür stammt aus den fünfziger und sechziger Jahren. In drei Dimensionen konnte man dieses Problem jedoch bis heute nicht lösen." In Festkörpern besitzt jedes Atom einen inneren Drehimpuls, den sogenannten Spin, der verschiedene Werte annehmen kann. Bei Antiferromagneten tendieren die Spins benachbarter Atome im Gitter dazu, verschiedene Werte anzunehmen. Genau diese Eigenschaft unterscheidet sie von Ferromagneten, in denen sich benachbarte Spins eher gleich ausrichten und das Material magnetisch machen. Bei den von Timmes Team untersuchten Modellen sind je nach Material verschiedene Spinzustände möglich. Sie reichen von zwei, drei und vier bis zu sechs. Die Anzahl der möglichen Spinverteilungen in einem solchen System können die Forscher dank der neuen Methode nun berechnen, was Rückschlüsse auf die Eigenschaften der Modelle erlaubt.



Liebe Leser, bitte melden Sie sich an, um diesen Artikel kommentieren zu können. Mehr Informationen.

Kommentare

(0)
Leserbrief schreiben

Für Kritik oder Anregungen füllen Sie bitte die nachfolgenden Felder aus. Damit wir antworten können, geben Sie bitte Ihre Adresse an.

Name
E-Mail
Betreff
Nachricht

Wählen Sie aus dem Pull-Down-Menü Ihren gewünschten Ansprechpartner aus. Vielen Dank für Ihre Mitteilung.

Artikel versenden

Empfänger

Absender

Name
Name
E-Mail
E-Mail
Anzeige
Video des Tages
Brutale Methode 
Was dieser Arzt gleich macht ist einfach unglaublich

Diese Behandlung ist garantiert nichts für zartbesaitete Menschen. Video

Anzeige


Anzeige
shopping-portal