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.

[invite9ae10fb5]

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.

[invitec314d025]

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.

[A voir en vidéo sur Futura]

[inviteaeeb6d8b]

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.

[invite5c27c063]

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

[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

[invite5c27c063]

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