Répondre à la discussion
Affichage des résultats 1 à 18 sur 18

Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!



  1. #1
    jubano

    Question Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Le Sudoku vous connaissez? Comment peut-on résoudre une grille mathématiquement parlant???

    -----


  2. Publicité
  3. #2
    n0unours

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Je dirais avec un peu de refléxion, un crayon, un bon fauteuil

    Après, il existe surement un algorithme permettant de générer les grilles, mais de là à ce qu'il y en éxiste un pour les résoudre, je ne sais pas.

  4. #3
    chung

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Il n'y a pas (encore!) d'algorithme permettant de résoudre les grilles de sudoku...
    Pour l'anecdote, j'ai entendu parler de l'existence d'une prime d'un million (euros? dollars?) qui reviendrait à celui ou celle qui en mettrait un sur pied.

  5. #4
    pat7111

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Je pense qu'il est beaucoup plus facile de programmer en n'importe quoi la résolution que la création des grilles.

    Pour la résolution, on fait le compte des nombres "possibles" dans chaque case, des "nécessaires" dans les lignes/colonnes/carrés. Quand on est bloqué, un petit coup de récursivité pour tester une hypothèse qui aboutit à la solution ou à une contradiction... c'est pas insurmontable... ni passionnant d'ailleurs...
    Plutôt appliquer son intelligence à des conneries que sa connerie à des choses intelligentes...

  6. #5
    matthias

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Citation Envoyé par chung
    Il n'y a pas (encore!) d'algorithme permettant de résoudre les grilles de sudoku...
    D'algorithme très efficace peut-être (et encore). Mais sinon c'est très facile d'envisager l'algorithme le plus bête et méchant qui soit: tester toutes les possibilités qui sont en nombre fini. C'est un algorithme idiot et inapplicable, mais c'est un algorithme.

  7. A voir en vidéo sur Futura
  8. #6
    Romain-des-Bois

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    l'algorithme pour créer les grilles existe à mon avis : il y a des logiciels de "création de grilles".

    ou alors, ce sont des grilles déjà faites.

    si on sait faire un prog pour résoudre un sudoku, on sait fabriquer une grille.
    par exemple, en 9x9, on fait réaliser une grille complète à l'ordinateur aléatoirement (ça doit pas être trop dur), puis on lui fait enlever un nombre au hasard, l'ordinateur résoud le sudoku. S'il peut le résoudre, il enlève à nouveau un nombre, sinon, il s'arrête. Et ainsi de suite. Au final, la grille comportera le nombre minimum d'informations pour que l'ordi le résolve.

  9. Publicité
  10. #7
    pat7111

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Citation Envoyé par Romain29
    l'algorithme pour créer les grilles existe à mon avis : il y a des logiciels de "création de grilles".
    Je suis d'accord, puisqu'il y a des grilles à foison et qu'on ne s'imagine pas qu'elles ont été laborieusement élaborées à la main.

    Quant à la résolution, il suffit de résoudre une demi douzaine de grilles pour se convaincre que le raisonnemment est tellement mécanique qu'une machine le ferait très bien. Seul le fameux mais sans doute illusoire million, qu'il s'agisse d'euros, de dollars ou même seulement de caramels mous, mériterait qu'on se donne la peine de coder cela.

    Sur ce, bon réveillon et bonne année à tous
    Plutôt appliquer son intelligence à des conneries que sa connerie à des choses intelligentes...

  11. #8
    cricri

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    suis en train de le coder
    pour l instant il resou sans probleme les grilles simple
    les plus dure j ai des truc a rajouter

  12. #9
    Pole

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    J'ai trouvé un programme en C++ qui résoud la grille que l'on lui donne. Donc, la prime 1 million de .... je ne vois pas à qui on peut la donner, car, plein de programmeurs on déjà écrits des algorithmes qui marchent (celui que j'ai testé met moins d'une seconde).

    Le plus interressant, c'est quand même de faire des grilles à la main et d'inventer des méthodes qui les résoud SANS récursivité.

    Bonne fin d'année. (avec peut-être des grilles de Su Doku)
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  13. #10
    xalbin.du.29

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    En tout cas la meilleur méthode c'est de prendre prendre son crayon et c'est parti pour un bon moment de réflexion (ça rime !!!! )

    J'allais oublié BONNE ANNÉE 2006 !!!!!!
    Rien ne se perd, rien ne se crée, tout se transforme.

  14. #11
    Narduccio

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Ayant récemment vu un accros résoudre de manière quasi-automatique des grilles difficiles, je me demande s'il n'y a pas des schémas relativement simple et que notre cerveau pourrait apprendre à force d'apprentissage.
    EN fait, la question que je me pose c'est combien y-a-t-il de variantes possibles dans le remplissage des grilles. Mais en tenant compte des répétabilités dans les schémas.
    Ainsi, si l'on prend des nombres a, b, c, d, e, f, g, h, et i, dans lequel a peut représenter n'importe lequel des 9 chiffres usuellement utilisés, b l'un des 8 autres chiffres et ainsi de suite. Le nombre de combinaisons possibles est-il si grand que cela ?
    "Une théorie n'est scientifique que si elle est réfutable". Karl Popper

  15. #12
    cricri

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    mon programme ne fait pas du recursif il agit comme un humain il y a toujours ( a premier vu ) des cases ou un seul chiffre rentre
    ( en tous ca pour les grilles simple a dure )
    pour les plus hyper dure faut que j amelliore

  16. Publicité
  17. #13
    ExtatiK Design

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Pour ceux qui aiment les récréations combinatoires, un petit site sympa:
    http://www.recreomath.qc.ca/dict_combinatoire_recre.htm
    Surement déjà donné sur le Forum, mais c'est pas grave...
    "Have a ball, and get involved" - Beastie Boys.

  18. #14
    Pole

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Pour ceux qui veulent le programme de résolution de Su Doku, faites une rechercher sur ce site : www.cppfrance.com.
    Si vous le voulez dans d'autres langages, regardez à gauche dans la section " Autres langages ".

    Bonne année!
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  19. #15
    sylvainix

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Bonjour,
    l'article de wikipedia est tres complet et établit le nombre de grilles possibles a 6.67*10^27.
    http://fr.wikipedia.org/wiki/Sudoku

  20. #16
    gregcrv

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Et pour les algorithme de génération de sudoku quelqu'un a une idée ?? Les deux principales difficultées etant : la solution doit etre unique , et pouvoir donner un niveau de difficulté au sudoku généré.
    -- Zebac --

  21. #17
    Pole

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Citation Envoyé par gregcrv
    Et pour les algorithme de génération de sudoku quelqu'un a une idée ?? Les deux principales difficultées etant : la solution doit etre unique , et pouvoir donner un niveau de difficulté au sudoku généré.
    Tu peux construire une grille avec tout les chiffres, puis tu en enlèves 1, tu résoud la grille, s'il y a plus d'une solution, tu affiches l'ancienne grille si c'est de la bonne complexité (la complexité doit être évaluée dans la résolution) sinon tu recommences au début.

    Tu peux faire dans l'autre sens : partir d'une grille vide et rajouter des chiffres.

    A+.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  22. #18
    pat7111

    Re : Vous connaissez le Sudoku? A la recherche de l'algorythme du Sudoku!!!

    Citation Envoyé par Pole
    Tu peux construire une grille avec tout les chiffres
    Il me semble que c'est là la principale difficulté et autant la résolution d'un problème donné ne me parait poser aucun problème algorithmique, la méthode de génération d'une grille complète ne saute pas aux yeux.
    A partir d'un certain nombre de chiffres placés, la solution devenant unique, si on continue à en rajouter au hasard, il n'y en a plus du tout...

    Je pense qu'on devrait y arriver en supposant disposer d'un algo de résolution qui ne postule pas l'unicité de la solution.
    A partir d'un début de grille, on construit l'arbre des solutions possibles. On devrait alors pouvoir créer toute une série de problèmes d'un coup et on verrait à partir de quel stade la solution est devenue unique.

    Dans l'absolu, en partant d'une grille complètement vide, on fabriquerait d'un coup tous les problèmes possibles mais il faut certainement restreindre l'espace des solutions pour obtenir quelque chose en un temps raisonnable
    Plutôt appliquer son intelligence à des conneries que sa connerie à des choses intelligentes...

  23. Publicité

Sur le même thème :

Discussions similaires

  1. Sudoku
    Par rapporteur dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 06/02/2009, 02h45
  2. Les challenges du Sudoku
    Par Argyre dans le forum Science ludique : la science en s'amusant
    Réponses: 5
    Dernier message: 16/11/2006, 08h43
  3. Cherche SVP une solution à un jeu Sudoku
    Par roro123 dans le forum Science ludique : la science en s'amusant
    Réponses: 4
    Dernier message: 24/07/2006, 10h01
  4. Sudoku
    Par pruno_d_agen dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 27/06/2006, 11h56
  5. sudoku & dénombrement
    Par fderwelt dans le forum Mathématiques du supérieur
    Réponses: 19
    Dernier message: 22/02/2006, 16h03