IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Sudoku, backstracking, récursion inévitable?


Sujet :

C++

  1. #1
    Membre éclairé
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    726
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2007
    Messages : 726
    Par défaut 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

  2. #2
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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 ^^

  3. #3
    Membre éclairé
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    726
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2007
    Messages : 726
    Par défaut argh...
    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...)

  4. #4
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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...

  5. #5
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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

  6. #6
    Membre Expert
    Avatar de coyotte507
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    1 327
    Détails du profil
    Informations personnelles :
    Âge : 35
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 1 327
    Par défaut
    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..

  7. #7
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  8. #8
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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é!
    Images attachées Images attachées

  9. #9
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    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.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  10. #10
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    et peut être plus couteuse si mal transformée

  11. #11
    Expert confirmé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Décembre 2003
    Messages
    3 549
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Décembre 2003
    Messages : 3 549
    Par défaut
    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.

  12. #12
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    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 )
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  13. #13
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    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.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  14. #14
    Membre émérite
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 064
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 064
    Par défaut
    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).

  15. #15
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  16. #16
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    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

  17. #17
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    Citation Envoyé par JolyLoic
    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
    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...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  18. #18
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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...

  19. #19
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    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)
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  20. #20
    Membre expérimenté Avatar de lun4t1k
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    276
    Détails du profil
    Informations personnelles :
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations forums :
    Inscription : Janvier 2007
    Messages : 276
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Invité de connexion "Adserver" sous FireFox
    Par KibitO dans le forum Administration
    Réponses: 10
    Dernier message: 13/11/2004, 14h19
  2. Eviter d'inviter tous les utilisateurs au groupe root
    Par ggnore dans le forum Administration système
    Réponses: 24
    Dernier message: 21/10/2004, 20h19
  3. [WebMacro] Les crochets s'invitent!
    Par Twofy dans le forum Développement Web en Java
    Réponses: 1
    Dernier message: 04/08/2004, 13h22
  4. Passer à l'invite d'ouverture de session...
    Par Leoxp dans le forum API, COM et SDKs
    Réponses: 2
    Dernier message: 14/12/2003, 20h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo