Vor einiger Zeit habe ich an dieser Stelle über das Problem des Sudoku Generierens berichtet. Heute möchte ich einen Algorithmus zum Lösen vorstellen, wie er so ähnlich in Mobile Sudoku implementiert ist:
- Einfaches Einschränken – Man trage alle 9 Zahlen in jedes freie Feld ein und streicht all die, die in der Zeile, Spalte oder dem Teilbereich vorkommen.
- Zahl setzen – Wenn in einem Feld nur eine einzelne Möglichkeit verbleibt, trägt man diese als sicher ein und beginnt von vorne.
- Weiteres Einschränken – Kommen zwei Zahlen in einer Zeile (Spalte/Teilbereich) in zwei Feldern jeweils beide exclusiv vor kann man diese Zahlen aus allen anderen Feldern dieser Zeile (Spalte, Teilbereich) streichen.
Analog geht dies für 3 Zahlen in 3 Feldern und 4 Zahlen in 4 Feldern… - Einschränken Stufe Zwei – Kommen zwei Zahlen nur in zwei Feldern vor und in keinem anderen, so kann man alle anderen Zahlen aus den zwei Feldern streichen.
Wiederum funktioniert dies analog für drei, vier und fünf Zahlen. - Einschränken Stufe Drei – Kommt eine Zahl z in einer Spalte s (bzw. Zeile) eines Teilbereiches vor und ist aber für jede anderen Zeile des Teilbereiches ausgeschlossen, so kann man die Zahl aus allen Feldern der Zeile s außerhalb des Teilbereiches streichen.
Mit diesen Einschränkungsregeln solltet Ihr euer Sudoku in die Knie zwingen. Ansonsten ist es mit großer Wahrscheinlichkeit nicht eindeutig lösbar.
[…] Hallo liebe/r Besucher/in, mit großer Wahrscheinlichkeit hast Du über das Suchbegriff “Sudoku” hierhergefunden. Die Buschtrommel hat sich neben anderen Themen zur Aufgabe gemacht, Aufklärung zu Sudoku zu betreiben. So ist sie eine der ersten deutschen Seiten, die das Thema Symetrie von Sudoku-Rätseln offen anspricht. Es wird verraten, mit welchen Techniken man Sudokus effizient generieren oder lösen kann. Wenn du der Ãœberzeugung bist, dass sich hier wertvolle Informationen finden, kannst du jetzt deine Stimme für die Buschtrommel abgeben! […]
Bin begeistert von Sudoku, aber komme nicht mehr weiter mit den einfachen Lösungsmethoden. Irgendwie benötige ich jetzt die Profis. danke für Hilfe
[…] Ein Nachtrag zum Artikel mit dem ultimative Lösungsalgorithmus. Heute Stelle ich Beispiele für die Teilstrategien "Weiteres Einschränken" und "Einschränken Stufe Zwei vor".Weiteres Einschränken – Die Sieben und die Acht kommen jeweils gemeinsam und exclusiv in zwei Kästchen des 3×3-Bereiches vor. Es können also ale Vorkommen dieser Zahlen außerhalb der eingekreisten Kästchen gestrichen werden. Einschränken Stufe Zwei Die Sieben und die Acht komen nur in zwei Kästchen vor und in keinem anderen, so kann man alle anderen Zahlen aus zwei eingekreisten Feldern streichen. Die 9 wird gestrichen!Viel Spass mein knobeln! […]
ich bin mir nicht sicher ob ich deine erklärungen richtig verstanden hab, aber ich glaub , dass ich noch ein verfahren zum einschränken kenne…ich versuchs mal zu erklären
1,2,3|,4,5,6,|7 x y
der ist tatsächlich abgeschnitten, vielleicht konnte ein Zeichen nicht verarbeitet werden.
Eure Tipps sind klasse. Jetzt fällt mir Sudoku viel leichter. Danke schön!