Ich versuche einen Sudoku-Puzzle-Generator zu machen. Es ist viel schwieriger als ich erwartet hatte und je mehr ich mich damit beschäftige, desto schwieriger wird es!
Mein derzeitiger Ansatz ist es, das Problem in zwei Schritte aufzuteilen:
- Erstellen Sie ein vollständiges (gelöstes) Sudoku-Puzzle.
- Entferne Zahlen, bis sie lösbar sind und nur noch 1 Lösung haben.
Da ich in Schritt 1 eine Brute-Force-Methode verwende, treten einige Laufzeitprobleme auf. Gibt es eine optimale Möglichkeit, ein komplettes Sudoku-Puzzle auszufüllen?
Welche Art von Algorithmus sollte ich in Schritt 2 verwenden, um ein gelöstes Sudoku zu "verwirren"?
algorithm
puzzle
content-generation
user223150
quelle
quelle
Antworten:
Ich habe ein meistverkauftes Sudoku-Spiel im iOS-App-Store. So habe ich Rätsel generiert.
Zuerst habe ich eine Puzzle-Generator-Anwendung. Aber es ist nicht Teil des Spielcodes. Es ist eine eigenständige App, mit der ich Rätsel mache. Es ist stark modifiziert, so dass ich es so einstellen kann, dass verschiedene Mustertypen, Schwierigkeitsgrade, Anzahl der Givens usw. erstellt werden. Das Generieren von Rätseln und das Erzielen eines einheitlichen Schwierigkeitsgrades ist im Flug schwierig und dauert länger, als ein Spieler warten möchte. Also erstelle ich so genannte "Samen-Rätsel", und das wird vom Spielcode verwendet, um die Rätsel zu generieren, die die Leute spielen.
Ich antworte hier nicht, wie man einen Generator codiert. Sie können tonnenweise Puzzlespiel-Generator-Code online googeln und finden. Fang dort an. Aber um ein gutes Spiel zu machen, muss man ein gutes Spiel machen. Mein Spiel generiert keine Rätsel im laufenden Betrieb.
Die Art und Weise, wie meine Puzzle-Generator-App funktioniert, ist, dass sie Tausende von Puzzles pro Minute generiert, aber sie sind nicht alle gut und sie stimmen nicht mit einem bestimmten Schwierigkeitsgrad überein. Der Generator erstellt ein Puzzle, löst es und ermittelt einen Schwierigkeitsgrad. Er bewertet das Puzzle basierend auf den Techniken, die zur Lösung des Puzzles erforderlich sind, und ermittelt, ob eine Schätzung erforderlich ist, um das Puzzle zu lösen (was normalerweise schlecht ist). Es wirft alle Rätsel aus, die keinem Kriterium entsprechen. Bei harten, aber nicht unmöglichen Rätseln kann es auf einer schnellen Maschine eine Stunde dauern, bis 100 Rätsel generiert sind, die genau meinen Spezifikationen entsprechen. Deshalb mache ich das nicht in der App. Das Generieren von Rätseln im laufenden Betrieb mit diesen harten Spezifikationen würde für die Qualität der Rätsel, die ich in meiner App habe, nicht funktionieren.
Die Rätsel sind Zeichenfolgen mit einer Länge von 162 Zeichen, 81 Zeichen mit Zahlen und Strichen oder Punkten an der Stelle, an der sich die Leerzeichen befinden, und weitere 81 Zeichen mit der Lösung. Dann Spalten für jede Statistik, wie viele Einzel-, Doppel- usw.
Meine Ausgabe aller Generierungssitzungen sind durch Kommas getrennte Zeilen mit den Statistiken als Spalten. Ich nehme vielleicht 10.000 Puzzles, bringe sie ins Spiel und sortiere sie nach Schwierigkeitsgrad. Dann bring sie in eine App, um sie auf dem Spielplan zu sehen. Ich schaue sie auch an, um die visuelle Attraktivität und die sichtbaren Muster des Puzzles zu prüfen. Dann wähle ich von Hand aus.
Ich nenne sie Samenpuzzles und hier ist was ich meine. Die Zahlen in einem Sudoku-Spiel sind eigentlich nur Token. Anstatt die Zahlen 1 bis 9 zu sein, könnten sie Farben oder Symbole oder Buchstaben sein. Meine Rätsel sind also keine Zahlen, sondern die Buchstaben ai. Jedes Samen-Puzzle wird im laufenden Betrieb geändert, um ein spielbares Puzzle zu erstellen:
Jedes Samen-Puzzle kann daher 5.806.080 Variationen erzeugen. Ich habe dies im Feld mit echten Spielern getestet. Die Leute wissen nicht, dass sie im Grunde dasselbe Puzzle spielen. Das ist eigentlich unmöglich. Nur wenn sie bemerken, dass das Muster, in dem sich die Gaben befinden, jedes Mal dasselbe ist. Aber selbst mit 100 verschiedenen Samen wird es niemand bemerken. Eine Million Benutzer meines Spiels haben es nicht getan. Ich habe es auch mit Solver-Apps getestet. Eine Solver-App löst ein Puzzle nicht auf die gleiche Weise, wenn es gedreht oder gefloppt wird. Manchmal wird es sogar als ein anderer Schwierigkeitsgrad analysiert, obwohl es technisch dasselbe Rätsel ist.
Allerdings hat Big Bad Sudoku Book 10 von 1000 Puzzles in 5 Schwierigkeitsstufen und mehrere Puzzlemustertypen. Das bedeutet, dass mein Spiel Milliarden von Rätseln enthält. Pro 10.000 Rätsel gibt es 58.060.800.000 verschiedene Rätsel.
In Sudoku Book Version 4 (voraussichtlich 2016) habe ich einen Weg gefunden, um aus diesen 58 Milliarden ein genaues Puzzle zu bestimmen und auf dem Gerät jedes Spielers das gleiche Puzzle zu erhalten.
quelle
Es gibt eine einfache Möglichkeit, ein komplettes Sudoku-Puzzle auszufüllen - Gruppenfüllung und kreisförmige Verschiebung.
Um zu verhindern, dass der Benutzer das offensichtliche Muster bemerkt, ist es möglicherweise eine gute Idee, die Reihenfolge der Zeilen und Spalten so zu ändern, dass kein Muster mehr vorhanden ist. Solange sich alle 9 Zahlen in jeder Zeile / Spalte zu einer atomaren Einheit zusammen bewegen, bleibt das Sudoku-Board immer gültig.
Sie erhalten ein vollständiges Sudoku-Puzzle. Für weitere Details können Sie nach "make Sudoku" suchen.
quelle
Dies ist nicht allzu schwierig, vorausgesetzt, Sie haben einen Sudoku-Löser.
Das Erstellen von Sudoku-Lösern ist ein schwieriges / interessantes Problem. Speichern Sie es daher am besten für eine andere Frage. Oder Sie können einfach lesen dies und sehen Sie, wie Sie gehen.
1, 2, 3, 4, ...
und das erste auswählen, das funktioniert. Sie müssen diesen Befehl mischen , so dass es versucht, sagen wir,4, 7, 2, 9, ...
. Dieser Prozess sollte so schnell wie Ihr Solver sein.Dies ist eine sehr einfache (und naive) Methode, daher gibt es keine Garantie dafür, dass Sie Rätsel mit einem bestimmten Schwierigkeitsgrad erhalten - abgesehen von der Anzahl der fehlenden Zahlen - oder wenn Sie sogar die gewünschte Anzahl von Zahlen entfernen können. Hoffe das hilft trotzdem.
quelle
Ich halte es nur für interessant, auf diese Webseite hinzuweisen , da sie mir bei unserer erfolgreichen Entwicklung sehr geholfen hat. Ein Sudoku mit einer einzigartigen Lösung zu erstellen, ist keine einfache Aufgabe. Unter dem Link können Sie nachlesen, wie der Autor (er hat wirklich gute Arbeit geleistet, nein ich!) Verschiedene Strategien entwickelt hat. Sie können eine Idee haben, um Ihren eigenen Sudoku-Löser zu generieren.
Wenn wir uns dem Thema widmen, gibt es auch eine Möglichkeit, ähnliche Sudokus zu generieren
Prost und viel Glück mit dem Algorithmus: D
quelle
Mein Löser wendet rohe Gewalt an und kann innerhalb von 20 Millisekunden eine Lösung finden. Mit der oben beschriebenen Löschmethode erzeugt mein Generator innerhalb von 200 Millisekunden ein Puzzle.
Normalerweise wird ein Puzzle mit etwa 24 bis 34 verbleibenden Ziffern erstellt, und ich weiß immer noch nicht, wie es auf der Welt gelingt, ein 17-stelliges Puzzle zu erstellen.
quelle