Informatik
DE | ENContact

Bedienung in Kürze

Klickselektiert eine Zelle
Zahlentastesetzt den Wert der selektierten Zelle
Ctrl+Zahlentastesetzt oder löscht den Kandidaten in der selektierten Zelle (in der Kandidatensicht)

Die Sudoku Regel

Das Sudoku Spiel hat nur eine Regel:
Fülle das 9x9 Gitter mit den Zahlen 1 bis 9 aus, sodass alle Zeilen, Kolonnen und 3x3 Blöcke keine doppelten Zahlen enthalten. Anders gesagt, alle diese Regionen müssen alle Zahlen 1 bis 9 enthalten.

Allgemeine Benutzung dieses Spiels

Dieses Sudoku Spiel unterstützt Sie bei der Lösung von Sudoku Rätseln, die Sie in Zeitungen, Büchern und im Interner finden. Es stellt auch vorbereitete Rätsel in drei Schwierigkeitsstufen zur Verfügung. Die hauptsächlichen Eigenschaften dieses Spiels sind die folgenden:

Das Spiel hat zwei Phasen:

Phase 1

In der ersten Phase übertragen Sie das zu lösende Rätsel in das Spiel.

Während dieser Phase können Sie die Zahlen in den Zellen beliebig editieren. Wenn Sie auf eine Zelle klicken, wird sie grün. Das deutet an, dass Sie eine Zahl 1 .. 9 einsetzen können, indem Sie die entsprechende Taste auf der Tastatur drucken. Sie können eine Zahl mir einer anderen Zahl überschreiben, oder Sie können den Zellinhalt mit den Tasten x, 0, Del, Enter löschen. Wenn Sie Anfangsposition gesetzt haben, klicken Sie auf den Knopf Einfrieren. Die eingegebenen Zahlen werden "eingefroren" (dargestellt schwarz) und können nicht mehr verändert werden.

Noch bequemer ist es, ein Rätsel als eine Zahlenreihe zu erhalten, z.B. auf der Seite www.sudocue.net, diese Reihe in das Textfeld unter dem Gitter zu kopieren, und mit dem Knopf Setze in das Gitter einzufügen.

Sie können auch ein vorbereitetes Rätsel verlangen. Wählen Sie den Schwierigkeitsgrad und drucken Sie auf den Knopf Rätsel verlangen. Ein neues Rätsel wird in das Gitter eingefüllt und eingefroren. Alle verfügbaren Rätsel sind nur mit logischer Überlegung lösbar. Die Schwierigkeitsstufen haben die folgende Bedeutung:

StufeLösungsstrategien
Einfach Nackter Single
Versteckter Single
Mittel Block/Reihe Schnitt
Block/Kolonne Schnitt
Nacktes Paar
Schwierig Nackter Dreier
Verstecktes Paar
Versteckter Dreier
X-Wing

Phase 2

In der zweiten Phase lösen Sie das Rätsel. Sie klicken auf eine leere Zelle und setzen eine Zahl mit der entsprechenden Taste ein. Nun können Sie eine Zahl nicht direkt löschen, sondern müssen die Befehle Zurück (und Vor) anwenden. Das garantiert, dass die Zahlen in der umgekehrten Reihenfolge gelöscht werden als sie gesetzt wurden. Dies ist wichtig, wenn Sie z.B. mit der "Versuch-und-Irrtum" Strategie experimentieren. Sie erkennen die letzte eingefügte Zelle am grauen Hintergrund - diese Zelle wird gelöscht, wenn Sie Zurück drucken.

Der Knopf Kandidaten zeigen (resp. das Ankreuzfeld, resp. die Tastenkombination Ctrl c) schaltet zwischen den Sichten mit oder ohne sichtbare Kandidaten. Die Kandidaten sind die noch möglichen Werte für die Zelle. Ein der Kandidaten ist der Lösungswert. Die Kandidaten können editiert werden: die respektive Zahlentaste zusammen mit der Control- oder Alt-Taste schaltet zwischen der Präsenz und Absenz des Kandidaten in der selektierten Zelle. Diese Möglichkeit ist wichtig für fortgeschrittene logische Lösungsstrategien. Auch in der Kandidatensicht können Sie Werte der Zellen mit der respektiven Zahlentaste setzen.

Die Änderungen bei den Kandidaten können nicht rückgängig gemacht werden. Die Kandidaten können aber neu aus den ausgefüllten Zellen mit wieder berechnet werden. Der Befehl Kandidaten neu berechnen setzt die Kandidaten in den leeren Zellen auf die maximal mögliche Kandidaten, die mit den gefüllten Zellen konsistent sind. Alle Ihre Änderungen der Kandidaten gehen dabei verloren.

Der Befehl Konsistenz prüfen prüft ob alle soweit eingegebenen Werte mit der Sudoku Regel konsistent sind. Der Befehl prüft nicht, ob die Werte auch die richtigen Lösungswerte sind.

Befehle

Neues Rätsel
Ein neues Spiel wird gestartet. Das Gitter wird geleert, eine allfällig gezeigte Lösung wird gelöscht.
Einfrieren
Friert die aktuellen Zellwerte ein. Der aktuelle Zustand wird als das zu lösende Rätsel definiert.
Rätsel verlangen
Ein neues Rätsel mit der gewählten Schwierigkeitsstufe wird in das Gitter gesetzt und eingefroren.
Kandidaten zeigen
Der Knopf Kandidaten zeigen, oder das Ankreuzfeld, oder die Tastaturkombination Ctrl c schalten zwischen der normalen und der Kandidatensicht um.
Kandidaten neu berechnen
Die Kandidaten werden neu berechnet ausgehend aus den gefüllten Zellen. Die leeren Zellen erhalten die maximale Anzahl von Kandidaten, die mit der Sudoku Regel konsistent sind. Editierte Kandidaten gehen verloren.
Konsistenz prüfen
Die gefüllten Zellen werden auf die Konsistenz mit der Sudoku Regel überprüft. Es wird nicht geprüft, ob die ausgefüllten Zellen die richtigen Werte haben.
Alles löschen
Alle gesetzten, nicht eingefrorenen Zellen werden gelöscht und die Kandidaten werden neu berechnet.
Zurück
Die zuletzt ausgefüllte Zelle (mit grauem Hintergrund) wird gelöscht und alle Kandidaten werden neu berechnet. Nachher wird die zweit letzte Zelle grau markiert und kann mit diesem Befehl gelöscht werden usw.
Vor
Dieser Befehl macht den vorherigen Zurück Befehl rückgängig. Die Zelle, die mit dem letzten Zurück Befehl gelöscht wurde, bekommt ihren Wert zurück.
Lösung
Das Rätsel wird gelöst und die Lösung wird unten angezeigt.
Diese Funktionalität ist während etwa 2 Stunden vorhanden. Danach ist es nötig, das Browserfenster neu zu laden. Dabei geht das gegenwärtige Rätsel verloren. Wenn Sie mit dem Rätsel nach dem Reload fortfahren wollen, müssen Sie es zwischenspeichern und wiederladen:
  1. Kopieren Sie den String unterhalb des Gitters in einen Editor.
  2. Laden Sie das Browserfenster neu, indem Sie auf den Refresh-Knopf des Browsers klicken.
  3. Klicken Sie den Knopf "Neues Rätsel".
  4. Kopieren Sie den gespeicherten String vom Editor in das Feld unterhalb des Gitters.
  5. Klicken Sie den Knopf "Setze" neben dem eingefügten String.
  6. Fahren Sie mit der Lösung fort.
Setze
Die Sudoku Kodierung im nebenstehenden Feld wird in das Gitter eingefügt und als Startposition genommen. Der Befehl ist nur während der ersten Phase möglich. Während der Lösungsphase zeigt das Feld die Kodierung des gegenwärtigen Spielzustandes.

Maus und Tasten

Maus Klick
Ein Mausklick auf einer Zelle selektiert diese Zelle für die Eingabe der Lösungszahl. Die selektierte Zelle ist grün markiert.
Tasten 1, 2, ... 9
Mit einer Zahlentaste wird die entsprechende Zahl in die selektierte Zelle eingegeben.
Ctrl + 1, 2, ... 9
Wenn die Kandidaten sichtbar sind, dann bewirkt eine Zahlentaste zusammen mit Control oder Alt das Setzten oder Löschen des respektiven Kandidaten in der selektierten Zelle.
Ctrl + c
Die Tastenkombination Ctrl c schaltet um zwischen der normalen Sicht und der Sicht mit Kandidaten.

Browser Kompatibilität

Das Spiel wurde mit den folgenden Browsern auf Windows XP getestet:

Bemerkungen zur Implementierung

Generierung der Sudoku Rätsel

Ich generiere die Sudoku Rätsel offline mit einem C++ Programm. Zuerst erstelle ich ein zufällig ausgefülltes Sudoku mit Backtracking. Dann nehme ich Zahlen auf zufälligen symmetrischen Positionen weg. Die so entstandene Sudoku versuche ich mit den programmierten logischen Regeln zu lösen. Wenn ich eine Lösung finde, dann habe ich ein Rätsel konstruiert. Wenn die Sudoku mit den logischen Regeln nicht lösbar ist, versuche ich wieder eine andere zufällige Ausgangsposition. Um eine "schwierige" Sudoku zu generieren, brauche ich etwa 100'000 Versuche.

Lösung von Sudoku Rätseln

Durch Klicken des Knopfes "Lösung" wird das gegenwärtige Rätsel auf dem Server mit Backracking gelöst. Ursprünglich habe ich den Algorithmus in PHP programmiert, was für die generierten Rätsel ausreichend war. Es war aber zu langsam für schwierige Puzzles. Das 17-Puzzle
080004000000003005005000007002000000000070006400001030000000000000000140007250000
mit der Lösung
789564321624713985315982467972635814831479256456821739293146578568397142147258693
brauchte ca. 21 Sekunden.

Ich portierte den Algorithmus nach Perl. Das Programm war ziemlich hässlich wie erwartet, aber die Lösungszeit wurde auf 4 Sekunden reduziert, vermutlich wegen den random-access Arrays in Perl.

So war ich neugierig, wie sich Python verhalten würde, und portierte den Algorithmus auch in diese Sprache. Das Programm ist nicht nur schön, sondern zu meiner Überraschung auch am schnellsten - es löst das Rätsel in 2 Sekunden. Bravo Python!