Version imprimable
Bonjour,
je fais un projet à la fac sur le sudoku que j'ai quasiment terminé. Je voudrais l'améliorer en y ajoutant un compteur de solutions. Au moins savoir s'il y a plus d'une solution. Est-ce que quelqu'un pourrait m'aider, juste me doner une piste si posible.
Merci d'avance,
Spane :D
Ton algo de recherche va (j'imagine) tenter d'appliquer des patterns connus qui permettent de restreindre l'ensemble valeurs possibles sur chaque case.
De temps à autres, aucun de ces patterns ne sera applicable et il te faudra faire des choix.
Chaque choix est réalisé au niveau d'un noeud ("de décision" ?), chacun des choix correspond à une branche d'un arbre de recherche. La recherche sera très certainement en profondeur-d'abord.
Le tout est de ne pas s'arréter quand tu as trouvé une solution, mais de remonter tranquillement jusqu'au noeud précédent où il reste des branches à explorer. Et à chaque fois que tu trouves une solution valide ... => +=1 (stocker chaque solution dans un vecteur t'incrémentera implicitement le nombre de solutions)
Bref, c'est de l'algorithmie, et cela n'a pas grand chose à faire sur ce forum.
J'avais croisé un excellent forum (phpbb) anglophone sur le sujet des sodokus.
Et pour faire semblant de revenir dans le thême du forum, j'avais vu que un des gens d'ASL y avait fait de la pub pour Adam, qu'il avait utilisé avec succès pour résoudre des sudokus -- vous comprennez pourquoi une bibliothèque permettant de faire des IHMs à vocation portable, et en C++ moderne m'intrigue autant.