C'est bon mon algorithme marche hein! (le récursif)
Effectivement la méthode de mon prof c'est de faire au hasard, mais alors... Pourquoi ne le fais-tu pas?
Si j'ai bien compris tu dresses la liste des valeurs admissibles pour chaque case et tu les rentres là où il n'y en a qu'une, et tu adaptes celles qui restent...?
Eh bien quand il bloque, hop tu tentes au hasard sur la case, à la rigueur en retenant la position de la case et la valeur que tu as rentré.
Si ça rebug, soit tu refais la même avec une autre case (tu détermines arbitrairement combien de fois tu le fais), et sinon tu reviens à la case où tu avais tenté au pif, et tu essayes avec l'admissible suivant!
Du coup ça peut facilement te débloquer sur pas mal de grille, mais il y en aura toujours qui bloqueront...
En fait ça ressemble énormément à mon propre programme récursif!
Sauf que lui il est exact car il peut faire le "test au pif" une infinité de fois!
Donc voilà c'est ce que je te conseille, de mettre un peu d'aléatoire "maîtrisé" dans ton programme. Maîtrisé au sens que tu retiens toujours la position pour pouvoir rechanger au cas où!
Pour Purobaz' si tu passes par là:
En réfléchissant à la complexité de mon algorithme de sudoku, avec un pote on s'est dit qu'il n'y avait que 9^81 possibilités maximum! Donc le nombre d'essais est borné!
Du coup j'ai dit à mon prof:
"- Monsieur j'ai fait un solveur de sudokus en O(1)!
- Ah c'est pas mal pour un problème NP-Complet..."
Basique = ta mothode est très complique
En effet il faut tout enregistrer, créer une seconde matrice, et encore une pour coordonné et valeurs ...
Donc je pense que niveau rapidité/fiabilité je suis bien
Après en add-in tout est plus facil (même si je me le suis un peu raté )
en add-in, il n'y a pas besoin de faire des optimisations de taré pour avoir quelque chose de fluide, a moins de faire un moteur 3D ou des trucs de taré, ce sera toujours hyper rapide
(c'est d'ailleurs pour ça que je trouve qu'il est plus simple de programmer en C qu'en basic )
Tsuneo: euh.......
Tu crois que ça ne fonctionne pas pour montrer que P=NP...?
Pourtant je me voyais déjà avec le million en poche... Tant pis!
Theprog: Ma méthode n'est pas très compliquée!
Tu crées une liste où tu sauvegardes les coordonnées et la valeur des chiffres que tu rentres au hasard (quand tu es bloqué), et quand tu veux revenir en arrière tu peux retrouver les valeurs que tu as entrées, les modifier et recommencer le calcul à partir d'une autre configuration!
Dommage pour le million, c'était bien essayé ! Par contre, moi aussi je pensais qu'il y avait max 9⁸¹ essais grand maximum quoi, ça parait super logique quoi... J'aimerais bien avoir une explication plus à ma portée de tout ça !
En réfléchissant à la complexité de mon algorithme de sudoku, avec un pote on s'est dit qu'il n'y avait que 9^81 possibilités maximum! Donc le nombre d'essais est borné!
Du coup j'ai dit à mon prof:
"- Monsieur j'ai fait un solveur de sudokus en O(1)!
- Ah c'est pas mal pour un problème NP-Complet..."
Pour la complexité je l'avais indiquée dans mon dernier message.
Je pense que c'est normal qu'il y ait un nombre d'essais limité puisqu'il y a un nombre fini de grille.
Je pense cependant qu'il est possible de transcrire en basic un tel algorithme, j'essayerais peut-être un jour.
Transcrire l'algorithme, oui, le faire marcher, euh...
A mon avis il ne terminera pas pour un bon nombre de grilles, étant donné qu'il met genre 2 minutes sur mon ordi en Caml, alors en Basic il faudra 1 an! Sans parler de la capacité de mémoire hallucinante que la calculette n'aura sûrement pas, ou alors il faudra ruser à mort, mais éventuellement ça se fait! (en utilisant toutes les listes!)
Au passage, oui moi aussi j'aimerais faire de la récursivité en Basic, mais j'aimerais m'atteler à un truc bien plus général,une sorte d'éditeur de programme récursif, (j'en ai déjà fait un assez rudimentaire), ou une sorte de compilateur, mais je promets rien!
Bien sûr la complexité c'est une blague! C'est exponentiel, il n'y a pas de miracle!
@Tsuneo: Pourquoi 9^81?
Regarde en binaire: avec n bits, tu as 2^n combinaisons possibles (11111=2^5).
En fait, 2^n est le nombre de 2-colorations d'un graphe à n sommets!
Donc en fait p^n est le nombre de p-colorations d'un graphe à n sommets!
("nombre de valeurs possibles" puissance "nombre de cases")
Ici on a en quelque sorte un graphe à 81 sommets (81 cases) et on considère des 9-colorations (9 "couleurs" possibles), donc 9^81 grilles possibles. Bien sûr la plupart sont incorrectes, je ne dis pas! Mais c'est bien une majoration du nombre de grilles à tester!
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 
(le récursif)
