Comment générer un tableau Sudoku avec une solution unique? Ce que je pensais était d'initialiser un tableau aléatoire puis supprimer certains chiffres. Mais ma question est comment je maintiens l'unicité d'une solution?
Voici comment mon programme SuDoKu fonctionne :
Commencez avec un tableau complet et valide (rempli de 81 chiffres).
Faites une liste de toutes les positions des 81 cellules et mélangez-la aléatoirement.
Tant que la liste n'est pas vide, prenez la prochaine position de la liste et retirez le chiffre de la cellule correspondante.
Testez l'unicité en utilisant un solveur de retour arrière rapide. Mon solveur est - en théorie - capable de compter toutes les solutions, mais pour tester l'unicité, il s'arrêtera immédiatement s'il trouve plus d'une solution.
Si le tableau actuel n'a toujours qu'une seule solution, revenez à l'étape 3) et répétez.
Si le tableau actuel a plus d'une solution, annulez la dernière suppression (étape 3), et continuez l'étape 3 avec la prochaine position de la liste.
Arrêtez quand vous avez testé toutes les 81 positions.
Cela vous donne non seulement des tableaux uniques, mais des tableaux où vous ne pouvez plus retirer de chiffres sans détruire l'unicité de la solution.
Bien sûr, ceci est seulement la deuxième moitié de l'algorithme. La première moitié consiste à trouver d'abord un tableau complet et valide (rempli aléatoirement!) Cela fonctionne de manière très similaire, mais "dans l'autre direction" :
Commencez avec un tableau vide.
Ajoutez un chiffre aléatoire dans l'une des cellules libres (la cellule est choisie au hasard, et le chiffre est choisi au hasard dans la liste des chiffres valides pour cette cellule selon les règles du SuDoKu).
Utilisez le solveur de retour arrière pour vérifier si le tableau actuel a au moins une solution valide. Si ce n'est pas le cas, annulez l'étape 2 et répétez avec un autre chiffre et une autre cellule. Notez que cette étape pourrait produire des tableaux valides complets, mais ils ne sont en aucun cas aléatoires.
Répétez jusqu'à ce que le tableau soit complètement rempli de chiffres.
Je suis un peu perplexe par (3) Utilisez le solveur pour vérifier si le tableau actuel a au moins une solution valide. Si vous n'avez ajouté qu'un seul caractère à un tableau vide (à l'étape 2) et que vous testez ensuite votre solveur dessus (à l'étape 3), vous résolvez essentiellement un tableau vide. Je ne pense pas que mon solveur soit si bon, et surtout s'il pouvait résoudre un tableau vide alors le problème d'obtenir une solution valide serait déjà résolu et je pourrais passer à l'étape 4!
@The111: résoudre un tableau vide est facile, vous pouvez le faire même sans ordinateur. Mais je recherche un tableau rempli de manière aléatoire, c'est pourquoi je ne m'arrête pas simplement après l'étape 3.
Facile :
Je doute que vous puissiez trouver une solution beaucoup plus rapide que celle-ci.
Je pense que vous avez raison, mais comment évaluer le niveau pour le tableau généré de cette manière, il semble ne pas y avoir de paramètre pour contrôler la difficulté.
Eh bien, c'est une question différente, beaucoup plus difficile. Ce qui est sûr, c'est que plus vous ajoutez de chiffres, plus c'est facile.
Vous pouvez tricher. Commencez avec un tableau de Sudoku existant qui peut être résolu puis bidouillez-le.
Vous pouvez échanger n'importe quelle rangée de trois blocs 3x3 avec une autre rangée. Vous pouvez échanger n'importe quelle colonne de trois blocs 3x3 avec une autre colonne. Au sein de chaque rangée de bloc ou de colonne de bloc, vous pouvez échanger des rangées individuelles et des colonnes individuelles. Enfin, vous pouvez permuter les chiffres de sorte qu'il y ait des chiffres différents dans les positions remplies tant que la permutation est cohérente sur tout le tableau.
Aucun de ces changements ne rendra un tableau soluble impossible à résoudre.
Mais qu'en est-il de l'unicité? comment choisissez-vous les cellules vides à garder pour que la solution soit unique?
@kvphxga: Vous commencez avec un tableau partiel ayant une solution unique. Aucun des échanges autorisés n'affecte l'unicité de la solution.
N'est-ce pas une solution horrible? Si vous utilisez un seul tableau de Sudoku complet et échangez les lignes et les colonnes, le solveur remarquera-t-il des similitudes (semblable) entre les casse-tête? Vous finissez par n'utiliser qu'un nombre incroyablement petit de solutions uniques et je crains qu'à un moment donné, cela ne semble pas aléatoire pour le solveur. Il peut être utile de faire mieux que cela.
À moins que P = NP, il n'existe pas d'algorithme en temps polynomial pour générer des problèmes de Sudoku généraux avec exactement une solution.
Dans sa thèse de maîtrise, Takayuki Yato a défini Le Problème d'Une Autre Solution (ASP), où le but est, étant donné un problème et une solution, de trouver une solution différente à ce problème ou de montrer qu'aucune n'existe. Yato a ensuite défini la complétude ASP, des problèmes pour lesquels il est difficile de trouver une autre solution, et a montré que Sudoku est ASP-complet. Comme il prouve aussi que la complétude ASP implique la difficulté NP, cela signifie que si vous permettez des tableaux de Sudoku de tailles arbitraires, il n'existe pas d'algorithme en temps polynomial pour vérifier si le puzzle que vous avez généré a une solution unique (à moins que P = NP).
Désolé de briser vos espoirs pour un algorithme rapide!
Pour être juste, vous pouvez générer quelques centaines de puzzles uniques par seconde en utilisant la technique de la réponse sélectionnée.
Eh bien, dans ce cas, j'aimerais voir cela. Parce que si vous essayez de générer un sudoku diabolique, il est parfois vraiment long de tester toutes les possibilités possibles. Pour un sudoku facile avec beaucoup de chiffres initialement remplis, je suis d'accord.
Mes espoirs pour un générateur de casse-tête Zèbre rapide ont presque disparu jusqu'à ce que je lise attentivement le début de cet article (merci !). Dans le solveur, vous devez trouver une solution (d'où le nom de solveur), alors que dans le générateur, vous devez générer le casse-tête - vous n'avez pas besoin de le résoudre réellement (le fait que la plupart des approches utilisent le solveur comme partie du générateur est une autre histoire). Je ne dis pas que votre première déclaration est fausse, je dis simplement qu'elle n'est pas prouvée dans cet article.
Il n'est pas facile de donner une solution générique. Vous devez savoir quelques choses pour générer un type spécifique de Sudoku... par exemple, vous ne pouvez pas construire un Sudoku avec plus de neuf groupes de neuf nombres vides (rangées, blocs 3x3 ou colonnes). Le nombre minimum de nombres donnés (c'est-à-dire "indices") dans un Sudoku à une seule solution est estimé à 17, mais les positions des nombres pour ce Sudoku sont très spécifiques si je ne me trompe pas. Le nombre moyen d'indices pour un Sudoku est d'environ 26, et je ne suis pas sûr mais si vous retirez des nombres d'une grille complétée jusqu'à en avoir 26 et que vous les laissez de manière symétrique, vous pouvez avoir un Sudoku valide. D'un autre côté, vous pouvez simplement retirer aléatoirement des nombres de grilles complétées et les tester avec CHECKER ou d'autres outils jusqu'à ce qu'il dise OK.
Je voudrais ajouter que le problème du nombre minimum de cellules pré-remplies nécessaires pour garantir une solution unique a, depuis cette discussion, été prouvé être 17. (Bien sûr, cela ne signifie pas que chaque plateau peut être réduit à 17 cellules : cela signifie simplement qu'il n'y a pas de plateau de Sudoku avec 16 cellules pré-remplies ayant une solution unique, et il y a au moins un plateau avec 17 cellules pré-remplies ayant une solution unique.)
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
1 votes
Écrivez un algorithme qui résout un sudoku peu importe le nombre d'indices qu'il contient, même s'il n'en a aucun. Cet algorithme vous aidera dans de nombreuses tâches futures. La chose la plus basique qu'il fera est de vous donner une variété de sudokus résolus que vous pourrez utiliser pour créer des sudokus insolubles avec l'aide d'une fonction différente qui supprimera des indices et une autre qui trouvera le nombre de solutions à chaque fois que vous en retirerez un.
0 votes
J'ai généré les 81 nombres représentant l'une des solutions possibles à un sudoku sans nombres cachés. Voir ci-dessous: ``` 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 ```
0 votes
Ensuite, j'ai fixé le résultat de la computation dans un ``cache'' en utilisant une sorte de mémoïsation et j'ai généré un tableau mélangé de 9 chiffres que j'ai utilisé pour échanger les 81 chiffres avec ceux correspondants dans ce tableau mélangé. Exemple: Tableau mélangé: 9 6 1 2 5 4 7 8 3 >> Index: 1 2 3 4 5 6 7 8 9 >> nouveau tableau de 81 chiffres: ``` 9 6 1 2 5 4 7 8 3 2 5 4 7 8 3 9 6 1 ... ```