Mittwoch, 22. Oktober 2014

Lösungsstrategien für Sudokus

Nachdem ich im vorigen Post die Grundlagen zu der Postreihe Lösen / Generieren von Sudokus erläutert habe, möchte ich in diesem Post, wie angekündigt, die implementierten Lösungsstrategien vorstellen. Diese sind aus denen im vorigen Post genannten Quellen entnommen und mit einer Schwierigkeit gekennzeichnet, damit wir beim Generieren von Sudokus prüfen können, wie schwer diese sind. Wie bereits erwähnt, kann ich aus eigener Erfahrung die Schwierigkeit der Strategien schlecht einschätzen. Ich würde mich also sehr um Rückmeldung freuen, ob die Einteilung in etwa stimmt - und noch mehr über neue Strategien, die so wichtig sind, dass das Programm sie kennen sollte.
Die bis jetzt implementierten Regeln zur Lösung von Sudokus sind (die Namen sind ein Mix aus den Bezeichnungen in Creating Sudokuswww.sudokuoftheday.com/techniques und der deutschen Wikipedia Seite - dort auch genauere Erklärungen -, aber diese Techniken sind allgemein bekannt, die Schwierigkeit ist aufsteigend):

  • Stufe 1: 
    • Naked Single
    • Hidden Single
  • Stufe 2:
    • Naked Pair
    • Hidden Pair
    • Candidate Line
  • Stufe 3:
    • Naked Triple
    • Hidden Trippe
    • XWing
    • (theoretisch ist die Methode des naked / hidden X für beliebige X implementiert, wird aber nur bis X = 3 angewendet)
  • Stufe 4:
    • Guessing
Nun zur Erklärung, was diese Regeln im einzelnen sind.
Zuerst aber kurz ein paar Basisbegriffe: Die einzelnen Kästchen des Sudokus heißen Felder. Ich nenne eine Zahl als Lösung in das Feld eintragen "das Feld ausfüllen". Es hilft, sich alle möglichen Zahlen, die basierend auf der aktuellen Lösung noch das Feld füllen könnten, zu merken. Dieses sind die Kandidates des Feldes. Reihe und Spalte sollten klar sein, Box bezeichnet das 9er Kästchen, zu welchem das Feld gehört. Gruppe bezeichnet alle Felder in der Spalte, Zeile und Box eines Kästchens.

Naked Single: Gibt es für ein Feld nur noch einen Kandidaten, kann man das Feld mit diesem füllen.

Hidden Single: Wenn ein Kandidat in einer Zeile, Spalte oder Box nur noch genau einmal vorkommt, kann das Feld mit ihm gefüllt werden. (Diese beiden ersten Techniken werden wohl eigentlich alle intuitiv anwenden, und viele es vielleicht auch dabei belassen haben bis jetzt - mich eingeschlossen.)

Naked Pair: Wenn in 2 verschiedenen Feldern einer Zeile, Spalte oder Box nur genau die selben 2 Kandidaten vorkommen wissen wir zwar noch nicht, welcher Kandidat in welches Feld  gehört, aber dass die beiden Kandidaten auf jeden Fall in die beiden Felder gehören. Wir können also die beiden Kandidaten aus allen anderen Feldern der Zeile, Reihe oder Box löschen.

Hidden Pair: Wenn 2 verschiedene Kandidaten in einer Zeile, Spalte oder Box nur noch in genau 2 Feldern vorkommen, wissen wir zwar noch nicht, welcher Kandidat in welches Feld  gehört, aber dass die beiden Kandidaten auf jeden Fall in die beiden Felder gehören. Wir können also alle anderen Kandidaten aus den Feldern löschen.

Candidate Line: Wenn alle Kandidaten für eine Zahl in einer Box auf einer Linie liegen, können wir daraus schließen, dass diese Zahl auch irgendwo auf der Linie liegen muss, und sie von der Kandidatenliste aller anderen Felder in den anderen beiden Boxen auf der Linie streichen.

Naked / Hidden Triple: Das gleiche wie beim Naked / Hidden Double, nur mit 3 Feldern.

XWing: Hier verweise ich zur Visualisation nochmals auf Literatur und erkläre das Verfahren ohne Grafik. Wenn es 2 Reihen (Spalten) gibt, bei denen die gleichen 2 Kandidaten nur in genau 2 Feldern liegen und diese auch noch in den selben Spalten (Reihen) liegen, dann wissen wir, dass diese Zahlen auch in einem der 4 Fehler liegen müssen. Somit können wir diese Zahlen aus den Kandidatenlisten aller Felder in den 2 Spalten (Reihen) der Felder löschen.

Guessing: Hierbei sucht man durch Ausprobieren eine Lösung, geht also alle nicht ausgefüllten Felder durch und setzt eine mögliche Zahl ein. Dann geht man zum nächsten und schaut, ob immer noch eine Lösung möglich ist, andernfalls muss man ein (oder mehrere) Felder zurückgehen. (Diese Beschreibung ist sehr nah an der Implementierung, aber sicherlich gibt es noch viele andere Möglichkeiten, alle möglichen Belegungen auszutesten.)




Keine Kommentare:

Kommentar veröffentlichen