Zufälliger Sudoku-Generator

13

Ich möchte ein völlig zufälliges Sudoku generieren .

Definieren Sie ein Sudoku-Gitter als Gitter mit ganzen Zahlen zwischen und wobei einige Elemente weggelassen werden können. Ein Raster ist ein gültiges Rätsel, wenn es eine einzigartige Möglichkeit gibt, es zu vervollständigen, um die Sudoku-Bedingungen zu erfüllen (jede Zeile, Spalte und ausgerichtetes Quadrat enthält kein wiederholtes Element), und ist es minimal (dh wenn Sie nichts mehr weglassen) Element das Puzzle hat mehrere Lösungen).9×9193×3

Wie kann ich ein zufälliges Sudoku-Puzzle generieren, sodass alle Sudoku-Rätsel gleich wahrscheinlich sind?

algorithms randomness sudoku Justin
quelle
Dies sieht nach einer praktikablen Lösung aus: dryicons.com/blog/2009/08/14/…
Joe
1
Es gibt jetzt eine Meta-Frage dazu. Bitte dort oder im Chat besprechen.
Kevin

Antworten:

15

So können Sie die exakte gleichmäßige Verteilung aller Sudoku-Rätsel erstellen: Sie können ein 9x9-Raster nur zufällig generieren und dann nur beibehalten, wenn es sich um ein korrektes Sudoku-Raster handelt. Anderenfalls versuchen Sie es erneut.

Dieses Brute-Force - Ansatz garantieren Ihnen eine gleichmäßige Verteilung ist aber eindeutig nicht effizient, da Sie die Wahrscheinlichkeit des Gitters multiplizieren können richtig sein nur durch ein zufälliges 8x8 Gitter zu erzeugen und dann die restlichen zwei Linien füllen. Dies ist immer noch eine zufällige Verteilung, aber immer noch viel zu ineffizient.917

[1,2,..9]9!

Vielleicht sehen Sie, wohin ich gehe: Wenn Sie dieses Problem auf clevere Weise beantworten, werden Sie sich wahrscheinlich über die zugrunde liegenden Symmetrien von Sudoku-Gittern wundern. In dieser Richtung wurde viel Arbeit geleistet, um die Tatsache zu beweisen, dass 17 die minimale Anzahl von Hinweisen auf ein Sudoku ist ( siehe diesen Artikel ), und Sie können hier die genaue Aufzählung von 5.472.730.538 Klassen von 3.359.232 ähnlichen Gittern sehen, die diese verwenden Symmetrien:

  1. Permutationen von Ziffern
  2. Permutationen von Zeilen (die Bänder und die Zeilen in jedem Band)
  3. Gleiches gilt für Spalten
  4. Umsetzung

9!,64,64,2

BEARBEITEN: Um dies an unvollständige Rätsel anzupassen, können Sie eine Teilmenge Ihres Rasters zufällig auswählen, prüfen, ob die Lösung mit einem Sudoku-Löser eindeutig ist, und es erneut versuchen, wenn nicht. Dies ist keine gleichmäßige Verteilung, da die Anzahl der unvollständigen Rätsel mit einer eindeutigen Lösung für zwei Raster unterschiedlich sein kann. (Ich wäre sonst sehr überrascht)

jmad
quelle
Aber Justin fragt nach einer Möglichkeit, ein unvollständiges Puzzle so zu generieren, dass es eine einzigartige Möglichkeit gibt, es zu vervollständigen. Selbst wenn Sie ein 9x9-Raster generieren, das die Sudoku-Bedingungen erfüllt, ist nicht klar, warum das Entfernen einer bestimmten Teilmenge der Zellen ein Rätsel ergibt, das auf einzigartige Weise gelöst werden kann.
Janoma
1
@Janoma: oh, mein schlimmes, ich werde es bearbeiten. Aber es ist nicht sehr aussagekräftig, wenn man nicht definiert, was ein richtiges Puzzle ist. (Ist ein Gitter mit nur einer leeren Zelle ein Puzzle?). Wollen wir ein minimales Raster, dh wenn Sie eine Ziffer entfernen, ist die Lösung nicht mehr eindeutig? Das ist eine interessante Frage.
Jmad
"Einige Elemente können weggelassen werden" ist genau genug (dh "ein oder mehrere" Elemente können entfernt werden). Zum Beispiel kann ein gültiges Puzzle mit einer leeren Zelle kann in einer einzigartigen Art und Weise durchgeführt werden, während eine leere Puzzle kann nicht, da es mehr als ein gültiges Puzzle ist. Ein abgeschlossenes gültiges Rätsel kann auch auf eine eindeutige (triviale, leere) Weise abgeschlossen werden. Die Frage nach dem minimalen Raster ist ebenfalls interessant, unterscheidet sich aber von diesem.
Janoma
@Janoma, jmad: ein gültiges Rätsel ist normalerweise minimal, das habe ich vergessen zu erwähnen.
Gilles 'SO - hör auf böse zu sein'
@ Gilles Ist das eine Definition? Ich frage mich, ob dies tatsächlich die beabsichtigte Bedeutung des OP ist. Es macht das Problem viel schwieriger :-)
Janoma