Das Kulträtsel enträtselt!
Sudoku Lösung
Über Sudoku
- Ein anspruchsvolles Sudoku Feld (SuDoKu-Code: SLa-bf-5Cg5G-LoVQ4-xPWQb-oYp-6M-qNzGM-4rew)
Sudoku ist ein mathematisches Rätsel und gehört in die Unterkategorie der magischen Quadrate. 1979 wurde dieses Rätsel in Amerika entwickelt und kam fünf Jahre später nach Japan. Ein dort ansässiger Verlag veröffentlichte diese Rätsel unter der Bezeichnung "Suji wa dokushin ni kagiru" ("jede Zahl muss einzeln stehen"). Der doch eher lange Name wurde dann mit der Zeit zu Sudoku abgekürzt.
Zwei weitere Jahre darauf wurde das Rätsel um eine Variation erweitert und löste damit den japanischen Sudoku-Boom aus: Die vorgegebenen Zahlen auf dem Spielfeld wurden symmetrisch angeordnet wodurch das Quadrat dann noch "magischer" wurde.
Nach Europa kam das Rätsel durch die Arbeit des Programmierers Wayne Gould, der ein entsprechendes Programm entwickelte, das diese Rätsel zu produzieren vermochte. In verschiedenen Tageszeitungen, z.B. der englischen "The Times" wurden diese Rätsel nun regelmäßig veröffentlicht. In Deutschland haben "die Zeit" und das "Handelsblatt" nachgezogen. Die Aufgaben sind auch auf den Internetseiten der Verlage verfügbar.
Die Aufgabenstellung
Das Spielfeld ist ein Quadrat mit einer Kantenlänge von 9 Feldern. Damit hat die gesamte Matrix 81 Felder, die mit den Ziffern 1 bis 9 zu besetzen sind. Üblicherweise wird das Spielfeld zudem noch in 9 Neunerblöcke (3x3 Felder) durch dickere Linien unterteilt um die Übersichtlichkeit bezogen auf die Spielregeln zu erleichtern.
Die Regeln lauten nämlich, dass in jeder Zeile, in jeder Spalte und in jedem der 3x3 Felder jede Ziffer nur (und damit exakt) ein mal vertreten ist.
Der Schwierigkeitsgrad wird durch die Zahl der vorgegebenen Ziffern, aber auch durch deren Anordnung bestimmt.
Die trotz dieser Einschränkungen gegebenen Möglichkeiten für ein korrektes Sudoku Feld beträgt dabei 6.670.903.752.021.072.936.960. Diese Anzahl sollte ausreichen um jede nur erdenkliche Stunde der Langeweile zu füllen...
Ein gutes Sudoku Rätsel ist trotz der geringen Zahl an vorgegebenen Werte immer eindeutig lösbar. Die komplexeren Varianten erfordern unter Umständen lästige Backtracking Schritte, doch oftmals nur in geringer Anzahl.
Abgesehen von den oben Beschriebenen Vorgaben existieren noch weitere Abwandlungen zum Sudoku Spiel, wobei z.B. auch die Diagonalen jede Ziffer nur ein mal aufweisen dürfen, etc. Die Lösung dieser Sudokus lassen sich durch eine geringe Abwandlung des hier beschriebenen Verfahrens ebenfalls leicht, ja sogar durch die zusätzlichen Einschränkungen noch leichter lösen.
Die Lösung
Die Lösung der Sudokus basiert auf einem Ausschlußverfahren. Hierzu geht man den umgekehrten Weg des üblichen Rätselns. Es werden nicht die potenziell möglichen Lösungen einzelner Felder betrachtet, sondern Zug um Zug die nicht mögliche Lösung gestrichen, bis am Ende á la Sherlock Holmes nur noch die einzig mögliche Lösung übrig bleibt.
Die im folgenden beschriebenen Schritte sind immer wieder durchzuführen, bis alle 81 Felder mit Ziffern gefüllt sind. Nach der Vorbereitung mag es ein wenig länger dauern, dafür geht es zum Ende hin immer schneller. Die Markierung der einzelnen Felder muss sehr sorgfältig erfolgen, da eine fehlerhafte Markierung zu einem Stocken des Lösungsprozesses oder gar zu einer falschen Lösung führt. In dem Fall bleibt nur noch der Griff zum Radiergummi und dieser ist an und für sich nicht Bestandteil der hier gebotenen Lösung. Ein Bleistift und gegebenenfalls ein zusätzliches Blatt für das Backtracking sind vollkommen ausreichend.
Die Markierung
- Markierungen innerhalb der Felder
Glücklicherweise wird je Feld nur eine Ziffer aus dem Bereich 1 bis 9 zugelassen. Somit kann eine sehr simple Markierung der nicht zugelassenen Ziffern erfolgen. Die von mir präferierte Methode sind kleine Striche am Rand des jeweiligen Feldes, bzw. ein Punkt in der Mitte. Ein Strich in der linken oberen Ecke des Feldes bedeutet dabei, dass die Ziffer 1 nicht mehr möglich ist. Ein Strich in der Mitte oben am Rand hat die gleiche Bedeutung für die Zahl 2, in der rechten oberen Ecke für die 3. Links in der Mitte wird die 4 markiert und der Punkt in der Mitte des Feldes deutet an, dass die 5 nicht mehr in Lösungsraum ist, etc. Das Bild zur linken macht dies etwas deutlicher.
Felder in denen bereits eine Ziffer steht, bzw. eine Lösung gefunden wurde brauchen nicht weiter markiert zu werden.
Ziffern ausschließen
- Markierungen nach Auswertung der ersten bekannten Ziffer
Jede bekannte Ziffer in einem Feld schließt gleichzeitig bis zu 20 weitere Ziffern in anderen Feldern aus. Dieses Wissen ist bei 81 Feldern nur schwer im Kopf zu behalten, daher wird dieses Wissen durch die oben erwähnten Markierungen auf dem Spielfeld hinterlegt. Zu Beginn des Rätsels sind die nachfolgenden Schritte je gegebener Ziffer durchzuführen, im Verlauf des Rätsels müssen diese Schritte für jede gefundene Ziffer wieder durchgeführt werden.
Starten Sie mit der ersten (am weitesten links stehende) bekannten Ziffer in der obersten Zeile und arbeiten Sie sich nach rechts und anschließend zeilenweise (wie beim Lesen) nach unten rechts durch. Im gegebenen Beispiel wird mit der 2 in der ersten Zeile begonnen, anschließend die 1 rechts daneben, dann die 5 bis abschließend die 8 in der letzten Zeile abgearbeitet wurde.
Die Existenz der Ziffer 2 in dem Feld birgt das Wissen darüber, dass in der gleichen Zeile und gleichen Spalte jeweils keine weitere 2 erscheinen darf. Daher wird in jedem freien Feld der gleichen Zeile und Spalte die Markierung für die 2, also ein kleiner Strich oben in der Mitte angebracht.
Ferner weiß man, dass im gleichen Teilfeld, also die 9 Felder der 3x3 Matrix in der die 2 steht (oben Mitte) ebenfalls keine weitere 2 enthalten sein darf. Die leeren Felder dieses Quadrats werden ebenso gemarkert.
Die Grafik auf der rechten Seite zeigt die Markierung die sich aus dem Wissen durch die 2 in der oberen Zeile ergeben.
- Rätsel Feld nach Markierung aller gegebenen Werte
Nachdem diese Markierungen für alle bekannten Feldbelegungen durchgeführt worden ist, sieht im aktuellen Beispiel das Sudoku Feld wie in der linken Grafik dargestellt aus.
Mit der Zeit füllen sich die einzelnen Felder immer weiter, bis in jedem Feld eine kleine "Uhr" sichtbar wird, bei der immer mindestens ein Element fehlt. In dem Moment, wo nur noch ein Element fehlt, ist die Lösung für dieses Feld bekannt.
Triviale Lösungen
- erste Lösung gefunden
Prüfen Sie nun die markierten Felder, ob hier nun Felder sind, die acht Markierungen haben, also nur eine einzige Ziffer nicht ausschließen. Im hier gezeigten Beispiel ist dies an mehreren Stellen der Fall, z.B. im siebten Feld (von oben gerechnet) der ersten Spalte. Tragen Sie in diese Felder die einzig gültige Lösung ein und führen Sie den zuvor bereits beschriebenen Schritt (Ziffern ausschließen) für die neu gewonnenen Lösungen durch um weitere Möglichkeiten in anderen Feldern zu eliminieren.
Bei leichten Sudoku Rätseln lässt sich auf diese Weise bereits das ganze Geheimnis lüften. Das hier gezeigte Beispiel ist bereits erheblich anspruchsvoller und erfordert noch weitere kombinatorischer Kniffe, die im folgenden Beschrieben werden. Die Grafik zur Rechten zeigt den Zwischenstand nach Eintrag der Lösung "8" in der ersten Spalte sowie die daraus resultiernden Ausschlüsse in anderen Feldern.
Lösungen aus Kombination
- Sudoku Feld nach der ersten Lösungssuche in Spalten, Zeilen und Teilfeldern
Sind durch den oben beschriebenen Schritt keine weiteren trivialen Lösungen zu finden, so setzt die folgende Technik ein. Hierbei überprüft man Felder im Zusammenhang mit ihren Zeilen, Spalten, bzw. 3x3 Quadraten. Da in jeder dieser Mengen jede Ziffer nur ein mal vorkommen darf kann man im Umkehrschluss daraus folgern, dass in dem Fall, in dem nur ein ein einziges Feld einer Gruppe eine bestimmte Ziffer zulässt, diese dann auch exakt dort als Lösung anzunehmen ist.
Im Beispiel finden wir eine solche Stelle im rechten, oberen 3x3 Quadrat. Lediglich das Feld in der Mitte der oberen Zeile dieses Quadrats lässt die benötigte Ziffer 3 zu.
Das Feld daneben ist ebenso exklusiv bestimmt bezogen auf die Ziffer 8.
Diese Analyse und Lösungssuche kann/muss für alle Teilquadrate, Zeilen und Spalten durchgeführt werden. Die 3 in der letzten Zeile und die 4 in der rechten Spalte findet man im Beispiel nur durch Betrachtung der jeweiligen Spalten.
Die Durchführung der Markierungen entsprechend der oben Beschriebenen Verfahrensweise (Ziffern ausschließen) ist auch hier nach jeder gefundenen Ziffer erforderlich. Ebenso kann jeweils im Anschluß nach trivialen Lösungen gesucht werden, bevor mit diesem Schritt neuerlich begonnen wird.
Das Spielfeld zur Linken zeigt den Zustand nach der ersten Durchführung dieses Schritts. Bereits nun ist erkennbar, dass sich weitere Felder mit eindeutigen Lösungen herausstellen, die bei den nun folgenden weiteren Durchgängen der bisherigen Schritten eingetragen werden.
- Zwischenstand nach einigen Iterationen
Das Bild zur rechten zeigt einen weiteren Zwischenstand nach einigen der obigen Schritten. Das Quadrat in der oberen rechten Ecke ist bereits vollständig gelöst, das Quadrat in der unteren rechten Ecke steht auch kurz vor der vollständigen Lösung.
Lücken füllen
- Das letzte Element einer Spalte/Zeile, bzw. eines Telfeldes
Bei diesem Fortschritt können auch weitere, einfachere Techniken zum Tragen kommen. So kann z.B. das letzte leere Feld in der rechten Spalte (viertes Feld von oben) bestimmt werden, indem hier die fehlende Ziffer aus der Menge 1-9 (hier: 2) eingetragen wird. Dies läßt sich selbstverständlich auch auf das letzte offene Feld einer Zeile oder eines Teilquadrats (siehe 3x3 Quadrat in der unteren, rechten Ecke) anwenden.
- weiterer Zwischenstand
Im als schwierig gehandelten Beispiel löst sich das Rätsel nun nahezu von selber auf. Ein Backtracking wird hier nicht erforderlich werden.
Die Lösung
Des Rätsels Lösung.
Backtracking
Nicht alle Sudoku Rätsel lassen sich auf diese recht stringent lineare Art und Weise lösen. Vereinzelt erzielt man nach mehrmaliger Ausführung der oben beschriebenen Schritte einen stabilen Zustand mit weiterhin offenen Feldern. In diesem Fall - nur bei Rätseln der sehr schweren Kategorie der Fall - muss mittels Backtracking, bzw. Trial-and-error gearbeitet werden.
Hierzu wählt man sich ein Feld mit möglichst wenig Optionen, also zulässigen Ziffern aus und wählt eine dieser Ziffern aus, setzt diese Zahl ein und probiert so, ob sich das Rätsel nun durch Anwendung der bisherigen Schritte lösen lässt, oder nicht. Dabei notiert man sich alle von nun an getätigten Schritte, bzw. arbeitet auf einer Kopie des Spielfeldes. Im Fehlerfalle müssen nämlich alle Schritte peinlich genau wieder rückgängig gemacht werden um nun mit der nächsten möglichen Ziffer zu experimetieren bis die Lösung gefunden wurde.
Automatische Lösung (SuDoKu Solver)
Für all diejenigen, denen dieses Verfahren zu kompliziert ist oder die eine Lösung nicht finden habe ich eine 
automatische Sudoku Lösung implementiert, die genau die oben beschriebenen Schritte durchführt. Tragen Sie in der Matrix einfach die Ausgangswerte ein und lassen Sie per Knopfdruck die Lösung bestimmen.
Das Backtracking Verfahren ist derzeit noch nicht implementiert, hier hilft nur selber an der ein oder anderen Stelle einen Wert testweise eingeben und erneut lösen lassen.
Mittlerweile ist der Solver in der Version 1.2 online. Hierbei wurde ein Bug beseitigt und zwei wesentliche neue Features implementiert: Der SuDoKu-Code und die Spielerzeugung (Create).
Der SuDoKu-Code ist eine eindeutige Beschreibung mittels der ein Sudoku Spielfeld benannt werden kann. Die Darstellung des Buchstaben und Zahlen Salates wirkt etwas kryptisch, doch erlaubt dies den leichteren Zugriff und die Speicherung der Felder. Eine Sudoku Aufgabe mit 24 vorgegebenen Zahlenwerten lautet z.B. 84-tLdf-gMB8-R4s-6LAzh-EBYIU-DVA0g-r80CM-paSc und kann über den Link http://apps.internethumor.de/sudoku?sudokucode=84-tLdf-gMB8-R4s-6LAzh-EBYIU-DVA0g-r80CM-paSc referenziert werden. Nach Aufruf des Links wird zunächst das Spielfeld ungelöst angezeigt und kann dann durch Klick auf den Solve-Button automatisch gelöst werden.
Der Sudoku-Code wird nach Eingabe einer Spielmatrix angezeigt, sobald man auf den Solve-Button geklickt hat. So kann ein selbst erzeugtes Spielfeld immer wieder angezeigt werden.
Mit der Version 1.3 ist die Zusendung des Spielfeldes per Mail möglich. Darüber hinaus wurden kleinere Fehler behoben.
Mit dem Create-Button wird aus einer (mittlerweile beträchtlichen) Datenbank ein Sudoku-Rätsel ausgewählt und dargestellt. Die Sudokus in der Datenbank sollten alle lösbar sein.
Die Version 1.4 des SuDoKu Solvers kommt nun auch mit Diagonal Sudokus zurecht kommt. Hierzu ist lediglich vor dem Lösen des Rätsels ("solve") ein Haken im Feld "diagonal" zu setzen.
Version 1.5 ist aktuell die letzte Version in der Reihe des SuDoKu Solvers in der auch das Backtracking Verfahren implementiert wurde. Hierdurch sollten sich nun alle valide Sudoku Rätsel lösen lassen.
Viel Vergnügen!
Sudoku Newsletter
Falls sie täglich ein neues Sudoku Feld in ihrem Postfach finden möchten, so tragen Sie sich in den kostenlosen SuDoKu Newsletter ein. Aus dieser Liste können Sie sich jederzeit auch wieder abmelden. Ihre persönlichen Daten werden vertraulich behandelt und nur zum Zwecke des Versands der Sudoku Rätsel verwendet.
Sudoku Wissen
- Dreiecksform
- Normiert
Wussten Sie, dass sie ganze Spalten und Zeilen in Sudoku Spielfeldern (außer bei Diagonal-Sudokus) vertauschen können ohne dass das Rätsel dadurch ungültig wird? Damit kann man durch geschicktes Tauschen der Zeilen und Spalten alle Zahlenwerte in in eine Ecke bringen. Dies dürfte auch eine zulässige Vereinfachung der Lösung sein, allerdings wird die Wiederherstellung des Ausgangsfeldes (alle Tauschschritte in umgekehrter Folge) recht unübersichtlich.
Ferner können Sie in jedem gültigen Sudoku die Zahlen austauschen. Ersetzen Sie dabei alle Vorkommen einer Ziffer durch eine beliebige andere (sofern die andere Ziffer noch nicht auf dem Spielfeld ist, oder durch ein andere ersetze wird). Einfachster Fall: Alle vorhandenen Ziffern um 1 erhöhen (aus 1 wird 2, aus 2 wird 3, etc. aus 9 wird allerdings 1). Es bleibt nach wie vor ein gültiges Rätsel.
Aus der Kombination dieser beiden Erkenntnisse kann jedes Sudoku in ein eindeutig identifizierbares Feld gewandelt werden und gleichartige Sudokus ermittelt werden. Beispiel: Das Feld wird durch Zeilen und Spaltenvertauschungen so angeordnet, dass das linke obere Feld mit einem Wert besetzt ist und in der ersten Zeile und Spalte je die meisten Werte enthalten sind. Die nächsten Zeilen und Spalten haben je eine geringere Anzahl an Ziffern. Im Idealfall erhält man eine art Dreiecksform. Im nächsten Schritt ändern Sie die Zahlenwerte in der Art, dass das linke obere Feld den Wert 1 erhält. In Leserichtung weiter werden die anderen Zahlen aufsteigend umbenannt. (Gleiche Ziffern erhalten den gleichen Wert!) Kongruente Sudoku Spielfelder haben dadurch eine gleiche Dreiecksdarstellung.
In den nebenstehenden Bildern wird die Normierung des Bespielfeldes gezeigt. Bei der Normierung wurden die Ziffern wie folgt ersetzt: 2 wird 3, 3 wird 6, 4 wird 8, 5 wird 2, 6 wird 5, 8 wird 9 und 9 wird 4. 1 und 7 sind unverändert.
Mehr...
Aktuelles
Nächtliche Wartungsarbeiten zur Leistungsverbesserung
Suche
Handelsregisterauszug
Webhosting
Produkt- und Preisvergleich
Billig einkaufen
Internet Ratgeber
