WaBis

walter.bislins.ch

Sudoku: Begriffe

In den Beschreibungen zum Sudoku werden Begriffe verwendet, die auf dieser Seite erklärt werden.

Zellen, Zeilen, Spalten und Boxen

Zeile 2 (blau), Spalte 3 (grün) und Box 6 (rot) eines Sudokus

Ein Sudoku besteht aus 81 Zellen, die in einem 9 x 9 Raster angeordnet sind. In jeder Zelle kann eine Zahl von 1 bis 9 stehen. Die Zellen werden in 9 Zeilen, 9 Spalten und 9 Boxen organisiert.

Die Zeilen, Spalten und Boxen werden von 1 bis 9 nummeriert. Zeilen werden von oben nach unten und Spalten von links nach rechts nummeriert.

Jede Zelle kann durch den Schnittpunkt einer Zeile mit einer Spalte eindeutig bezeichnet werden. Dieser Schnittpunkt wird als Zellen-Koordinate bezeichnet. Oft werden Zellen mit folgender Abkürzung angeschrieben:

  • Koordinate: r3c4 (row 3 = Zeile 3, column 4 = Spalte 4).
  • Koordinate: r57c2 meint die Zellen Zeile 5 Spalte 2 und Zeile 7 Spalte 2.

Jede Box besteht aus 3 mal 3 Zellen. Die Boxen werden von links oben nach rechts unten von 1 bis 9 nummeriert. Die Zellen verschiedener Boxen überlappen sich nie. In jeder Box darf jede Zahl von 1 bis 9 nur exakt einmal vorkommen. Die Zellen innerhalb einer Box werden als Box-Zellen bezeichnet und werden wie die Boxen selbst von links oben nach rechts unten nummeriert. So hat z.B. die Box-Zelle 5 der Box 3 die Koordinaten r2c8.

Häuser

Es gibt drei verschiedene Typen von Häusern: Zeilen (engl.: rows, mit "r" abgekürzt), Spalten (engl.: columns, mit "c" abgekürzt) und Boxen (engl.: boxes, mit "b" abgekürzt"). Unter bestimmten Umständen kann auch eine Zelle selbst als Haus gesehen werden.

Wenn zwei Zellen im selben Haus sind (gleiche Zeile, gleiche Spalte oder gleiche Box), dann sagt man, sie sehen einander, oder sie sind Partner. Das ist für viele Strategien wichtig, weil zwei Zellen, die einander sehen, nach den Sudoku-Regeln nicht dieselbe Lösungs-Zahl haben können.

Zahlen und Kandidaten

Zellen werden gefüllt mit Zahlen von 1 bis 9. Eine durch Anwendung einer Lösungs-Methode gesetzte Zahl wird als Lösungs-Zahl bezeichnet. Die Zahlen, die zu Beginn bereits vorhanden sind, sind die Vorgaben. Zellen mit Vorgaben werden im gelösten Sudoku mit grauem Hintergrund gezeichnet.

Mögliche Werte für noch nicht gefüllte Zellen sind Kandidaten. Die Kandidaten werden im Gitter gezeigt, welches mit der Option Kandidaten-Gitter anzeigen sichtbar gemacht werden kann.

Bei Sudoku Lösungs-Methoden, welche auf Chains und Links basieren, werden Kandidaten logisch zu einer Kette (Chain) verknüpft. Eine solche Verbindung (Link) exisitiert immer zwischen einem Kandidaten-Paar.

Zahlen- und Kandidaten-Gitter

Meine Sudoku-App stellt ein Sudoku zur besseren Übersicht in zwei separaten Gittern dar:

Zahlen-Gitter
Sudoku Zahlen-Gitter

Kandidaten-Gitter
Sudoku Kandidaten-Gitter

Im linken Zahlen-Gitter werden bereits gesetzte Zahlen angezeigt. Bei komplizierteren Sudoku Lösungs-Methoden wie X-Chain und XY-Chain wird zusätzlich die Reihenfolge der Kettenglieder in keinerer Schrift und in Klammern angezeigt (siehe Beispiel Darstellung der Lösungs-Methoden).

Im Zahlen-Gitter können Zahlen über die Tastatur eingegeben werden, indem eine leere Zelle angeklickt wird und dann eine Zahlen-Taste gedrückt wird. Die Zellen in diesem Gitter sind normale Eingabefelder.

Im rechten Kandidaten-Gitter, welches mit der Option Kandidaten-Gitter anzeigen ein und ausgeblendet werden kann, werden zusätzlich zu den Lösungs-Zahlen die in den leere Zellen möglichen Kandidaten angezeigt. Wenn die Option Methoden grafisch anzeigen aktiviert ist, werden die Funktionsweise und Auswirkungen einer ausgewählten Lösungs-Methode farblich angezeigt.

Im Kandidaten-Gitter können Zahlen und Kandidaten durch Anklicken einer Zelle gesetzt und gelöscht werden (siehe Zahlen setzen und Kandidaten löschen im Kandidaten-Gitter).

Konstellationen

Der gerade aktuelle Zustand eines Sudokus wird als Konstellation bezeichnet.

In den meisten Konstellationen können mehrere Methoden angewandt werden um einen Schritt weiter auf dem Weg zur Lösung zu gelangen. Die Sudoku-App zeigt bei jeder Konstellation an, wie viele Methoden gefunden wurden, die weiter führen. Mit den Selektions-Buttons kann eine der Methoden für den nächsten Schritt ausgewählt werden.

Für die Lösung des Sudokus spielt es keine Rolle, welche der angebotenen Methoden in welcher Reihenfolge ausgewählt werden. Es gibt sehr viele Lösungswege für ein bestimmtes Sudoku, aber quasi alle Wege führen nach Rom, nur die Weglänge und der Schwierigkeitsgrad kann sich unterscheiden.

Jedes Anwenden einer Methode führt also von der aktuellen Konstellation zu einer von mehreren möglichen nächsten Konstellationen. Sehr oft können sogar unterschiedliche Methoden zur selben nächsten Konstellation führen. In der Sudoku-App kann mit der Option Alle Methoden berechnen eingestellt werden, ob alle programmierten Methoden aufgelistet werden sollen, die zu einer bestimmten nächsten Konstellation führen, oder ob jeweils nur die Methode mit dem niedrigsten Level angeboten werden soll.

Level (Schwierigkeitsgrad)

Die Sudoku-App gibt bei jeder Lösungs-Methode einen Level an. Ich spreche hier absichtlich von Level und nicht von Schwierigkeitsgrad, auch wenn der Level einen Anhaltspunkt für den Schwierigkeitsgrad liefert. Es ist praktisch nicht möglich, einen Schwierigkeitsgrad zu berechnen, da dieser nicht nur von der angewandten Methode alleine abhängig ist, sondern auch von der aktuellen Konstellation des Sudokus. Zudem hängt der Schwierigkeitsgrad sehr davon ab, ob das Kandidaten-Gitter zuhilfe genommen wird oder nicht. So ist ein Naked Single je nach Konstellation im Zahlen-Gitter nur mühsam zu finden, wogegen er im Kandidaten-Gitter sofort auffällt.

Der Level besteht aus zwei Zahlen, die durch einen Dezimalpunkt von einander getrennt sind. Die Zahl vor dem Punkt gibt an, zu welcher Methoden-Gruppe eine Methode gehört. Die Zahl nach dem Punkt gibt an, wie schwer die Methode innerhalb der Gruppe eingeschätzt wird. Diese Zahl gibt zum Beispiel bei Chains ein Mass dafür an, wie viele Kettenglieder die Kette hat, wird jedoch auch von der Art der Kette beeinflusst (offene Kette oder geschlossene Kette).

Am Ende eines von der Sudoku-App gelösten Rätsels gibt die App den Zug mit dem höchsten je verwendeten Level an. Von Hand ausgeführte Züge können nicht und werden nicht bewertet.

Da es zu den meisten Konstellationen verschiedene mögliche Methoden gibt um zu einer nächsten Konstellation zu gelangen, können für ein und dasselbe Sudoku verschiedene Schwierigkeitsgrade resultieren, je nachdem in welcher Reihenfolge die Methoden angewandt werden.

Die in einer Konstellation verfügbaren Methoden können mit der Option Methoden sortiert nach Level nach dem Level sortiert werden.

Mit der Funktion Trivial wird das Sudoku soweit automatisch gelöst, bis keine Triviale Methode mehr angewandt werden kann. Dann stopt der Löser. Die trivialen Methoden haben die Level von 1.1 bis 1.9. Es handelt sich im die folgenden Methoden:

Triviale Methoden (Level 1)

Bei vielen Sudoku Lösungs-Methoden müssen mehrere Zellen bzw. die darin enthaltenen Kandidaten logisch zu Chains (Ketten) verbunden werden. Die Verbindung wird immer über ein Kandidaten-Paar hergestellt. Eine solche Verbindung zwischen zwei Kandidaten wird als Link bezeichnet.

Ein Link kann zwischen zwei Kandidaten verschiedener Zellen oder zwischen zwei Kandidaten derselben Zelle bestehen.

Es werden zwei Arten von Links unterschieden: Weak Links (schwache Bindung) und Strong Links (starke Bindung).

 Für weitere Informationen siehe Grundlagen zu Links und Chains

Ein Weak Link (schwache Bindung) zwischen einem Kandidaten-Paar besteht immer dann, wenn die beiden Kandidaten nicht die einzigen im selben Haus oder derselben Zelle sind. Wenn zum Beispiel in einer Zeile noch drei oder mehr Kandidaten einer bestimmten Zahl vorkommen, so handelt es sich bei den Verbindungen zwischen je zwei dieser Kandidaten um Weak Links. Wenn in einer Zelle noch mehr als zwei Kandidaten vorkommen, so handelt es sich bei den Verbindungen zwischen diesen Kandidaten ebenfalls um Weak Links.

Ein Strong Link (starke Bindung) zwischen einem Kandidaten-Paar besteht immer dann, wenn die beiden Kandidaten die einzigen im selben Haus oder derselben Zelle sind. Wenn zum Beispiel in einer Zeile ein Kandidat einer bestimmten Zahl nur noch genau zweimal vorkommt, so handelt es sich bei der Verbindung zwischen diesem Kandidaten-Paar um einen Strong Link. Wenn in einer Zelle nur noch genau zwei Kandidaten vorkommen, so handelt es sich bei einer Verbindung zwischen diesen Kandidaten ebenfalls um einen Strong Link.

Die Art des Links zwischen einem Kandidaten-Paar muss immer peinlich genau unterschieden werden, denn sie ist für die logischen Schlussfolgerungen von essenzieller Bedeutung. Alle Chain- und einige andere Lösungs-Methoden beruhen auf einer Verkettung von Kandidaten-Paaren über eine bestimmte Reihenfolge der zwei Link-Arten. Die Methoden können nur verstanden werden, wenn du die Grundlagen zu Links und Chains verstanden hast.

Weitere Infos zur Seite
Erzeugt Donnerstag, 14. Februar 2013
von wabis
Zum Seitenanfang
Geändert Samstag, 18. Juli 2015
von wabis