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.

[r0d]

Bonjour,

je déterre la discussion et m'incruste dedans, parce que je me suis amusé à faire un solver (je sais pas comment dire en français) de sodoku ce matin.
J'ai fais ça en c++. La méthode de résolution est plutôt brutale, mais l'algo résous les grilles les plus difficiles en moins de temps qu'il ne faut pour afficher le résultat dans la console.
Jusqu'ici, il a résolu toutes les grilles que je lui ait donné à manger, même la fameuse ai_escargot, connue comme étant la plus difficile.

Pour les curieux, vous pouvez téléchoper le code ici: https://sourceforge.net/p/yassolver/code/HEAD/tree/
Si vous utilisez svn, voici l'adresse du dépôt directement: https://svn.code.sf.net/p/yassolver/code

Je vais maintenant m'attaquer à la génération de grille, en utilisant le solver. Mon but étant de trouver une grille encore plus difficile que la ai_escargot.

[Flodelarab]

Autant de lignes de codes pour un simple solveur de sudoku ... Tu t'es trompé.

[r0d]

Autant de lignes de codes pour un simple solveur de sudoku ... Tu t'es trompé.

J'ai essayé d'optimiser au maximum, du coup c'est pas du simple "brute force". Il y a une première passe qui calcule les nombres de façon déterministe. Du coup l'algo est un peu compliqué. C'est pour ça.

Je souhaitais optimiser beaucoup (bien qu'on puisse faire beaucoup mieux que ce que j'ai fais), parce que je veux l'utiliser pour générer des grilles. Du coup l'algo de résolution va être utilisé des millions de fois. Donc il faut que ça aille très vite.

Après, si tu penses pouvoir faire la même chose en moins de lignes de code, je suis preneur

[Flodelarab]

Tu plaisantes ? Un tableau de 81 entiers et une boucle while. Et c'est fini. Et tu fais toutes les grilles possibles.

[r0d]

Tu plaisantes ? Un tableau de 81 entiers et une boucle while. Et c'est fini. Et tu fais toutes les grilles possibles.

Comme je l'ai expliqué, j'ai choisi une méthode un peu plus fine. La méthode que tu proposes doit évaluer environ 6,67.10^21 grilles à chaque résolution. D'autant plus que ça nécessite une récursivité qui peut atteindre des profondeurs importantes pour les grilles difficiles. Donc ça peut être très lourd en terme de complexité (nombre de calculs). J'ai essayé d'éviter une telle complexité. Et je pense y être parvenu (on peut faire beaucoup, beaucoup mieux que ce que j'ai fait, mais c'est acceptable pour l'instant).
J'ai également tenté d'optimiser les recherches dans la grille, donc j'ai créé un objet dédié, avec un protocole (interface) élaboré. Finalement, je ne pense pas que cette approche objet ait apporté beaucoup, et peut-être que finalement, un simple tableau à 2 dimensions (int[9][9]) aurait suffit.
Quoi qu'il en soit, je fais ça pour m'amuser, et je me fiche bien royalement de la taille du code. L'essentiel est respecté: il est juste, hyper rapide, et je m'amuse en l'écrivant. Le reste n'a aucune importance.

[r0d]

Bon ok...
je viens de faire quelques tests, et mon code est en fait assez peu performant comparé à d'autres solutions plus simples.
Par exemple, le code ultra simple proposé par MAniiiSH sur stackoverfow (ici) est environ 100 fois plus rapide que le mien...
Il n'empêche que je me suis bien amusé à implémenter mon algo tarabiscoté

[Flodelarab]

Dans l'idéal, il faudrait faire agir le microprocesseur en assembleur. Rien de plus rapide. Et là tu ressens la puissance des 3GHz.
Malheureusement, c'est compliqué. Alors on peut programmer en C.
C'est pas mal, mais ce n'est pas orienté objet. Donc on programme en C++.

Plus tu fais simple et plus tu te rapproches de la puissance véritable de ton ordi.
Un "new" répété n'est pas cool. Car il alloue de la mémoire, et c'est long (tout est relatif). Vaut mieux un tableau fixe recyclé.
Un processus itératif vaut mieux qu'un processus récursif. (Enfin, ça, on peut en discuter)