all html : Le portail des webmaster

liste des forums liste des discussions Participer à la discussion

Message publié le mercredi 02 juillet 2008 - 11h35 par Pirz.

Bonjour,

J'essaye de faire un algorithme de résolution de Sudoku avec le backtracking mais il ne marche pas sur toutes les grilles. (Dans certains cas j'ai un dépassement de mémoire qui correspond, je pense, à une boucle infinie.) Voici mon algo :

Je cherche tout d'abord les coordonnées de tous les zéros* présents dans la grille, et je les place (les coordonnées) dans un tableau de coordonnées.

Soit un fonction back(i, val, tab) qui renvoie un Sudoku, avec
i : l'indice du zéro dont on doit trouver la valeur
val : la valeur que l'on souhaite tester pour cette case
tab : le tableau contenant les coordonnées de tous les zéros

Si la grille est complète et est valide -> je retourne le Sudoku tel quel.

Si val > 9 : je récupère la valeur actuellement testée au zéro situé à l'indice i - 1 (appellons cette valeur newVal), j'efface (= je mets à 0) la valeur du zéro actuel (à l'indice i, donc) et je retourne back(i - 1, newVal, tab).

Sinon :
Je mets la valeur val dans la case du zéro actuel, et je regarde si le Sudoku est valide avec cette nouvelle valeur.
Si oui : je retourne back(i + 1, 1, tab)
Sinon : je retourne back(i, val + 1, tab)

Voilà. Quelqu'un voit-il à quel niveau se situe le bug ?

Merci d'avance.

* je considère ici un zéro comme une case à chercher

• participer

liste des forums liste des discussions Participer à la discussion

Vous devez obligatoirement vous identifier en tant que membre pour participer à cette discussion.