Teil 5: Sudoku lokale lineare Suche

Die Sudoku Strategie „lokale lineare Suche“ reduziert übersichtlich und auf einfache Art Kandidaten aus den ermittelten Kandidatenlisten, so dass weitere Einer hervortreten.

Kapitel überspringen und gleich zur Sudoku-Spielplattform.

Inhalt Teil 5
Nachdem mit Teil 4: Sudoku nackte Einer die zweite der beiden Methoden, Einer zu finden, besprochen wurde, geht es nun bei jeder weiteren Strategie darum, Kandidatenlisten zu reduzieren um weitere Einer aufzuspüren. Die lokale lineare Suche (lS) stellt dabei die einfachste Methode dar, da man sie Block für Block und dort Ziffer für Ziffer anwenden kann.

Lokale lineare Suche
Bei der lokalen lineare Suche (lS) sucht man innerhalb von Blöcken nach Kandidaten (Ziffern), die nur in einer einzigen Zeile oder Spalte des jeweiligen Blocks vorkommen. Ist dies der Fall, ist die gesamte Zeile oder Spalte durch diese Ziffer gesperrt, auch wenn man noch nicht genau weiß, an welcher Stelle die Ziffer im untersuchten Block steht. Durch die Sperrung kann die Ziffer aber aus den Kandidatenlisten der Felder anderer Blöcke derselben Zeile oder Spalte eliminiert werden.

Beispiel/ lokale lineare Suche
Betrachten wir dazu den dritten der oberen drei Blöcken 1, 2 und 3 des 21er-Sudoku „sudoku_21er.txt“, das zunächst für sechs Spielzüge nur mit versteckten und nackten Einern gespielt wurde (und an dieser Stelle nicht mehr weiter gespielt werden kann, vgl. Teil 4). In Block 3 kommt die Ziffer 4 nur in der mittleren Zeile vor (Kandidatenlisten 3478 und 24). Das bedeutet konkret, dass die Ziffer 4 in jedem Fall in Zeile 2 steht und damit die Zeile 2 für die Ziffer 4 in den Blöcken 1 und 2 gesperrt ist (orange Linie):

In Block 1, Zeile 2, kann dementsprechend die Ziffer 4 kein Kandidat der Kandidatenlisten der Spalten 2 und 3 sein. Die Ziffer 4 muss daher aus den Kandidatenlisten der betroffenen beiden Felder #5 und #6 von Block 1 eliminiert werden. In Block 1, Feld #3, verbleibt auf diese Weise die Ziffer 4 als versteckter (Block-)Einer stehen (Zeile 1, Spalte 3):

Sudoku-Spielplattform/ lokale lineare Suche
Spielt man das 21er-Sudoku „sudoku_21er.txt“ auf der Sudoku-Spielplattform zunächst für sechs Spielzüge nur mit versteckten und nackten Einern, und schaltet dann erst die lineare lokale Suche (lS) ein, ergibt sich dementsprechend in der Schritt für Schritt-Lösung:
Spielzug 7
…
B3/ Z2 – lS (4) || B1/ Z2 #2 (#11): 247=>27
B3/ Z2 – lS (4) || B1/ Z2 #3 (#12): 247=>27
=> In Block 3, Zeile 2, ist die lineare lokale Suche (lS) mit der Ziffer 4 fündig, d. h. im genannten Block findet sich nur in Zeile 2 die Ziffer 4. Diese Ziffer wird daher aus allen anderen Feldern der Zeile 2 in den anderen Blöcken eliminiert, in diesem Fall aus Block 1, Zeile 2, Feld #2 dieser Zeile (Feld #11), und Block 1, Zeile 2, Feld #3 dieser Zeile (Feld #12). Aus den dortigen Kandidatenlisten 247 wird jeweils die Ziffer 4 entfernt, so dass jeweils die Kandidaten 27 übrig bleiben.
Dadurch lässt sich mit den üblichen Einer-Methoden in Zeile 1, Spalte 3, Block 1, Feld #3 dieses Blocks (Feld #3), die Ziffer 4 als versteckter (Block-)Einer (vE/B) aufspüren. Dieser Einer wird in nun in der Schritt für Schritt-Lösung in einem dunkleren Farbton angezeigt, da zu seiner Aufspürung eine zusätzliche Strategie angewendet werden musste:
…
Zeile 1/ Spalte 3/ B1 #3 (#3): – vE/B

Weiterer Treffer mit der linearen lokalen Suche (lS):
…
B7/ Z9 – lS (3) || B8/ Z9 #5 (#77): 358=>58
=> In Block 7, Zeile 9, ermittelt die lineare lokale Suche (lS) die Ziffer 3, d. h. in Block 7 kann die Ziffer 3 nur in Zeile 9 vorkommen. Diese Ziffer wird daher aus Block 8, Zeile 9, Feld #5 dieser Zeile (Feld #77), eliminiert.
…
B7/ Z9 – lS (5) || B8/ Z9 #5 (#77): 58=>8
=> In Block 7, Zeile 9, ermittelt die lineare lokale Suche (lS) die Ziffer 5, d. h. in Block 7 kann die Ziffer 5 nur in Zeile 9 vorkommen. Diese Ziffer wird daher aus Block 8, Zeile 9, Feld #5 dieser Zeile (Feld #77), eliminiert.
Dadurch verbleibt in diesem Feld in Zeile 9, Spalte 5, Block 8, Feld #8 dieses Blocks (Feld #77), mit der Ziffer 8 ein nackter Einer in der Kandidatenliste, der aufgrund der Anwendung einer zusätzliche Strategie nun ebenfalls in einem dunkleren Farbton angezeigt wird:
…
Zeile 9/ Spalte 5/ B8 #8 (#77): – nE

Weitere Beispiele
Beginnt man das 21er-Sudoku „sudoku_21er.txt“ bereits von Anfang an mit der Strategie der lokalen linearen Suche (lS) auf der Sudoku-Spielplattform, lässt sich das Sudoku in zehn Spielzügen lösen.

Am Ende von Teil 5
Kommt man mit Einer-Methoden nicht weiter, müssen zunächst zusätzliche Strategien angewendet werden, um Feldkandidaten zu reduzieren. Erst dadurch treten weitere versteckte und/oder nackte Einer hervor, und nur auf diese Weise lässt sich ein schwereres Sudoku Schritt für Schritt lösen. Mit der Sudoku-Strategie der lokalen linearen Suche (lS) kannst du bereits schwierige Sudokus knacken. Da man diese Strategie Block für Block und dort Ziffer für Ziffer anwenden kann, ist sie sehr übersichtlich und einfach, denn man kann sich stets auf wenige Kandidaten konzentrieren.

Zum nächsten Kapitel Teil 6: Sudoku hidden Subsets.