Comment est déterminée la difficulté d'un sudoku ?

Réponse publiée sur Quora

Commençons par définir quand un sudoku est très facile. C’est quand vous pouvez toujours déterminer avec certitude une cellule, parce que soit la ligne, soit la colonne, soit le carré contient les 8 autres chiffres.

La difficulté apparaît quand vous devez faire un choix, essayer, et revenir en arrière si vous êtes bloqué pour essayer une autre possibilité. Et évidemment, plus vous avez de choix à faire et plus ils surviennent tôt, plus c’est difficile.

Le Sudoku le plus difficile du monde est celui-ci :

(Source : aisudoku via What are the criteria for determining the difficulty of Sudoku puzzle? Sur Stack Advisor)

Pour résoudre ce sudoku, vous devez faire des essais à chaque case. L’arbre à explorer est très grand, donc les algorithmes “force brute” comme celui-ci [1] mettent plusieurs secondes (ce qui est très long) à le résoudre. Pour un humain, comptez plusieurs semaines…

Formellement, le sudoku est un Problème SAT , ou ou problème de satisfaisabilité booléenne . Les programmes utilisant un “sat solver” comme celui-là [2] , basé sur pycosat sont des centaines des fois plus rapides.

Notes de bas de page

[1] Python : un petit Sudoku pour commencer - Pourquoi Comment Combien

[2] taufanardi/sudoku-sat-solver