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

Algorithmes et structures de données Discussion :

Automatiser la réponse au Sudoku


Sujet :

Algorithmes et structures de données

  1. #81
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Essai erreur, ensuite tu peux essayer de tirer au hasard les cases exposées. Ca marche mais donne en général des grilles assez faciles.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  2. #82
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    Je dirais que tu doit avoir un algo de résolution, generer des cases aléatoirement et appliquer ton algo. Si il bloque, il genere des cases, si il reussi, il garde ta grille et tu peux etre sur qu'elle n'a qu'une solution. Par contre, la difficulté de la grille generée dependra de la puissance de l'algo de resolution qui doit, bien sur, fonctionner par logique et non par essai erreur... Je ne sait pas si je suis suffisement explicite.
    Je pense que si tu veux pouvoir generer des grilles tres difficile, tu doit deja realiser un algo de resolution capable de comparer les ensembles de possibilités de plusieurs groupes de cases (blocs+lignes,blocs+colones) et en tirer des conclusions. Pour ma part, j'ai un peut décroché ces derniers temps mais je n'ai pas encore trouvée une logique satisfesante pour cette étape.

    Ca rejoint un peut ce dont je parlait dans mon precedant post :
    Multiples solutions pour une grille :
    Je ne shaite pas que mon algorithme fasse de choix. Il ne doit donc pas etre capable de résoudre les grilles à plusieurs solutions. Mais je peux moi meme modifier la grille manuellement si elle n'est pas résolue.
    Il est facile de verifier qu'une grille n'a qu'une seule solution. Si la grille n'est pas resolue, je choisi une case pour laquelle il n'y à que peut de possibilité, fait un choix et relance mon algorithme. Si il se rend compte que la grille est invalide (certaines case n'ont plus de possibilités) c'est que ce choix n'etait pas correcte. En continuant ainssi, on peut vite verifier si une grille à une solution unique.

  3. #83
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Citation Envoyé par monstroplante
    e dirais que tu doit avoir un algo de résolution, generer des cases aléatoirement et appliquer ton algo. Si il bloque, il genere des cases, si il reussi, il garde ta grille et tu peux etre sur qu'elle n'a qu'une solution.
    C'est dans ce sens là que je parlais d'algo essais erreurs, tant que le Sudoku a plus d'une solution on rajoute une case, une fois qu'il n'a qu'une solution, on regarde si on peut évenutellement enlever des cases.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  4. #84
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    une fois qu'il n'a qu'une solution, on regarde si on peut évenutellement enlever des cases.
    Oui ca permetrait d'augmenter encore la difficulté !

    Mais je pense que ce qui est interessant a comprendre c'est que c'est la qualité de l'algo de resolution qui fera la difficulté de la grille.
    Ca permet d'alleur, en separant les algos de resolution, de choisir la difficulté de la grille generee.

  5. #85
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Citation Envoyé par monstroplante
    Mais je pense que ce qui est interessant a comprendre c'est que c'est la qualité de l'algo de resolution qui fera la difficulté de la grille.
    Ca par contre tu as tout à fait raison.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  6. #86
    Expert confirmé

    Profil pro
    Inscrit en
    Mai 2005
    Messages
    3 419
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2005
    Messages : 3 419
    Points : 4 297
    Points
    4 297
    Par défaut
    pour générer un sudoku qui n'a qu'une solution j'ajoute des
    nombres
    je remplis les quatres carrés de base placés aux quatre extrémités
    après chaque nombre placé je lance l'algo de résolution qui me donne
    les nombres que je peux placer au coup suivant
    quand mon algo de résolution a trouvé la solution je dispose d'une
    grille complète valide

    il suffit alors de travailler avec deux grilles
    je tire un nombre au hasard dans la grille résolue et je l'applique
    au problème quand mon algo de résolution a trouvé la solution le problème est complet
    la qualité du problème dépend donc de celle de l'algo de résolution
    ps ceci ne génère pas nécessairement des problèmes intéressants
    par contre cela permet de s'imprègner de tous les aspects du problème
    Elle est pas belle la vie ?

  7. #87
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Il existe une liste de toutes les grilles du Sodoku possible. On en prend une au hasard, et on supprime des points au fur et à mesure.

    Le seul pb, c'est effectivement que l'algo de résolution soit balèze - on peut même donner la complexité de la résolution en comptant le nombre d'appels à des fonctions de résolution genre assigner la seule valeur restante, assigner la seule case qui a une valeur dans un regroupement, ôter des valeurs dans un regroupement, ... -, et pour l'instant, je n'en ai pas vu capable de résoudre les 3 grilles que je fournis avec mon solveur - qu'il faudrait que je fasse évoluer un peu et qui sera aussi bientôt sur Sourceforge avec possibilité de l'essayer sous Linux et sous Windows -

  8. #88
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    Nous sommes donc tous d'accord que la difficulté réside dans le codage de l'algo de résolution.

    Pour ma part, j'ai pensé à une regle supplémentaire :
    Considerons un bloc (carré de 3x3 cases) :
    -Il peut se décomposer en 3 lignes.
    -Chaqune de ces lignes fait partie d'une ligne du tableau general.
    Imaginons maintenant qu'une possibilité ne soit presente que dans une ligne de notre bloc. Nous pouvons en déduire que cette possibilité ne peut se trouver dans le reste de la ligne du tableau general dont fait partie cette ligne du bloc.
    Inversement : On peut decomposer une ligne du tableau général en 3 morceaux de 3 cases. Si une possibilité n'est presente que dans un de ces morceaux alors, cette possibilité peut etre supprimée du reste du bloc dont fait partie ce morceau.

    On peut, bien sur, appliquer cette regle aux colones...

    Voila, c'est tout ce que j'ai trouvé pour le moment mais je me demande si il n'y a pas une regle plus generale a trouver...

  9. #89
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Ca s'appelle notre règle n°2 de Dr Topos, non ?

  10. #90
    Membre averti
    Profil pro
    Inscrit en
    Août 2005
    Messages
    417
    Détails du profil
    Informations personnelles :
    Âge : 73
    Localisation : France

    Informations forums :
    Inscription : Août 2005
    Messages : 417
    Points : 372
    Points
    372
    Par défaut
    Citation Envoyé par Miles
    Ca s'appelle notre règle n°2 de Dr Topos, non ?
    J'ai bien eu l'impression en effet qu'on était déjà passé par là. Mais je n'ai pas trop le temps de m'occuper de Sudoku en ce moment.

    Miles -> où en es-tu de ta démonstration ?

  11. #91
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    En effet ca ressemble à une de ces regles (plustot la 3).
    Je n'avait pas lu en détail...
    Petite subtilité tout de meme, na nuance suivante n'avait pas étée abordée :
    Inversement : On peut decomposer une ligne du tableau général en 3 morceaux de 3 cases. Si une possibilité n'est presente que dans un de ces morceaux alors, cette possibilité peut etre supprimée du reste du bloc dont fait partie ce morceau.
    En dehors de ca, il me semble que toutes les regles évoquées sont prises en compte par mon algo de base. Sauf, peut etre, la regle N2 mais je n'en ait pas le tps de verifier ce soir.

  12. #92
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    J'ai déjà cette subtilité dans mon programme

    Les règles seront de plus en plus difficiles, je n'ai pas encore analysé précisément quelles pourraient être les moyens de résoudre les 3 grilles très très très très difficiles, mais effectivement, je n'ai pas de démonstration que les 3 règles suffisent, ou plutôt j'ai la preuve qu'elles ne suffisent pas

  13. #93
    Expert confirmé

    Profil pro
    Inscrit en
    Mai 2005
    Messages
    3 419
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2005
    Messages : 3 419
    Points : 4 297
    Points
    4 297
    Par défaut
    la complexité maximale du problème est ici toujours égale à la sagacité du solveur
    en effet celui qui publie le problème doit proposer une solution
    unique
    c'est donc qu'il manque des règles au solveur
    Elle est pas belle la vie ?

  14. #94
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    cela dit, on peut tout de meme proceder par essai erreur.

    Je m'explique :
    On peu déterminer si une grille à une solution unique en appliquant un algo de base (elimine les possibilitées uniquement en se basant sur les case ellucidées).
    Pour ce faire, il suffit :
    -d'appliquer l'algo jusqu'a ce qu'il ne trouve plus rien a resoudre
    -On choisit une case qui à plusieurs possibilitées
    -On choisit une de ces possibilitées au hasard
    -On réapplique l'algo jusqu'a ce qu'il ne trouve plus rien a resoudre
    -On continue jusqu'a ce que l'algo démontre que la grille est invalide (un case doit se retrouver sans possibilité)
    -On peut alors elliminer la possibilité choisie au départ puisquelle conduit à une grille invalide.

    Par contre, si l'algo parvient a resoudre la grille c'est qu'il n'y a qu'une seule possibilité suite au choix que nous avons fait. Il faut alors vérifier si un autre choix pour la meme case de départ aurait pu donner une solution...
    J'espere que cette explication est suffisement comprehensible (elle meriterait d'hetre mieu developpée).

    Du coup, puisque nous disposons d'un alogo qui est capable de determiner pour n'importe quelle grille si elle a une et une seule solution, nous sommes aussi en mesure de generer des grilles d'une difficultée maximum...

  15. #95
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    C'est la bifurcation, mais je ne trouve pas ça une super approche

  16. #96
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    Je suis d'accord mais c la seulle que nous ayons pour le moment qui soit capable de generer des grilles d'une difficulté sans limite.
    Je ne considere pas pour autant qu'il soit ininteressant de trouver une methode plus élégante.
    Il me semble simplement que cette solution devait etre évoquée.

  17. #97
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Mouais... Le problème avec la bifurcation, c'est qu'il faut tester les autres possibilités afin de n'avoir qu'une seule solution.

  18. #98
    Membre régulier Avatar de monstroplante
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    107
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2004
    Messages : 107
    Points : 76
    Points
    76
    Par défaut
    En fait, pour etre plus precis, on ne test que des arbres de possibilité. à chaque fois que l'algo de resolution bloque, on cree un nouvel arbre. Donc plus l'algo de resolution est efficace et moin on aura d'arbre de possibilité à verifier.

  19. #99
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Points : 2 227
    Points
    2 227
    Par défaut
    Deux questions :

    Combien existe-t-il de grilles complètes valides au Sudoku ?
    Combien existe-t-il de grilles incomplètes donnant une et une seule solution ?
    J'affirme péremptoirement que toute affirmation péremptoire est fausse
    5ième élément : barde-prince des figures de style, duc de la synecdoque
    Je ne réponds jamais aux questions techniques par MP

  20. #100
    Expert confirmé

    Profil pro
    Inscrit en
    Mai 2005
    Messages
    3 419
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2005
    Messages : 3 419
    Points : 4 297
    Points
    4 297
    Par défaut
    en fait pour la bifurcation il faut partir à l'envers
    j'ai une grille avec n chiffres placés qui conduit à une solution valide
    j'ai la grille précédente avec n-1 chiffre placés qui diffère de n par la résolution d'un bigramme sur le solveur
    si je propose la grille n-1
    le solveur va s'arrêter en n-1 si j'inhibe la bifurcation
    en testant les deux chiffres du bigramme je vais arriver
    soit à une solution non valide (non respect des contraintes)
    soit à la solution valide
    partant de n-1 je peux remonter en n-2 éventuellement 4 solutions possibles

    c'est encore dire que solveur et générateur sont toujours de même niveau
    Elle est pas belle la vie ?

Discussions similaires

  1. [XL-2010] Automatiser réponse dans une cellule
    Par tintin69 dans le forum Macros et VBA Excel
    Réponses: 3
    Dernier message: 30/04/2015, 11h56
  2. Comment recevoir rapidement une réponse à votre question ?
    Par Community Management dans le forum Windows
    Réponses: 3
    Dernier message: 17/08/2014, 03h28
  3. [XL-2007] automatisation d'une réponse à un message
    Par skipeemed dans le forum Macros et VBA Excel
    Réponses: 13
    Dernier message: 16/10/2010, 11h28
  4. Macro VBA : automatiser la réponse à une question.
    Par monf29 dans le forum Macros et VBA Excel
    Réponses: 3
    Dernier message: 04/06/2007, 12h18
  5. réponse ds la meme page
    Par autumn319 dans le forum ASP
    Réponses: 13
    Dernier message: 03/09/2003, 19h02

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