Je cherche à générer une grille de Sudoku resolvable avec une seule et unique solution.
J'ai déjà codé un résolveur en utilisant la brute force et le backtraking. J'ai également codé un générateur de grille complète.
Par contre quand je veux vider des cases, comment être certain qu'il n'y aura qu'une seule réponse. En cherchant sur le net, on resort toujours la même chose : A chaque case enlevée, il faut resoudre la grille et compter le nombre de résolution possible.
Le truc c'est que mon résolveur, une fois la grille résolue, ne continue pas à bosser. De plus, la grille aura beau avoir 100 solutions possibles, il affichera toujours la même solution, la première qu'il trouve. Il bosse de manière recursive, en incrémentant le chiffre à tester, de la première case à la dernière case.
Donc ma question est comment resoudre une grille en trouvant plusieurs solutions ?
- Edité par ChristopheMargarian 23 mai 2016 à 23:42:50
en gros si tu as une solution récursive à base de backtracking alors un moment donné quand tu trouves la première solution tu fais quelque chose d'équivalent à renvoyer vrai qui signale la découverte d'une solution et tu remontes tout l'arbre de recherche. Pour en trouver d'autres il «suffit» de ne pas s'arrêter.
Si tu veux compter le nombre de solutions rajoute un paramètre à l'appel qui compte. Si je comprends bien tu ne désires pas vraiment compter le nombre de solutions, mais juste t'assurer qu'il n'y en a qu'une. Du coup tu peux terminer ta recherche dès que tu en as trouvé une deuxième.
First solve the problem. Then, write the code. ~ John Johnson
Quand tu dis qula fin je remonte tout l'arbre de recherche, il faut que dans ce cas je remette toutes les cases à 0. Sinon il n'y a plus rien à tester. Et dans ce cas là, mon programme va retrouver la même solution.
De ce que j'ai compris, dans ton cas ou tu ne cherches qu'une unique solution, tu remontes, mais la ce n'est plus le cas donc tu ne remontes plus. Garde toi quelque part une variable qui, soit te stock le nombre de solution trouvées, soit un boolean qui te diras si tu as déjà trouvé une solution. Et a chaque fois que tu trouves une solution, tu update cette variable en conséquence et tu continues ta récursive (Sans revenir tout a 0).
SI tu remets toutes les cases à 0 ça te retourne la même solution ? Et bien ne les remplit pas avec des 0. Pourquoi ne pas faire en sorte de (re)partir avec ta grille comme si elle n'était pas une solution ?
Si je remets tout à 0, ça me retourne la même solution. Et si je repars avec une grille complète et que je considère que ça n'est pas une solution, ça ne marchera pas. En effet, vu que la grille est complète, chaque case n'a forcement qu'une seule valeur à prendre pour être valide.
A mon avis, je dois revoir mon algorithme de résolution et ne plus parcourir linéairement la grille et remplir chaque case avec des valeurs ordonnées aléatoirement plutôt que des valeurs qui se suivent.
Le probleme de l'aleatoire, c'est que tu as une chance de ne jamais trouver de solution sur une grille qui en a 50 ...
Mais non, admettons tu arrive en case 81 avec ta solution, tu notes que tu as une solution, tu incrémentes ton compteur, et tu repars. Ton compteur ne peut pas etre valide, donc tu vas te retrouver en case 80. Qui n'aura pas de solution valide. Ou si elle en a, c'est deja que ta grille a deux solutions. Si si, si tu tombes sur une solution et que tu continues, si ta grille n'en a qu'une tu n'en trouveras pas d'autre, s'il y en a d'autre tu les trouveras, faut pas chercher trop loin c'est ta solution.
Je déterre ce sujet après quelques années étant moi même dans la même impasse.
Je cherche en effet à vérifier l'unicité d'une grille de sudoku que mon algorithle créé, et pour cela je n'arrive pas à ajouter un compteur dans mon solveur de sudoku.
Peux-tu (ou qqn d'autre) me dire comment tu as réussi au final stp ?
Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.
Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre. En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.
Au lieu de déterrer un sujet il est préférable :
soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
soit de créer un nouveau sujet décrivant votre propre contexte
ne pas répondre à un déterrage et le signaler à la modération
Je ferme ce sujet. En cas de désaccord, me contacter par MP.
Pas d'aide concernant le code par MP, le forum est là pour ça :)
Pas d'aide concernant le code par MP, le forum est là pour ça :)