Générateur de Sudoku aléatoire

Je veux générer un Sudoku complètement aléatoire .

Définissez une grille Sudoku comme une grille d'entiers entre et où certains éléments peuvent être omis. Une grille est un casse-tête valide s'il existe un moyen unique de le compléter pour correspondre aux contraintes de Sudoku (chaque ligne, colonne et aligné carré n'a pas d'élément répété) et il est minimal à cet égard (c'est-à-dire si vous omettez plus élément du puzzle a plusieurs solutions).$9\times9$$1$$9$$3\times3$

Comment puis-je générer un puzzle Sudoku aléatoire, de sorte que tous les puzzles Sudoku soient équiprobables?

Générer la distribution uniforme exacte de tous les puzzles sudoku peut être fait de cette façon: vous pouvez simplement générer au hasard une grille 9x9 et la conserver uniquement s'il s'agit d'une grille sudoku correcte, sinon réessayez.

Cette approche par force brute vous garantit une distribution uniforme mais n'est clairement pas efficace, car vous ne pouvez multiplier la probabilité que la grille soit correcte par qu'en générant une grille aléatoire 8x8, puis remplir les deux lignes restantes. Il s'agit toujours d'une distribution aléatoire, mais toujours beaucoup trop inefficace.$9^{17}$

Vous pouvez également forcer la première ligne à , puis générer aléatoirement le reste de la grille, puis choisir aléatoirement une permutation de tous les chiffres. Vous choisirez toujours toutes les grilles avec la même probabilité mais 9 ! plus rapide.$[1, 2, .. 9]$$9!$

Peut-être voyez-vous où je vais: répondre à ce problème de manière intelligente vous amènera probablement à vous interroger sur les symétries sous-jacentes des grilles de sudoku. Beaucoup de travail a été fait dans ce sens pour prouver que 17 est le nombre minimal d'indices pour un sudoku ( voir cet article ) et vous pouvez aller ici pour voir cette énumération précise de 5 472 730 538 classes de 3 359 232 grilles similaires, qui utilise ces symétries:

1. Permutations de chiffres
2. Permutations de rangées (les bandes et les rangées à l'intérieur de chaque bande)
3. Même chose pour les colonnes
4. Transposition

Avec ce cadre, vous pouvez choisir au hasard l'une des 5 472 730 538 classes (elles peuvent en fait être compressées en 6 Go), puis choisir l'un des représentants pour chaque symétrie, respectivement un sur .$9!, 6^4, 6^4, 2$

EDIT: pour l'adapter à des puzzles incomplets, vous pouvez choisir au hasard un sous-ensemble de votre grille, vérifier si la solution est unique avec un solveur sudoku et réessayer sinon. Ce n'est pas une distribution uniforme car le nombre de puzzles incomplets avec une solution unique peut être différent pour deux grilles. (Je serais très surpris sinon)