3-Farben-3-Formen-Sudoku

(Teil-)Lösung prüfen 
 sichtbare Motive, Zufallswahl mit  Versuchen, Konflikttiefe
Nr.

Ziel

In jeder der neun Zeilen, in jeder der neun Spalten und in jedem der neun 3 × 3 Zellen großen Quadrate kommt jedes der neun Motive genau einmal vor. Lösen Sie das Sudoku, indem Sie jede der leeren Zellen mit genau einem Motiv belegen! Es gibt nur eine Lösung.

Benutzung

Ein Mausklick auf eine leere Zelle zeigt die Motive in verkleinerter Form. Ein Doppelklick auf eines der Motive belegt die Zelle damit. Ein einfacher Klick entfernt das Motiv aus der Auswahl. Ein weiterer Klick auf die leere Stelle zeigt es wieder.

Eine Zellenbelegung kann durch einen einfachen Klick zurückgenommen werden. Die Zelle erscheint wieder leer wie in der Ausganssituation.

(Teil-)Lösung prüfen

Die belegten Zellen werden überprüft. Fehlbelegungen werden schwarz umrahmt und ihre Anzahl wird dokumentiert. Sie können einfach weiterspielen. Der schwarze Rahmen verschwindet, wenn Sie die Belegung zurücknehmen.

Die Überprüfung kann zu jedem Zeitpunkt und beliebig oft durchgeführt werden.

Neues Sudoku

Mit der Eingabe einer Nummer kann ein bestimmtes Sudoku aufgerufen werden. Durch Weglassen der Nummer wird eine Nummer abhängig vom Zeitpunkt des Aufrufs gewählt.

Bei der Nummer handelt es sich um den Initialwert für die pseudozufällige Vorbelegung der Zellen. Gleiche Nummern führen zum gleichen Sudoku. Zwei verschiedene Nummern können aber auch das gleiche Sudoku erzeugen.

Schwierigkeitsstufe

Über den Schwierigkeitsgrad könnte die Anzahl der sichtbaren Motive Aufschluss geben. Je mehr Zellen bereits belegt sind, um so einfacher ist es wahrscheinlich, das Sudoku zu lösen. Wenn jedoch Motive offenbart werden, die vom menschlichen Benutzer leicht herauszufinden wären, vereinfachen diese das Sudoku kaum.

Ein weiterer Hinweis könnte die Anzahl der Versuche der Zufallswahl sein. Wenn mehr Versuche benötigt wurden als es sichtbare Motive gibt, mussten bei der Erstellung des Sudokus entsprechend viele Belegungen zurückgenommen werden. Das Programm hatte Motive zur Wahl zugelassen, die zu einem Regelverstoß führten. Es ist anzunehmen, dass dem eine Konstellation zugrunde liegt, die auch vom menschlichen Benutzer als schwierig empfunden wird. Wenn jedoch keine Fehlversuche vorliegen, bedeutet das nicht zwangsläufig, dass es sich um einfachere Konstellationen handelt. Das Programm könnte mit seiner Wahl auch nur Glück gehabt haben.

Nach der Rücknahme einer regelwidrigen Belegung wird das Motiv aus dem Pool der zur Wahl stehenden Motive entfernt. Dies kann zu weiteren Konflikten führen, die es erforderlich machen, vorhergehende Belegungen zurückzunehmen. Das bedeutet, dass das Programm mehrere Fehlversuche in Folge benötigte, um die Nichtverfügbarkeit eines Motivs festzustellen. Wahrscheinlich sind solche Konstellationen auch für den menschlichen Benutzer schwer zu durchschauen. Die Konflikttiefe gibt die maximale Anzahl an, in der solche aufeinanderfolgende Zurücknahmen vorkamen, und ist somit ein weiteres Indiz für die Schwierigkeitsstufe des Sudokus.

Es gibt unterschiedliche Herangehensweisen, um ein Sudoku zu lösen. Je nach bevorzugtem Verfahren kann dasselbe Sudoku dem einen Benutzer schwieriger erscheinen als einem anderen. Je nach bevorzugtem Verfahren erweisen sich die genannten Indizien auch als mehr oder weniger nützlich zur Einschätzung des Schwierigkeitsgrads.

Wie dieses Sudoku generiert wurde

Bei einem Sudoku handelt es sich um eine Anordnung von Elementen, von Vorbelegungen, die erstens eine Anordnung der noch fehlenden Elemente unter Einhaltung der Regeln zulässt, und die zweitens nur eine mögliche Anordnung gemäß der Regeln zulässt. Es wird also eine Methode benötigt, mit der der Zustand der eindeutigen Lösbarkeit festgestellt werden kann. Es dürfen auch mehr Elemente vorbelegt werden als für die Eindeutigkeit notwendig wären. Das bedeutet, eine Methode, die gewisse eindeutige Konstellationen nicht erkennt, genügt dennoch der Anforderung, wenn sie nur sicherstellt, dass eine behauptete Eindeutigkeit korrekt ist.

Eindeutigkeit kann an den verschiedenen Bestandteilen eines Sudokus bestimmt werden: Als Ansammlung von Regelverbänden (Zeilen, Spalten, 3×3-Quadrate) betrachtet, ist ein Sudoku dann eindeutig, wenn jeder Verband nur noch eine seiner ursprünglich 9! Möglichkeiten hat, seine Motive und Zellen einander zuzuordnen. Dies ist gleichbedeutend damit, dass jede Zelle des Sudokus nur noch eines seiner ursprünglich neun möglichen Motive zur Verfügung hat, oder damit, dass jedes der 81 Motivelemente nur noch eines seiner ursprünglich 81 möglichen Zielzellen hat. Im vorliegenden Verfahren wird ein leeres Sudokuspielfeld als eine Ansammlung der möglichen Motive aller Zellen betrachtet, die sich im Zuge der Belegungen immer weiter leert. «Möglich» ist hier im strengen Sinn gemeint. Ein zugeordnetes Motiv zählt nicht mehr. Es zählt nur, solange es eine echte Alternative zu anderen möglichen Motiven darstellt. Mit der Eindeutigkeit des Sudokus dürfte es keines mehr geben.

Ein Sudoku wird generiert, indem ein Motiv nach dem anderen aus dem Pool gefischt und seine Zelle damit belegt wird. Das sind die sichtbaren Motive. Mit jeder Belegung entfallen auch alle anderen möglichen Motive der Zelle für die weitere Belegung. Sie werden aus dem Pool entfernt. Unter Berücksichtigung der Sudokuregel kommt darüber hinaus meistens noch eine Reihe weiterer Poolmotive nicht mehr für eine Belegung in Betracht. Im Idealfall sollten diese erkannt werden. In der Praxis trifft dies für einen großen Teil davon zu, der ebenfalls gestrichen wird. Auf diese Weise wird die zunehmende Einschränkung der erlaubten Belegungen messbar in der schwindenden Anzahl der noch im Pool befindlichen Motive. Auch Motive, die durch die Reduzierung des Pools alternativlos geworden sind, werden gelöscht. Dies sind implizite Belegungen. Sie bilden die verdeckten Zellen, deren Motive der Spieler erknobeln muss. Da sie mit der Löschung der Zufallswahl entzogen sind, wird die Anzahl der sichtbaren Motive niedrig gehalten. Zur Generierung leichterer Sudokus könnte man die Erkennung der Eindeutigkeit von der Zulassung zur Wahl trennen.

Der spannende Punkt ist die Ermittlung der «Reihe weiterer Poolmotive», die nicht mehr für eine Belegung in Betracht kommen. Das naheliegendste sind die gleichartigen Motive in den unmittelbar tangierten Verbänden. Jede Zelle ist Teil einer Zeile, einer Spalte und eines 3×3-Quadrats. Da das gewählte Motiv in den Restzellen dieser Verbände nicht mehr verwendet werden kann, müssen die entsprechenden Poolmotive eliminiert werden. In den ersten Belegungen ist es damit auch getan. Irgendwann wird die sukzessive Entfernung von Zellmotiven jedoch zu einer heimlichen Zellbelegung führen. Die Zelle hat nur noch ein mögliches Motiv. Das hat nicht nur Konsequenzen für den Status des Motivs, das aus dem Pool entfernt werden muss, sondern auch für die Verbände der Zelle. Eine implizite Belegung erfordert diesbezüglich die gleiche Behandlung wie eine explizite. Und die kann zu weiteren impliziten Belegungen führen. Ab einem gewissen Stand der Vorbelegung kann eine einzige weitere Wahl durch rekursive Anwendung der Verbandsbereinigung den Pool enorm reduzieren.

Es können sich aber auch noch andere Fälle von Eindeutigkeit einstellen. Für eine gezielte Steuerung des Schwierigkeitsgrads könnten verschiedene Kombinationen aus Überwachungskriterien der Eindeutigkeit angewendet werden. Im vorliegenden Verfahren wird neben der Anzahl der einer Zelle zur Verfügung stehenden Motive auch noch die Anzahl der einem Motiv in einem Verband zur Verfügung stehenden Zellen überwacht. Jedes entfernte Poolmotiv bedeutet für jeden der drei Verbände, zu denen die Zelle des Motivs gehört, dass das Motiv auf einen der Plätze im Verband verzichten muss. Wenn es nur noch eine Zelle hat, ist die Zuordnung alternativlos. Alle anderen bisher möglichen Motive der Zelle müssen weichen, und auch diese implizite Belegung muss eingereiht werden in die Kette der noch zu erledigenden Verbandsbereinigunen.

Die Ermittlung der aus dem Pool zu entfernenden Motive ist damit jedoch nicht vollständig. Was die Überwachungskriterien betrifft, kann das Programm nur bis eins zählen. Dabei ist das nur der Spezialfall der allgemeineren Regel: «Wenn in einer bestimmten Anzahl an Zellen in einem Verband nur die gleiche Anzahl an Motiven möglich ist, beanspruchen diese Zellen diese Motive exklusiv.» Mit zunehmender Anzahl steht jedoch der Aufwand für die Überwachung in einem zunehmend ungüngstigen Verhältnis zum wahrscheinlichen Auftreten des Falls. Außerdem blieben auch damit immer noch Abhängigkeiten offen, die durch die diversen Querverbindungen der Verbände bestehen. Letztendlich ist jede Zelle eines Sodukus mit jeder anderen vielfach durch ein Netz indirekter Abhängigkeiten verbunden. Mit Fehlbelegungen wäre dann zwar immer weniger aber immer noch zu rechnen. Auch dann müsste eine Behandlung der Fehlbelegungen realisiert werden.

Für die entgangenen zu entfernenden Motive ist ein Trial-On-Error-Mechanismus eingebaut, der sie erst nachträglich und nur durch Zufall als solche erkennen lässt. Hierzu werden Konfliktfälle definiert. Als Konflikt wird registriert, wenn ein den Eindeutigkeitskriterien entsprechendes Motiv im Zuge einer Bereinigung (und nicht per impliziter Belegung) aus dem Pool entfernt werden soll. Dann wird die letzte explizite Belegung zurückgenommen und das Motiv aus dem Pool entfernt. Hierbei kann natürlich erneut ein Konflikt auftreten, so dass eine rekursive Rücknahme erforderlich wird.

Eine Zufallswahl ist, zumindest ab einer gewissen Anzahl an Belegungen, immer zugleich ein Test auf einen eintretenden Konflikt. Vom Standpunkt der möglichst frühen Feststellung der Eindeutigkeit aus, ist das Erwischen einer Fehlbelegung der Glücksfall. Für die gezielte Erzeugung besserer Sudokus könnten ab einem gewissen Grad der Belegung systematische Tests implementiert werden.

Warum Motive und nicht Zahlen?

Warum Zahlen? Ein Zahlen-Sudoku unterscheidet sich von einem Motive-Sudoku nur dadurch, dass die Motive dort Zahlen genannt werden, weil sie wie Zahlen aussehen, obwohl es keine sind. Basteln Sie schon mal Ihre eigenen Motive! Demnächst gibt es hier eine Möglichkeit, sie einzubinden. Die grellen Farben meiner Motive machen sich nach ein paar Stunden bemerkbar...