Sudoku

Der Erstellungsalgorithmus

Hier geht es nun um die Erstellung von Sudokus. Generell gibt es verschiedenste Arten von Algorithmen um Sudokus zu erstellen. Wir verwenden einen Algorithmus, der bei jeder Ausführung mit an Sicherheit grenzender Wahrscheinlichkeit immer ein neues Sudoku erzeugt. Es gibt einige Generatoren im Internet, die sich einfacher Methoden bemühen, das letztliche Ergebnis jedoch nie stark von einander abweicht und somit der Rätselspaß ein wenig verloren geht.

Unser Algorithmus platziert nacheinander die Zahlen von 1 bis 9 jeweils 9-fach im Rätsel, natürlich den Regeln entsprechend, immer nur einmal pro Zeile/Spalte. Unser Spielfeld ist dabei ein zweidimensionales Byte-Array (jeweils von 0 bis 8). 1 bis 9 repräsentieren dort jeweils die Zahlen, eine 0 bedeutet ein freies Feld. Im Code sieht dies wie folgt aus:

For Number = 1 To 9
 For i = 1 To 9

In der inneren Schleife werden nun per Zufallsgenerator die Koordinaten bestimmt, an der die Zahl platziert werden soll.

rndX = Int(Rnd * 9)
rndY = Int(Rnd * 9)

Nun wird überprüft, ob die Zahl an dieser Stelle möglich ist und falls nicht, wird erneut ein Feld ausgesucht. Ist das Platzieren möglich, wird die Zahl in die Lösungsmatrix eingetragen. Zum Schluss wird noch einmal das gesamte Rätsel überprüft, ob jede Zahl 9 mal vorkommt.

Die Lösungsmatrix ist damit erstellt, jedoch ist es noch ein weiter Weg zum interessanten Rätsel, denn es fehlen die Lücken. Diese werden nun auch wieder per Zufall ausgesucht. In einer Schleife wird nun immer ein Feld entfernt und geprüft, ob das Rätsel noch eindeutig lösbar ist, denn es darf später nicht vorkommen, dass man mehrere Zahlen eintragen kann. Die Lösbarkeit testen wir mit der Funktion "SolveSudoku", welche ein Sudoku löst und die Anzahl der Lösungen zurückgibt. Näheres zu dieser Funktion gibt es im Abschnitt "Sudokus lösen". Hier kommt nun auch der Schwierigkeitsgrad mit ins Spiel. Je nachdem, welche Stufe eingestellt ist werden mehr (schwieriger) oder weniger (leichter) entfernt. Die Formel dafür sieht so aus:

uCount = 45 + (m_Difficulty * 2)

uCount ist die Anzahl der zu streichenden Felder. Es werden also immer mindestens 45 Kästchen gelöscht. m_Difficulty reicht von 0 (sehr einfach) bis zu 5 (Profi).

Zurück zur Einführung | Weiter zum Lösungsalgorithmus



Kontakt - Impressum - Datenschutz
Alle Grafiken, Bilder, Texte und Dokumente sind urheberrechtlich geschützt und dürfen nicht ohne schriftliche Genehmigung verwendet werden. Copyright © 1998-2008 by Martin Walter.
Alle Rechte vorbehalten. all rights reserved.