Sudoku

[handyplayer13]

Hallo an alle!

Ich bin neu hier und hoffe den richtigen Bereich für meine Frage gefunden zu haben.

Ich bin gerade dabei ein Spiel zu schreiben, das ein Sudoku Rätsel generiert, das man dann selber lösen kann.
Bin auf der Suche nach Informationen auf diesen Wikipedia Eintrag gestoßen:

Belegung des gelösten Sudokus erstellen:
1. Weg: Ein leeres Sudokufeld wird Zelle für Zelle durch „Auswürfeln“ (Zufallsgenerator) mit Ziffern befüllt. Sobald es zu einem Regelverstoß kommt, muss per Backtracking-Methode eine andere Belegung probiert werden. Dies ist weniger trivial als beim Lösen des Sudokus: Da eine möglichst „zufällige“ Belegung des Sudokufeldes benötigt wird, kann man nicht einfach alle Ziffern der Reihe nach durchprobieren. Es hindert aber nicht, alle Ziffern, sobald sie einmal „ausgewürfelt“ wurden, als künftig – für die jeweilige Zelle – gesperrt „abzuhaken“ (in einer Tabelle zu markieren)
2. Weg: Neun Einsen ohne Regelverstoß im Puzzlefeld verteilen. Dann neun Zweier, neun Dreier, usw. verteilen. Auch hier muss ein Backtracking-Algorithmus angewandt werden.
3. Weg: Man füllt eine Zeile oder eine Spalte in beliebiger Reihenfolge mit den erlaubten Ziffern, verschiebt dann mit jeder weiteren Zeile/Spalte die Ziffernfolge, bis man am Schluss alle möglichen Varianten untereinander/nebeneinander in einer n × n-Matrix vorliegen hat. Dies alleine wäre ein äußerst trivial zu lösendes Rätsel, da sich die Ziffernfolgen wiederholen; deswegen sollte man über erlaubte Transformationen diese Matrix nun schrittweise so verändern, dass die Ursprungsziffernfolge sowie die ausgeführten Transformationen nicht mehr nachvollziehbar sind. Erlaubte Transformationen sind z. B. das Spiegeln (vertikal, horizontal, schräg), das Rotieren, das Vertauschen ganzer Zeilen oder Spalten, sofern sie innerhalb eines Mini-Quadrates bleiben, das Vertauschen ganzer Zeilen und Spalten von Miniquadraten, oder das komplette Austauschen zweier Ziffern. Etliche dieser Transformationen hintereinander verwischen (fast) alle Hinweise auf die ursprüngliche Ziffernfolge. Von den hier vorgestellten Erstellungsmethoden ist diese die am wenigsten aufwendige aber rechenintensivste.
4. Weg: Aus einem vorhanden Sudoku durch Transformation ein „neues“ Sudoku erstellen. Mögliche Transformationen sind etwa das Drehen und Spiegeln des Brettes, die Vertauschung von Zeilen innerhalb eines Blocks oder von ganzen Blöcken, sowie das elementweise Anwenden von Permutationen.
5. Weg: Man füllt drei voneinander unabhängige Blöcke eines leeren Sudokufeldes in zufälliger Weise mit den Ziffern 1 bis 9. Damit hat man bereits 27 Vorgabewerte die ohne Prüfung eines Regelverstoßes gesetzt werden konnten. Unabhängige Blöcke sind zum Beispiel die diagonal liegenden Blöcke 1, 5 und 9 oder 3, 5 und 7, aber auch die Blöcke 2, 4 und 9 oder 1, 6 und 8 sind voneinander unabhängig. Nach dem Auffüllen der unabhängigen Blöcke werden die restlichen freien Zellen per Backtracking-Methode in zufälliger Folge gelöst.

Hier werden 5 Wege vorgestellt, wie man ein Sudoku generieren könnte.
Meine Frage an euch ist nun, welchen Weg ihr mir empfehlen würdet?

Ich freu mich schon auf eure Antworten! :toll:

Mit freundlichen Grüßen
handyplayer13

 

[Marcinek]

Also die Kompexität der verschiedenen Lösungen ist ja nicht so unterschiedlich.

Implementiere doch einfach alle oder würfel.

 

[sophismo]

Weg 5. Mit einem Hauch Weg 2 .

Weg 1 und 2 sind mehr oder minder gleich. Überleg dir einen Algorithmus, der die beiden Wege erfüllt.
Vielleicht sehe ich nicht weit genug, aber für Weg 2 scheint mir die Regelverwaltung etwas erleichtert zu sein. (im vlg mit zufälligen Zahlen, da du ja dann immer die genommene Zahl nehmen musst). Ist aber ziemlich egal, da beides Variablen sind. Weg 2 wird halt einfacher durchlaufen - im Sinne eines leichten Fehlersuchens scheint es mir simpler.
Was Permutationen sind, ist hoffentlich bekannt.
Dass solche zu erzeugen nicht die Hölle ist, ist wahrscheinlich klar, allerdings vollkommen zu behirnen, dass nur erlaubte Trafos angewandt werden ist einfach ein geistiger Aufwand, den du sonst umgehen kannst :rtfm: (Student - leichtester Weg..).
Weg 5 deshalb, weil ich mit dem beginnen würde.
Du musst (außer du bist steven hawking, oder machst das mehr als professionell das game) ohnehin eine Überprüfung machen, ob die Felder korrekt befüllt sind.
Und um nicht unnötig viel zu rechnen, kannst du einfach die unabhängigen Felder befülllen lassen, wie du willst, und dann zufällig weitermachen (mit Prüfung).

 

[Apo]

Ich persönlich finde den 5 Weg am besten. Aber das ist Geschmackssache und umsetzbar sind alle recht gut.

Ich fand es damals interessant, die eigentlichen Rätsel zu erstellen, , also beim Löschen von Zahlen. Da die Eindeutigkeit beizubehalten fand ich gar nicht so einfach. Eine "schlecht performante" Variante war es, das Rätsel nach dem Löschen einer Zahl wieder zu lösen und wenn es nur eine Möglichkeit gab, dann die nächste Zahl löschen, ansonsten Zahl wieder hinschreiben und andere Zahl löschen. Solange bis man x-Zahlen gelöscht hat.
Rekursiv hat das gut funktioniert, aber es gibt bestimmt viel schönere Varianten. =)

 

[turtle]

Den Weg-0 finde ich auch interessant. Suchen, ob das jemand schon gemacht hat und dessen Code studieren.

Hier ein Beispiel.

 

[handyplayer13]

Danke für eure Antworten!

@sophismo:
Nein, das war das erste mal, dass ich von "Permutation" gehört habe.
Ich bin 15 Jahre alt, gehe diesen September in die 10. Schulstufe und hatte bis jetzt 1 Jahr Java-Programmierung in der Schule.
Doch ich hab mich schon früher fürs Programmieren interessiert.

@turtle:
Weg-0 ist nicht so meins. Da ich wie gesagt noch ein Anfänger bin, verstehe ich die Codes von anderen auch nicht wirklich.
Da hab ich lieber die Theorie in Textform, wo ich mich durcharbeiten kann.

@all:
Ich habe nun Weg 5 genommen, um ein Sudoku zu generieren.
Das klappt auch recht gut, doch ganz selten kommt es vor, dass das Generieren zu lange braucht und sich das Programm aufhängt.
Doch ich bin froh, dass ich es überhaupt geschafft habe und belasse es mal hierbei.

Nächster Schritt wäre also ein paar Zahlen zu löschen.

Auf Wikipedia steht:

Wiederum durch „Auswürfeln“ werden je nach Schwierigkeitsgrad eine Anzahl Ziffern wieder entfernt (typischerweise so dass zwischen 22 und 36 Ziffern verbleiben). Ohne weitere Kontrolle kann es hierbei aber passieren, dass das Rätsel trivial (langweilig) oder nicht mehr eindeutig lösbar wird.

Also werde ich es bezüglich den Schwierigkeitsgraden so machen:
LEICHT - 36 Ziffern verbleiben
MITTEL - 29 Ziffern verbleiben
SCHWER - 22 Ziffern verbleiben

Wäre das realistisch?
Und dann steht, dass es ohne weitere Kontrolle passieren könnte, dass das Rätsel "langweilig" wird.
Inwiefern kann ich das überprüfen?