C est exactement ce que fais mon programme
Si t es son élève ... Bonne chance
Et pour la faute ... j ai tres longuement hésité sur l orthographe mais je vais faire une maj des que possible
Votre méthode de résolution utilise les probabilités.
Il existe des algorithmes récursifs pour résoudre les sudoku de manière exacte et quelque soit la difficulté pourvu qu'il ait une solution. Voici un sujet que j'ai fait l'année dernière sur ce sujet et le corrigé Maple.
La difficulté est alors de "remplacer la récurrence" par une liste.
En fait il y a deux algos de résolution.
Le premier ( si je me trompe pas ) correspond au sujet (c'est a dire: si le chiffre qu'on cherche a mettre dans la case n'est ni dans la colonne, ni dans la ligne, et ni dans la zone de la case courante, alors c'est qu'il est bien ici ).
Le deuxième, appelé si le premier flanche car plus long et plus complexe utilise les probabilités (par exemple si le premier bloque car il y a 2 cases possibles pour un chiffre dans la zone).
Apres je n'ai peut être pas tout a fait compris ce que vous vouliez dire dans votre précédant post car je ne suis pas en MPSI mais en première et je n'ai donc pas encore vu les "récurrences".
PS: Je sais très bien qu'il existe des algo tout fait sur Internet mais mon but est d'en faire un potable tout seul a partir de techniques de resolution
Ah c'est sympa ce sujet Puro, merci!
(d'ailleurs nous on a fait un TD entier sur le coloriage de graphe si ça t'intéresse...).
Edit: le coloriage optimal d'un graphe!
Oui remplacer les appels récursifs c'est toute la difficulté, même si là ça devrait être possible, puisqu'on a un nombre d'arguments constant.
Mais au fait, c'est quoi la complexité de ton algorithme récursif?!
Elle doit être énorme non?
Tient j'ai bien envie de le tenter, d'autant que je kiffe la récursivité!
Pour la complexité je ne sais pas trop, à vue de nez je dirais qu'il y a maximum 9^81 opérations. En réalité on peut déjà en supprimer énormément avec les chiffres déjà placés.
Maple mettait 1 à 2 min pour résoudre une grille donc ça donne un ordre de grandeur acceptable pour la complexité.
Theprog a écrit : je n'ai donc pas encore vu les "récurrences"
C'est normal que tu ne comprennes pas tout, en basic il est impossible de faire des algorithmes récursifs.
Un exemple simple pour comprendre la récursivité consiste à regarder l'algorithme d'un pot de peinture. Voici le code qu'on pourrait utiliser en C :
Il faut bien avoir en tête que les variables x et y sont locales à la fonction, c'est à dire que si la fonction est ouverte plusieurs fois simultanément, x et y auront des valeurs dépendantes de la fonction considérée.
Essaye de suivre avec une feuille et un stylo le fonctionnement de cet algo. Tu comprend alors toute la difficulté de transcrire un tel algorithme en basic
C'est le même principe dans le cas du Sudoku mais la fonction est déjà plus complexe.
Theprog a écrit : PS: Je sais très bien qu'il existe des algo tout fait sur Internet mais mon but est d'en faire un potable tout seul a partir de techniques de resolution
Pour cette même raison, il n'existe pas de tel algo en basic, qui n'accepte pas la récursivité, d'où l'enjeu.
C'est bon je viens d'enfin faire marcher ma fonction de résolution récursive en Caml!
J'ai galéré je vous dis pas! J'avais pas capté un truc (stupide)...
Enfin maintenant ça marche!
Mais je confirme, c'est impossible en Basic!!!
Déjà que Caml mets genre une minute pour résoudre des grilles difficiles, et à supposer qu'on arrive à faire marcher un algo récursif en Basic, et qu'on ait assez d'espace mémoire (en rusant), je n'ose pas imaginer le temps de calcul...
Je m'y attendais un peu a vrai dire
Parce que le récursif demande a ce que j'ai compris beaucoup de variables pour stoker les valeurs x,y,nombre ... et les Matrices ne suffisent pas
J'ai compris le principe du pot de peinture. Merci Purobaz
Une question Theprog: pourquoi dis-tu que ton algorithme ne résout que les grilles faciles et moyennes?
Les difficiles il abandonne avant?
Le programme de mon prof marche à tous les coups, et est basé sur un principe probabiliste comme le tien, du coup y a-t-il une différence entre les deux algorithmes?
C'est par exemple un truc tout simple:
La grille difficile, tu vas forcement arriver a un moment où tu vas avoir dans un meme carré, 2 cases possibles pour 2 chiffres. L'algo ne peut pas décider quelle case choisir (exemple de grille joint).
Donc l'algo bloque tout simplement car il ne peut pas trancher sur quelle case est la bonne. Pour ça soit tu fait au hasard (comme tu fais je crois ) soit il faut faire des méthodes plus complexes (mais tu verras par toi meme parce que c'est chaud a expliquer )
Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd
).
)
) le generateur est HS pour le moment 
mais je vais faire une maj des que possible
