Combien de possiblilités

[juliengoestony]

Bonjour,
combien de possibilité un logiciel de résolution doit-il tester pour résoudre un sudoku?

[admin]

Bonjour.

Tout dépend du logiciel.
Un logiciel « performant » peut se retrouver face à quatre cas de figure :

Grille relativement facile avec une seule solution possible :
Le nombre de possibilités testées sera égale au nombre de case à trouver. Ni plus, ni moins.

Grille difficile, par exemple la « al escargot », avec une seule solution possible :
Le nombre de possibilités testées sera légèrement supérieure au nombre de cases à trouver.

Grille avec plusieurs solutions possibles, cela arrive :
Le nombre de possibilités testées sera égal ou légèrement supérieur au nombre de cases à trouver.

Grille sans solution, il faut le prévoir :
Dans ce cas le logiciel devra détecter la non possibilité d'aucune solution possible.
Le nombre de possibilités testées peut être unique ou aller jusqu'à une valeur légèrement supérieur au nombre de cases à trouver.

Le sujet mérite discussion et approfondissement, dans ce cas dans la rubrique programmation.

Cordialement.
Admin