Discussion :

[benji1801]

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.

[jeroman]

Je pense que tu aurais plus de chances dans le forum "Algorithmes".

[Pouet_forever]

Ca ne dépend pas que de ton algo, ça dépend de la manière dont tu as fait ton algo et de la grille.
Je dis une bêtise, mais c'est pour schématiser : si ton backtrack est fait pour résoudre ton sudoku pour 1,2,3,4...9 et que la grille doit se résoudre dans l'autre sens (9,8...1) ton algo va passer beaucoup plus de temps à le résoudre.

Le but pour que ton algo soit plus rapide est de prendre le nombre qui aura le moins de possibilités pour 'casser' le backtracking au plus vite et explorer le moins de cases possible.
Tu peux aussi avoir un compteur 'général' qui compte le nombre de 'nombres' restant sur la grille et jouer en fonction de ça.