Comment générer des puzzles Sudoku?

J'essaie de créer un générateur de puzzle Sudoku. C'est beaucoup plus difficile que ce à quoi je m'attendais et plus j'y participe, plus c'est difficile!

Mon approche actuelle consiste à diviser le problème en 2 étapes:

1. Générez un puzzle Sudoku complet (résolu).
2. Retirez les chiffres jusqu'à ce qu'il soit résoluble et qu'il n'y ait qu'une seule solution.

À l'étape 1, puisque j'utilise une méthode de force brute, je rencontre des problèmes d'exécution. Existe-t-il un moyen optimal de remplir un puzzle Sudoku complet?

À l'étape 2, quel type d'algorithme dois-je utiliser pour "perplexer" un sudoku résolu?

J'ai un jeu Sudoku le plus vendu sur l'App Store iOS. Voici comment j'ai généré des puzzles.

J'ai d'abord une application de génération de puzzles. Mais cela ne fait pas partie du code du jeu. C'est une application autonome que j'utilise pour faire des puzzles. Il est très modifié, je peux donc le configurer pour créer différents types de motifs, niveaux de difficulté, nombre de données, etc.Générer des puzzles et obtenir un niveau de difficulté constant est difficile à faire à la volée et prend plus de temps qu'un joueur ne voudrait attendre. Donc, je génère ce que j'appelle des "puzzles de base" et c'est ce qui est utilisé par le code du jeu pour générer les puzzles auxquels les gens jouent.

Je ne réponds pas ici comment coder un générateur. Vous pouvez google et trouver des tonnes de code générateur de puzzle en ligne. Commencez par là. Mais pour faire un bon jeu, vous devez faire un bon jeu. Mon jeu ne génère pas de puzzles à la volée.

La façon dont mon application de générateur de puzzles fonctionne est qu'elle génère des milliers de puzzles par minute, mais ils ne sont pas tous bons et ne correspondent pas tous à un niveau de difficulté spécifique. Le générateur crée un casse-tête, puis le résout et calcule un niveau de difficulté, et marque le casse-tête en fonction des techniques nécessaires pour résoudre le casse-tête, et détermine si une supposition est nécessaire pour le résoudre (ce qui est généralement mauvais). Il lance des puzzles qui ne correspondent pas à un critère. Pour les puzzles difficiles mais pas impossibles, sur une machine rapide, il peut prendre une heure pour générer 100 puzzles qui correspondent à mes spécifications exactes. C'est pourquoi je ne fais pas cela dans l'application. Générer des puzzles à la volée avec ces spécifications strictes ne fonctionnerait pas pour la qualité des puzzles que j'ai dans mon application.

Les puzzles sont des chaînes, 162 caractères de long, 81 caractères avec des chiffres et des tirets ou des points où les blancs vont être, puis 81 autres avec la solution. Ensuite, des colonnes pour chacune des statistiques, comme le nombre de simples, de doubles, etc.

Ma sortie de toutes les sessions de génération sont des lignes délimitées par des virgules avec les statistiques sous forme de colonnes. Je prendrai peut-être 10 000 puzzles, les amènerai pour exceller et les trierai par difficulté. Amenez-les ensuite dans une application pour les voir sur le plateau de jeu. Je les regarde également pour leur attrait visuel et les motifs visibles du puzzle. Ensuite, je les choisis à la main.

Je les appelle des puzzles de graines et voici ce que je veux dire. Les nombres dans un jeu de sudoku ne sont vraiment que des jetons. Au lieu d'être des nombres de 1 à 9, ils pourraient être des couleurs, des symboles ou des lettres. Donc mes puzzles de graines ne sont pas des nombres, ce sont les lettres ai. Chaque puzzle de semences est changé à la volée pour en faire un puzzle jouable:

1. Randomisez les nombres / jetons. Lorsque je remets les lettres ai dans les nombres 1 à 9, la table de recherche est aléatoire. Ce qui signifie qu'un n'est pas toujours 1. Cela crée à lui seul environ 300 000 variations sur chaque puzzle.
2. Faites pivoter le puzzle de 90, 180 ou 270 degrés. Cela ajoute 4 variantes supplémentaires.
3. Basculez le puzzle horizontalement, verticalement ou les deux. Cela ajoute 4 variantes supplémentaires.

Chaque puzzle de graines peut donc créer 5 806 080 variations. Je l'ai testé sur le terrain avec de vrais joueurs. Les gens ne savent pas qu'ils jouent essentiellement le même puzzle. C'est impossible en fait. Seulement s'ils devaient remarquer que le schéma dans lequel les données se trouvent sont les mêmes à chaque fois. Mais avec même 100 graines différentes, personne ne le remarquera. Pas un million d'utilisateurs de mon jeu. Je l'ai également testé avec des applications de solveur. Une application de résolution ne résoudra pas un puzzle de la même manière lorsqu'il est tourné ou floppé. Il va même parfois l'analyser comme un niveau de difficulté différent même s'il s'agit techniquement du même casse-tête.

Cependant, Big Bad Sudoku Book propose 10 des 1000 puzzles de graines dans 5 niveaux de difficulté et plusieurs types de modèles de puzzle. Cela signifie qu'il y a des milliards de puzzles dans mon jeu. Pour chaque tranche de 10 000 puzzles, il y a 58 060 800 000 puzzles différents.

Dans Sudoku Book version 4 (prévue pour 2016), j'ai trouvé un moyen de spécifier un puzzle exact sur ces 58 milliards et d'obtenir le même puzzle sur l'appareil de chaque joueur.

À l'étape (1) Générez un puzzle Sudoku complet (résolu), puisque j'utilise une méthode de force brute, je suis confronté à des problèmes d'exécution. Existe-t-il un moyen optimal de remplir un puzzle Sudoku complet?

Il existe un moyen facile de remplir un puzzle Sudoku complet - remplissage de groupe et décalage circulaire.

1. Remplissez la première ligne avec neuf nombres différents.
2. Remplissez la deuxième ligne qui est un décalage de la première ligne de trois emplacements.
3. Remplissez la troisième ligne qui est un décalage de la deuxième ligne de trois emplacements.
4. Remplissez la quatrième ligne qui est un décalage de la troisième par une fente.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

Pour empêcher l'utilisateur de remarquer le motif évident, il peut être judicieux de randomiser l'ordre des lignes et des colonnes afin qu'il n'y ait plus de motif. Tant que les 9 numéros de chaque ligne / colonne se déplacent ensemble en une seule unité atomique, la carte Sudoku restera toujours valide.

Vous obtenez un puzzle Sudoku rempli. Pour plus de détails, vous pouvez rechercher "faire du Sudoku".

Ce n'est pas trop difficile, à condition d'avoir un solveur sudoku.

Faire des solveurs sudoku est un problème difficile / intéressant, il est donc préférable de le sauvegarder pour une autre question. Ou vous pouvez simplement lire ceci et voir comment vous allez.

1. Pour générer un puzzle résolu, exécutez simplement le solveur sur un plateau vide. La seule mise en garde est que vous devez randomiser les "suppositions" que le solveur utilise, sinon vous pourriez vous retrouver avec le même puzzle à chaque fois. Autrement dit, à un moment donné, le solveur essaiera un nombre pour une cellule; il pourrait l'essayer dans cet ordre:1, 2, 3, 4, ... et choisissez le premier qui fonctionne. Vous devez mélanger cet ordre pour qu'il essaie, par exemple, 4, 7, 2, 9, .... Ce processus doit être aussi rapide que votre solveur.
2. Pour supprimer des nombres, utilisez cet algorithme:
   • Choisissez un nombre aléatoire que vous n'avez pas essayé de supprimer auparavant
   • Supprimez le numéro, exécutez votre solveur avec la condition supplémentaire qu'il ne peut pas utiliser le numéro supprimé ici
   • Si le solveur trouve une solution, vous ne pouvez pas supprimer le nombre
   • Répétez l'opération jusqu'à ce que vous ayez supprimé suffisamment de numéros (ou que vous ne puissiez plus en supprimer)

Il s'agit d'une méthode très simple (et naïve), donc il n'y a aucune garantie que vous obtiendrez des puzzles d'une certaine difficulté - à part le nombre de numéros manquants - ou si vous pouvez même supprimer le nombre de chiffres que vous voulez. J'espère que cela aide de toute façon.

Je pense juste qu'il est intéressant de souligner cette page Web , car cela m'a beaucoup aidé pour notre développement de projet. Faire un sudoku avec une solution unique est loin d'être une tâche simple. Dans le lien, vous pouvez trouver comment l'auteur (il a vraiment fait du bon travail, ce n'est pas moi!), A trouvé plusieurs stratégies différentes. Vous pouvez avoir une idée pour générer votre propre solveur Sudoku.

Maintenant, avec le sujet, il y a aussi un moyen de générer des sudokus similaires, juste en

1. La permutation des lignes.
2. Une autre solution simple consiste à commencer par un sudoku à remplir de minimun à 17 chiffres à remplir (c'est le minimun éprouvé pour trouver une solution unique) et à remplir les différentes stratégies suivantes (par exemple, dans le lien précédent, les stratégies sont divisées en fonction des difficultés, vous peut faire quelque chose de similaire), jusqu'à ce que vous atteigniez la solution unique.
3. Il y avait une liste d'un mathématicien essayant de trouver un sudoku de solution unique à 16 chiffres de départ, avec une liste HUGEEEEEE de sudokus à 17 chiffres. Je ne me souviens pas s'il a une copie, mais je suis sûr que si vous pouvez lui proposer 17 autres solutions uniques, sudoku sera plus qu'heureux de vous laisser utiliser ses données.

Vive et bonne chance avec l'algorithme: D

Mon solveur utilise la force brute et peut trouver une solution en 20 millisecondes. En utilisant la méthode de suppression décrite ci-dessus, mon générateur produit un puzzle en moins de 200 millisecondes.

Il génère généralement un puzzle avec environ 24 à 34 chiffres restants, et je ne sais toujours pas comment dans le monde ils parviennent à produire un puzzle à 17 chiffres.