Sudoku

Bonjour tout le monde!
Quelqu'un aurait-il la gentilesse de m'expliquer les différentes manières de résoudre un sudoku d'un point de vue scientifiques s'il vous plait? ( wikipédia est plutôt moyen pour ce sujet :/)
Ex : comment calculer le nombre de grille possible ou de solution pour une grille? Existe-il des théorèmes mathématiques pour résoudre un sudoku? etc etc

merci d'avance :D

( Niveau 1ère S, recherche dans le cadre d'un TPE)

Bonjour, pour que l'aide soit appropriée il faudrait que tu nous précises ton niveau en maths ?

Eh bien je suis en 1ère S, c'est une recherche dans le cadre de mon TPE.

Il est comique ^^
En tout cas l'algo de résolution je l'ai cherché en prépa et j'ai pas aboutis (okay j'avais pas que ça à faire faut dire)....
TPE maths ?

Stu veux j'ai fait un programme qui résoud ton sudoku en 1 millieme de seconde ;) Par contre c'est de la brute force...

Moi mon algo de résolution favori c'est de regarder dans ma table des (environ) 6.67*10^21 sudokus possibles et de trouver la grille qui convient.

Le problème plus général (compléter un sudoku de taille quelconque) étant NP-complet, il n'y a pas de stratégie polynomiale connue.

Pour le sudoku 9*9, il existe un jeu de règles déterministes à appliquer qui permette de tout résoudre, mais en augmentant la taille on perdra la complétude au bout d'un moment. Toujours.

:marteau: heuuu je savais pas que c'était aussi complexe.. pour le nombre de grille possible pourriez vous juste m'expliquez comment vous trouvez le nombre de grille possible, et en ce qui concerne les théorèmes un lien où je pourrais les étudier plus ou moins superficiellement? enfin je veux dire histoire de connaître un minimum

lapras a écrit:Stu veux j'ai fait un programme qui résoud ton sudoku en 1 millieme de seconde Par contre c'est de la brute force...

+1.

On peut améliorer un peu la force brute par quelques considérations mais ça ne va pas chercher très loin...
(C'était un de mes premiers DM d'info en sup !)

Perso j'ai fait ca avec de la récursivité, c'est puissant comme principe.

Certes mais c'est lourd...
La récursivité sur un sudoku ça entraîne une floppée d'empilement et de dépilement et donc faut réserver une bonne partie de mémoire parce que appel de fonction en continue comme ça c'est pas excellent.

Y'a longtemps j'ai fait un solveur en caml mais avec un style horrible et complètement illisible qui implémentait quelques stratégies de bases, et puis de toutes façons, pour ce genre de trucs, c'est utiliser prolog qu'est le plus facile.

heuuu...je peux mettre ça dans le tpe ou... trop élevé pour un niveau 1ère?

bah trouver un algo ou une façon de résoudre un sudoku niveau 1ère... a part réfléchir puis le faire traditionnellement il n'y a rien donc il faudrait que tu regarde un peu avec ta prof de maths ce qui est envisageable pour toi

guigui51250 a écrit:bah trouver un algo ou une façon de résoudre un sudoku niveau 1ère... a part réfléchir puis le faire traditionnellement il n'y a rien

Ce n'est pas parce que tu n'as pas cherché d'algo qu'il faut dire de suite qu'il n'y a rien !!!
1) il faut considérer chaque ligne, chaque colonne, chaque carré 3x3 comme une zone (au sens algorithmique du terme). Bien entendu, chaque zone est reliée à toutes les autres puisque les lignes et colonnes et carrés se croisent en tous sens
2) pour chaque position de la zone (donc de chaque ligne, de chaque colonne, de chaque carré), tu regardes quels sont les chiffres qui y vont de 1 à 9 => si un seul chiffre est possible dans la case (parce que tous les autres sont en double dans une des zones associées), c'est le bon alors tu le places
3) tu prends ensuite chaque chiffre de 1 à 9 et tu regardes à quel endroit de la ligne tu peux le placer. S'il ne se place qu'à un seul endroit possible, alors c'est le bon donc tu le places. Tu fais de même pour chaque case de la colonne et chaque case du carré
4) si les phases 2 et 3 ont engendrées une modif, tu recommences alors à 2 sinon c'est qu'on ne peut plus le résoudre de façon algorithmique simple donc faut passer, comme l'a dit Lapras, en brute force

brute force: algorithme récursif => tu prends la première des cases restantes et tu y places un chiffre parmi tous les chiffres restants (en vérifiant qu'il est autorisé) puis tu ré appelles l'algorithme pour les cases vides restantes
=> si plus aucun des chiffres ne peut être placé alors que la case est vide, c'est qu'un des chiffres en amont est mauvais => tu arrètes l'algo à ce niveau et tu remontes au niveau précédent où tu places un autre des chiffres possibles => etc etc
=> s'il n'y a plus de case vide, c'est que le sudoku est résolu.

Bonne année à tous.

Si je peux me permettre ce coup de pub (si vous avez du temps à perdre) http://www.sudoku-factory.com/forumsudoku/viewtopic.php?t=443

J'aurais voulu généraliser cette technique (qui mathématiquement est finalement simple quand on a compris de quoi on parle) mais je n'ai jamais eu le courage.