Discussion :

[Invité]

Sup'

Sur mon temps libre je fais un petit programme en python pour faire et resoudre des sudoku.
Je suis actuellement sur la partie generation. J'arrive a creer une grille valide avec une algo toute conne, mais la n'est pas le probleme.

Je au moment de faire les trous dans la grille. Je pensais y aller random au debut, mais apres reflexions, y a toujours moyen de rendre la grille infaisable.
Y a t'il des algos dispo ou connues? J'ai deja fais des recherche sur le net et j'ai rien trouve d'interessant.

Je joins avec le lien vers le fichier sur github pour les curieux.
Thanks!

[dourouc05]

Je au moment de faire les trous dans la grille. Je pensais y aller random au debut, mais apres reflexions, y a toujours moyen de rendre la grille infaisable.
Y a t'il des algos dispo ou connues? J'ai deja fais des recherche sur le net et j'ai rien trouve d'interessant.

Infaisable, ça m'étonnerait quand même . Par contre, la solution n'est plus forcément unique.

Une petite recherche me donne http://blog.forret.com/2006/08/a-sud...nge-generator/, qui a l'air intéressant. Tu as aussi des retours d'expérience dans http://gamedev.stackexchange.com/que...sudoku-puzzles.

Mon approche intuitive serait de baser la génération sur la résolution, avec une dose de nombres aléatoires : commencer avec une grille vide, décider arbitrairement d'une case à remplir avec un chiffre arbitraire, continuer la résolution (en fait, au lieu de faire une recherche, imposer une valeur) ; dès que tu tombes sur une grille qui remplit tes critères de qualité (nombre de cases remplies, d'itérations de filtrage ou que sais-je encore), tu la mets de côté ; une fois que tu as atteint une grille complète, celles que tu as trouvées sur le chemin menant à cette grille pourront être mises en sortie. Probablement pas très efficace.

[Invité]

Hm, je pense qu'a ce moment la, je vais passer sur le solveur, puis je l'utiliserai pour creer la grille en enlevant un random et en verifiant si la grille a une solution unique a chaque iterations.

Merci!.

[Flodelarab]

Bonjour,

si tu pars avec l'idée de faire les trous 1 par 1, il est plus optimal de choisir les trous suivants après (dans l'ordre de la grille) ceux déjà créés pour ne pas étudier un cas plusieurs fois.

[tbc92]

Voici un algorithme assez simple à mettre en place.
1. tu choisis arbitrairement 20 cases, régulièrement réparties sur la grille.
2. Tu places sur ces 20 cases des nombres au hasard... en vérifiant quand même la cohérence. ( si tu as choisi les cases A1 et A2, il ne faudra pas poser un 5 sur A1 et aussi un 5 sur A2 )
3. A partir de ces premières contraintes , tu recenses toutes les grilles compatibles. En gros, ça va donner 1000 à 2000 grilles compatibles.
Dans ce que j'ai fait pour tester, le programme qui recense toutes les grilles compatibles utilise 'activement' les 20 cases de départ. Ces 20 cases sont donc codées en dur dans le programme...
Tu as là une base pour batir 1000 grilles, et même beaucoup plus.
Pour les étapes suivantes, imaginons qu'on copie ce tableau de 1000 lignes, 81 colonnes dans Excel.
On va faire des filtres automatiques,et on va faire des filtres sur plusieurs colonnes, jusqu'à ce qu'il reste une seule ligne... et en répétant l'opération , tu peux bâtir des milliers de grilles.
Si on donne comme indices juste le strict nécessaire pour avoir une solution unique, ça donne des grilles extrêmement difficiles.

Vous allez me dire : Toutes les grilles générées vont se ressembler, on va avoir systématiquement 20 cases communes à toutes ces grilles.
Oui et Non.
Une fois qu'on a généré une grille, on peut parfaitement permuter les lignes 1 et 2, ou permuter les colonnes ABC avec DEF ... et les grilles ne se ressemblent plus du tout.

[Flodelarab]

Re,

j'ai oublié l'essentiel: puisque tu es sous GNU Linux, il existe un paquet qui crée des grilles de sudoku avec le niveau que tu veux (4, de mémoire: facile, moyen, dur, très dur). Si la plus-value de ton programme python n'est pas la création de grille, cela peut te faire gagner du temps.