Generierung von minimalem/nicht reduzierbarem Sudokus

Question

Ein Sudoku-Puzzle ist minimal (auch irreduzibel genannt), wenn es eine einzigartige Lösung hat, aber das Entfernen einer Ziffer würde ein Puzzle mit mehreren Lösungen ergeben. Mit anderen Worten, jede Ziffer ist notwendig, um die Lösung zu bestimmen.

Ich habe einen grundlegenden Algorithmus minimal Sudokus zu generieren:

• ein fertiges Puzzle generieren.
• Besuchen Sie jede Zelle in zufälliger Reihenfolge. Für jede besuchte Zelle:
  • entfernen Zaghaft seine Ziffer
  • das Rätsel zweimal Lösen eines rekursiven Backtracking-Algorithmus verwendet wird. Ein Löser versucht die Ziffern 1-9 in umgekehrter Reihenfolge, der andere in umgekehrter Reihenfolge. In gewissem Sinne durchlaufen die Löser einen Suchbaum, der alle möglichen Konfigurationen enthält, aber von entgegengesetzten Enden her. Dies bedeutet, dass die beiden Lösungen übereinstimmen, wenn das Puzzle eine einzigartige Lösung hat.
  • Wenn das Puzzle eine einzigartige Lösung hat, entfernen Sie die Ziffer dauerhaft; Andernfalls setzen Sie ihn wieder ein.

Diese Methode garantiert ein minimales Rätsel zu produzieren, aber es ist ziemlich langsam (100 ms auf meinem Computer, einige Sekunden auf einem Smartphone). Ich möchte die Anzahl der Lösungen reduzieren, aber alle offensichtlichen Möglichkeiten, die ich mir vorstellen kann, sind falsch. Beispiel:

• Ziffern hinzufügen, anstatt sie zu entfernen. Der Vorteil davon ist, dass, da minimale Puzzlespiele mindestens 17 gefüllte Ziffern erfordern, die ersten 17 Ziffern garantiert keine einzigartige Lösung haben, was die Menge des Lösens reduziert. Da die Zellen in zufälliger Reihenfolge aufgerufen werden, werden unglücklicherweise viele unnötige Ziffern vor der einen wichtigen Ziffer hinzugefügt, die eine eindeutige Lösung "sperrt". Wenn zum Beispiel die ersten neun hinzugefügten Zellen alle in derselben Spalte sind, gibt es eine große Menge redundanter Informationen dort.
• Wenn keine andere Ziffer die aktuelle ersetzen kann, behalten Sie sie bei und lösen Sie das Rätsel nicht. Da die Überprüfung, ob ein Placement legal ist, tausendmal schneller ist als zweimaliges Lösen des Puzzles, könnte dies eine enorme Zeitersparnis bedeuten. Aber nur weil es keine andere gültige Ziffer gibt, bedeutet das nicht, dass es später nicht mehr sein wird, sobald wir andere Ziffern entfernt haben.
• Da wir die ursprüngliche Lösung erstellt haben, lösen Sie nur einmal für jede Zelle und prüfen Sie, ob sie mit dem Original übereinstimmt. Dies funktioniert nicht, da die ursprüngliche Lösung irgendwo im Suchbaum der möglichen Lösungen sein könnte. Zum Beispiel, wenn die ursprüngliche Lösung in der Nähe der "linken" Seite des Baumes ist und wir von links suchen, werden wir Lösungen auf der rechten Seite des Baumes vermissen.

Ich möchte auch den Lösungsalgorithmus selbst optimieren. Der schwierigste Teil besteht darin festzustellen, ob eine Lösung eindeutig ist. Ich kann Micro-Optimierungen wie das Erstellen einer Bitmaske für legale Placements für jede Zelle vornehmen, wie in this wonderful post beschrieben. Fortgeschrittene Algorithmen wie Dancing Links oder Simulated Annealing sind jedoch nicht dazu gedacht, die Eindeutigkeit zu bestimmen, sondern nur, um eine beliebige Lösung zu finden.

Wie kann ich meinen minimalen Sudoku-Generator optimieren?

Answer 1

Hier sind die wichtigsten Optimierungen I mit (stark angenäherten) Prozentuale Zunahme der Geschwindigkeit durchgeführt:

• Verwenden von Bitmasken zu verfolgen erfüllt sind die Zwänge (Zeile, Spalte, Kasten) in jede Zelle. Das macht es viel schneller, nachzusehen, ob ein Placement zulässig ist, aber langsamer, um ein Placement zu erstellen. Ein komplizierender Faktor beim Erzeugen von Puzzles mit Bitmasken, anstatt sie nur zu lösen, besteht darin, dass Ziffern entfernt werden müssen, was bedeutet, dass Sie die drei Arten von Beschränkungen als getrennte Bits verfolgen müssen. Eine kleine weitere Optimierung besteht darin, die Masken für jede Ziffer und jede Beschränkung in Arrays zu speichern. 40%
• Timing der Generierung und Neustart, wenn es zu lange dauert. Siehe here. Die optimale Strategie besteht darin, die Zeitüberschreitungsdauer nach jeder fehlgeschlagenen Generierung zu erhöhen, um die Wahrscheinlichkeit zu verringern, dass sie unbegrenzt weiterläuft. 30%, hauptsächlich aus der Reduzierung der Worst-Case-Laufzeiten.
• mbeckish und user295691 Vorschläge (siehe die Kommentare zum ursprünglichen Beitrag). 25%

Answer 2

Ich habe eine Idee on the 2nd option Sie war besser sein wird vorgeschlagen, für das zur Verfügung gestellt Sie 3 zusätzliche Kontrollen hinzufügen für die ersten 17 Nummern

• finden Sie eine Liste von 17 Zufallszahlen zwischen 1-9

• fügen jedes Einzelteil zufällig Stelle vorgesehen

  1. diese neue Nummer nicht hinzugefügt, um die drei grundlegenden Kriterien von Sudoku scheitern

     • Es gibt keine gleiche Zahl in derselben Zeile
     • gibt es keine gleiche Anzahl in gleicher Spalte
     • gibt es keine gleiche Anzahl in gleichen 3x3 Matrix

  2. wenn Bedingung 1, um die Verschiebung fehlschlägt nächste Spalte oder Zeile und überprüfen Sie erneut die 3 Grundkriterien.

  3. Wenn es keine nächste Zeile gibt (dh in der 9. Spalte oder der 9. Zeile) fügen Sie die 1. Spalte hinzu sobald die 17 Zeichen gefüllt sind, führen Sie die Löserlogik aus und suchen Sie nach Ihrer einzigartigen Lösung.