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

[invite95786954]

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

[invite9b6e0fb5]

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.

[chung]

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.

[pat7111]

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

[A voir en vidéo sur Futura]

[matthias]

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.

[Romain-des-Bois]

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.

[pat7111]

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

[invitedebe236f]

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

[invite3d7be5ae]

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)

[inviteefc508ca]

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

[Narduccio]

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 ?

[invitedebe236f]

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

[invitee51aa8e9]

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

[invite3d7be5ae]

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!

[invitef60ce002]

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

[invite5a0e4f7f]

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

[invite3d7be5ae]

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

[pat7111]

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