Sudoku, backstracking, récursion inévitable?

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

Citation:

---

Envoyé par 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

---

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 ^^

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...)

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...

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

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..

Salut,

Ceci dit, la récursivité, malgré les apparences, ce n'est pas si compliqué que cela ;)...

Il y a quelques jours à peine, j'ai posté des explications concernant la récursivité ==>sur ce thread<==

Ca devrait t'aider à la démystifier ;)

rebonjour, si ca t'intéresses, j'avais programmé le sudoku pour un projet d'études et je viens de retrouver le rapport pour générer une grille à solution unique.
Si tu sais faire ca, tu sais solver ta grille, compter le nombre de solution etc...
regarde le fichier joint.
le langage utilisé est Maple qui se rapproche fortement du langage algorithmique. il sera facile de transcrire en c++
j'ai aussi un excellent ps qui m'a énormément servi, si tu le veux je te donnerai une adresse sur mon ftp pour le dl...
car je ne sais pas pourquoi mais ce format n'est pas autorisé à être uploadé!

Il est toujours possible de remplacer une récursivité par une itération. Par contre, il y a des algorithmes qui s'écrivent plus naturellement avec la récursivité, et la réécriture par itération peut alors être très peu claire.

et peut être plus couteuse si mal transformée

Citation:

---

Il est toujours possible de remplacer une récursivité par une itération.

---

Cela nécessite généralement la création d'une structure de données dynamique comme une pile, bien moins performante que la pile d'execution.

Citation:

---

Envoyé par JolyLoic

Il est toujours possible de remplacer une récursivité par une itération. Par contre, il y a des algorithmes qui s'écrivent plus naturellement avec la récursivité, et la réécriture par itération peut alors être très peu claire.

---

Autant il est absurde - hormis pour "la beauté du geste" ou pour leur coté didactique - de créer une fonction récursive pour calculer Xexposant N ou la factorielle de Y, autant tu risque de te casser la tete inutilement avec les boucles imbriquées pour une tour de hannoï ne contenant ne serait-ce que trois ou quatre disques, ou pour un sudoku fusse-t-il 6*6, pour obtenir une application qui ne sera en mesure que de résoudre un problème particulier (tour de hannoï à N disque ou sudoku à N cases)

La récursivité, dans ces cas là, permettra de résoudre un plus grand spectre de problème, tout en permettant malgré tout d'avoir un code franchement plus simple ;)

Sans compter sur le fait qu'il y a de fortes chances que l'algorithme itératif mette en oeuvre une gestion de ruptures assez impressionnante, et que les ruptures restent un point algorithmique rarement maîtrisé (meme si elles ne me font personnellement pas peur :P)

Citation:

---

Envoyé par loufoque

Cela nécessite généralement la création d'une structure de données dynamique comme une pile, bien moins performante que la pile d'execution.

---

Effectivement, je n'ai jamais eu l'intention de dire que c'était une chose à faire, juste que la question initiale n'avais pas vraiment d'intérêt. Les seules fois où j'ai fait ce genre de choses, c'est quand la pile d'exécution explosait, ce qui fut assez rare.

Citation:

---

Envoyé par koala01

Autant il est absurde - hormis pour "la beauté du geste" ou pour leur coté didactique - de créer une fonction récursive pour calculer Xexposant N ou la factorielle de Y, autant tu risque de te casser la tete inutilement avec les boucles imbriquées pour une tour de hannoï ne contenant ne serait-ce que trois ou quatre disques, ou pour un sudoku fusse-t-il 6*6, pour obtenir une application qui ne sera en mesure que de résoudre un problème particulier (tour de hannoï à N disque ou sudoku à N cases)

La récursivité, dans ces cas là, permettra de résoudre un plus grand spectre de problème, tout en permettant malgré tout d'avoir un code franchement plus simple ;)

---

En quoi on obtiendrait un algo moins adaptatif en itératif? C'est différent c'est tout, ce n'est jamais qu'une question de style et le programmeur consciencieux prendra soin d'utiliser le style le plus clair (ou éventuellement le plus rapide) pour résoudre ses problèmes. A l'exception peut-être de ces langages comme le scheme où on a pas le choix (pour ma part, je ne peux qualifier ces langages que de masturbation mentale).

Citation:

---

Envoyé par zais_ethael

En quoi on obtiendrait un algo moins adaptatif en itératif? C'est différent c'est tout, ce n'est jamais qu'une question de style et le programmeur consciencieux prendra soin d'utiliser le style le plus clair (ou éventuellement le plus rapide) pour résoudre ses problèmes.

---

Hé bien, essaye de créer un algorithme qui permette la résolution des tours de hannoï avec 4 disques, puis essaye de l'adapter pour le faire fonctionner avec 12...

Personnellement, avec la récursivité, qu'il doive gérer 3 disques ou 12 (avec plus, le nombre de déplacements devient à ce point important qu'on en a pour une éternité... mais il pourrait le faire) restera, à la virgule pres, exactement identique ;)... je doute que tu puisse y arriver avec une fonction itérative (mais ne demande pas mieux que de me tromper ;))

[EDIT] si tu hésites sur les règles des tours de hannoï, je suis d'accord pour te les rappeler ;)

Citation:

---

Envoyé par koala01

Hé bien, essaye de créer un algorithme qui permette la résolution des tours de hannoï avec 4 disques, puis essaye de l'adapter pour le faire fonctionner avec 12...

---

Il y a une solution iterative a ce probleme (principe: alterner deplacement du plus petit de maniere cyclique suivi du seul deplacement ne faisant pas intervenir le plus petit alors possible).

A+

--
Jean-Marc

Citation:

---

Envoyé par JolyLoic

Il est toujours possible de remplacer une récursivité par une itération.

---

Citation:

---

Cela nécessite généralement la création d'une structure de données dynamique comme une pile

---

A partir du moment où l'on a une pile, l'algorithme est récursif.

Déplacer la pile de la pile système vers le tas ne transforme pas par magie un algorithme récursif en algorithme itératif. Ce n'est que quand on n'a plus du tout de pile qu'on peut qualifier son algorithme de vraiment itératif.

Tout ce que ça change, c'est la taille maximale de la pile utilisée...

Et je ne pense pas qu'il soit possible d'utiliser du backtracking sans pile : Pour moi, c'est le principe même du backtracking...

Citation:

---

Envoyé par zais_ethael

A l'exception peut-être de ces langages comme le scheme où on a pas le choix (pour ma part, je ne peux qualifier ces langages que de masturbation mentale).

---

Après deux ans passés sur Scheme pour bien assimiler les principes de la récursivité et tout ce qui va avec, je confirme que ce langage est vraiment une *masturbation mentale* !

Citation:

---

Envoyé par "Médinoc

Et je ne pense pas qu'il soit possible d'utiliser du backtracking sans pile : Pour moi, c'est le principe même du backtracking...

---

le backtracking évoque un retour en arrière. Certes une pile modélise au mieux ce fait, premier entré, dernier sorti. on dépile et on obtient létat précédent.

mais tu peux "tricher" et sauvegarder chaque état de la matrice (pour revenir au sudoku hein!) n'utilisant pas la pile dont l'appel récursif se sert. Mais sinon le mieux pour le backtrack c'est le récursif, c'est le plus simple et ca se fait tout seul.

Donc je reprends ta phrase (tu m'autorises ? ^^)

Et je ne pense pas qu'il soit possible d'utiliser du backtracking sans récursivité : Pour moi, c'est le principe même du backtracking...

Et où le sauvegardes-tu, l'état, si ce n'est pas dans une pile ?
(qu'il s'agisse de la pile système ou d'une pile sur le tas)

Pas dans la pile d'éxecution en tout cas.
c'est dans la pile sur le tas. mais on parlait ici de la pile d'exécution. enfin il me semble!
bonne journée

Dans mon post que tu as cité, je parlais d'une pile où qu'elle soit. Même si "tricher" n'utilise pas LA pile système, ça utilise quand même une pile.

Donc, je ne t'autorise pas à reprendre ma phrase. Na! :P

Mais heu... :(
moi je parlais juste de la pile système! :lol:
allez bonne journée! et au fait il(elle) en est où le monsieur(madame) qui fait le sudoku?

Citation:

---

Envoyé par Médinoc

Et où le sauvegardes-tu, l'état, si ce n'est pas dans une pile ?

---

Tu peux vouloir stocker l'arbre complet plutôt que simplement la branche que tu es en court d'explorer. En particulier si l'"arbre" en question est un DAG et donc que tu veux profiter que AB et BA en tete, ca revient au meme.

Mais si tu ne fais plus un parcours en profondeur, je n'ai pas l'impression que c'est encore du backtracking.