Discussion :

[piotrr]

Voilà j'essaye en vain de programmer une fonction C++ qui rempli une grille de sudoku partiellement remplie (il y a 0 dans les cases vides).
Pour cela je dispose d'un tableau 2d et 1d pour la grille ainsi qu'un tableau de sauvegarde des cases à compléter.
Je dois écrire la fonction avec le principe du backstracking seulement il apparait indispensable d'utiliser de la récursion et là dessus j'avoue que je ne suis pas très au point.
Mes questions sont les suivantes:
-Peut-on programmer la méthode du backstracking sans récursion? Si oui comment?
-Si non, quelqu'un aurait-il l'algo ou le code c++ de la fonction écrit clairement?
-Existe-t-il d'autres méthodes aussi efficaces pour compléter une grille de sudoku avec juste quelques cases de remplies?

merci beaucoup

méthode du backstracking:
http://perso.orange.fr/christophe.gu...res/sudoku.xml

[lun4t1k]

Voilà j'essaye en vain de programmer une fonction C++ qui rempli une grille de sudoku partiellement remplie (il y a 0 dans les cases vides).
Pour cela je dispose d'un tableau 2d et 1d pour la grille ainsi qu'un tableau de sauvegarde des cases à compléter.
Je dois écrire la fonction avec le principe du backstracking seulement il apparait indispensable d'utiliser de la récursion et là dessus j'avoue que je ne suis pas très au point.
Mes questions sont les suivantes:
-Peut-on programmer la méthode du backstracking sans récursion? Si oui comment?
-Si non, quelqu'un aurait-il l'algo ou le code c++ de la fonction écrit clairement?
-Existe-t-il d'autres méthodes aussi efficaces pour compléter une grille de sudoku avec juste quelques cases de remplies?

merci beaucoup

méthode du backstracking:
http://perso.orange.fr/christophe.gu...res/sudoku.xml

Deja c'est backtracking et récursivité!
J'ai programmé un sudoku qui me générait une solution unique, proposait de compter les solutions de la grille et me donner une solution (résolvait)...

Donc en fait tu veux un solver:
le backtrack c'est mettre un chiffre et continuer . si ca va pas tu reviens. le mieux c'est de backtracker.

et pour backtracker le mieux c'est du recursif!

cependant, moi je l'avais fait autrement.
tu trouveras facilement des signatures de fonctions recursives avec google.
et tu pourras aussi trouver un bon nombre incalculable de méthode pour résoudre.

mais génére, c'est plus drôle ^^

[piotrr]

Si il n'existe pas d'autre façon que la récursivité quelq'un aurait -il l'algo ou le code c++ de la fonction?

merci... (je ne trouve rien de satisfaisant sur google et cie...)

[lun4t1k]

sans parler de complexité:
- stocker les nombres présents sur la grille (parcourt de la matrice)
dans une pile (stack).
- tu rajoutes un chiffre sur ta grille, si il convient, tu mets dans la pile
- tu choisis une autre case vide et tu la mets dans ta pile si c'est ok.
- des que ta pile as 1 taille de 81 chiffres c'est fini.
bien entendu il faut qu'a chaque ajout de chiffre sur ta grille, le chiffre aille bien.

comme ca si tu n'as plus de possibilité pour une case donnée, tu dépiles et t'essaie un autre chiffre. c'est le principe du backtrack sans récursivité.
et tu peux stocker tes cases vides dans une pile aussi et dépiler au fur et a mesure que t'empiles.

J'ai fait un peu comme ca en plus compliqué mais le principe est là. j'ai oublié quelque chose mais quelqu'un saura le rajouter!
je ne vois que cette solution si tu veux backtracker sans du récursif.

ou sinon enregistrer chaque état d'une matrice et reprendre l'ancien a chaque fois...
apres tu optimises ton code en prenant la liste des voisins, etc...

[lun4t1k]

par contre faut modifier un peu si tu veux générer une grille avec solution unique... un peu plus compliqué encore mais faisable ^^

Et quand je dis tu met dans la pile, tu t'arranges pour trouver une structure de données la plus et la plus efficace qui soit.

si t'as un tab 1D, c'est simple tu stockes le num de la case et la valeur... enfin apres c'est un choix et ca ne fai tpas partie du détail algorithmique

[coyotte507]

si tu veux un algo (et des explications approfondies), j'ai un lien:

http://www.codeproject.com/useritems/sudoku_solver.asp

Par contre c'est en Anglais..