Génerer une Grille 9*9 classique

[Fox]

Bonjour,

Je viens vous voir pour savoir quels sont les méthodes utilisées pour générer une grille de sudoku. Effectivement après plusieurs essais, j'ai pus me rendre compte que le nombre de grilles était plutôt réduit (Le nombre de grilles complètes possibles est inférieur à 9!^9 (wiki)). Il faut donc trouver des astuces...

Et là je sèche un peut

Auriez vous des idées ou des noms d'algorithmes connus?

[admin]

Bonjour.

Les conseils ci-dessous traiterons des concepts mais ne discuterons pas des algorithmes ou de la programmation. Nous développerons une manière de faire. Certainement y en a t-il d'autres bien plus intéressantes ou élaborées.

Réponse : Pour générer un sudoku il vous faut tout d'abord créer une grille complète et ensuite y retirer le maximum de chiffres de telle sorte que la grille incomplète obtenue n'accepte qu'une seule et unique solution. C'est tout.

Développons avec un peu de maïeutique :

Comment créer une grille complète ?
Simplement en résolvant une grille vide.
Le code proposé dans le site résout toute grille, même les vides.
http://www.top-sudoku.com/sudoku/fr/exemple-backtracking-c.php
Inconvénient, en cas résolution de grille vide, le code proposé vous donnera toujours la même solution commençant par 1, 2, 3, 4, etc...

Comment obtenir une suite de grilles complètes différentes ou plus exactement en ayant une petite probabilité d'une malchance sur 6,6 par 10 puissance 21 d'avoir deux résultats identiques à la suite ?
En vous débrouillant pour sélectionner à chaque coup à résoudre une case au hasard.

Comment sélectionner une case au hasard ?
Il y a une multitude de méthodes possibles. Mais allez au plus simple. Que diriez-vous d'un tableau fixe de coordonnées de coordonnées tirées au hasard ?...

La grille complète faite, comment retirer le maximum de chiffres de telle manière que la grille incomplète obtenue n'accepte qu'une seule et unique solution ?
Retirer au fur et à mesure des chiffres au hasard en vérifiant à chaque retrait si cette grille admet une ou plusieurs solutions.

Comment vérifier si une grille admet une ou plusieurs solution ?
Plusieurs méthodes :
° La moins esthétique et la plus longue : Résoudre plusieurs fois de suite la grille et vérifier si vous obtenez le même résultat. Bof...
° Avoir une méthode de résolution récursive qui, une fois la grille résolue, permet de revenir en arrière pour résoudre avec d'autres chiffres ; si aucune solution n'est possible avec d'autres chiffres alors la solution est unique.

Constat, conclusion et petits égarements.
On se retrouve ici dans un monde étrange ressemblant un peu à celui d'Alice au pays des merveilles de Lewis Carroll, de son vrai nom Charles Dodgson, mathématicien dont certains écrits sont des contes - et non pas des comptes - liés à la logique des mathématiques.

Ici tout est inversé. Pour créer un sudoku il vous faut tout d'abord le résoudre de rien. Ensuite la nécessité et la difficulté n'est pas tant de résoudre une grille mais de pouvoir détecter sa non résolution...

Christian.

[Julie]

Bonjour.
Merci Christian pour ces explications.
Par contre Fox a t-il bien compris le sens de 9!^9 ?

Effectivement après plusieurs essais, j'ai pus me rendre compte que le nombre de grilles était plutôt réduit (Le nombre de grilles complètes possibles est inférieur à 9!^9 (wiki)). Il faut donc trouver des astuces

9!^9 = (factorielle de 9) puissance 9 = 362 880 puissance 9 = environ 1,091106884e+50. c'est à dire un 1 suivi de 50 zéros. Je pense qu'il a de quoi faire !

Bises à tous.

[admin]

Bonjour.

Quels sont les facteurs de difficultés d'un énoncé sudoku ?

Ma réponse sera d'ordre général.
Il me semble que les facteurs de difficultés de résolution d'un sudoku sont principalement afférents aux méthodes que l'on doit utiliser pour résoudre le problème. Le nombre de case à résoudre est certes un facteur de difficulté, mais n'ai pas une finalité en soit. Le nombre de chiffre à trouver est plutôt une conséquence du nombre des méthodes utilisées. Plus il y aura de méthodes différentes de résolution utilisées plus il y aura de chance d'obtenir un nombre élevé de cases vides à résoudre.

Développons les pistes :
« on retire des chiffres tant qu'il n'y a qu'une solution à notre sudoku »
Comment faites-vous pour savoir qu'il n'y aura qu'une seule solution pour le sudoku en cours ?
En le résolvant.
Comment allez-vous le résoudre ?
En utilisant des méthodes de résolution. Plus les méthodes de résolution seront variées et complexes plus l'énoncé final abouti sera difficile.
En conséquence de quoi le niveau du sudoku à créer se fera en fonction des manières dont il sera résolu au fur et à mesure de ses résolutions successives, suite à chaque retrait d'un chiffre à une case.

Cordialement.
Admin.