Se connecter / S'enregistrer
Votre question

Sudoku : choix du backtracking

Tags :
  • Programme
  • Programmation
Dernière réponse : dans Programmation
31 Octobre 2011 15:23:11

Bonjour,

Je suis en train de travailler sur un projet de programmation C, je dois fais un générateur/solveur de grilles Sudoku.

Tout fonctionne comme il faut, sauf que j'aurai besoin d'aide pour une petite preuve..

Mon algo de backtracking choisit d'abord le chiffre le plus petit : par exemple, s'il y a 3,5,6,7 comme possibilités, il essaye 3, puis 5, puis 6, puis 7...

Pour que ma génération de grilles soit plus aléatoire, j'ai pensé à changer les choix du backtracking. Au lieu de choisir le chiffre le plus petit, il fait un choix "aléatoire" parmi les possibilités.

Bien sûr le programme va résoudre la grille, mais le temps d'exécution va varier : des grilles seront résolues plus vite avec le 1er algo, d'autres seront résolues plus vite avec le choix aléatoire...

Comment justifier que ces deux algorithmes sont équivalents..? Qu'il y en a pas un plus rapide que l'autre en général ?

Merci.

Cordialement.

Autres pages sur : sudoku choix backtracking

a b L Programmation
31 Octobre 2011 19:13:59

Que tu fasses une recherche ordonnée ou non, au final, ça ne change pas le résultat. Donc, a priori, peu importe l'ordre.
Pour la résolution, tu peux chercher une heuristique dans l'ordonnancement des possibilités. Par exemple, si tu découvres qu'un critère te permet de dire qu'une possibilité est probablement (au sens mathématique) plus rapide, alors tu appliques ce critère dans l'ordonnancement des possibilité.
Attention toutefois à ce que le temps passé à la résolution du critère ne soit pas trop important vis-à-vis de la résolution.
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS