Des chercheurs trouvent une formule pour résoudre tous les sudokus

Zoltan Toroczkai et Maria Ercsey-Ravasz, chercheurs en optimisation et complexité informatique à l'université de Notre-Dame, ont mis au point un algorithme mathématique déterministe résolvant tout sudoku bien plus efficacement que les méthodes classiques. Contrairement à l'approche par force brute combinée à la déduction que les amateurs utilisent, leur algorithme élimine les essais-erreurs et garantit toujours une solution exacte en temps considérablement réduit.

Au cours de leurs recherches, les scientifiques ont découvert que le temps de résolution avec leur algorithme dépend directement de la difficulté réelle de la grille, et non de sa classification subjective. Ils ont donc développé une échelle objective de 1 à 4 : une grille de niveau 2 prend 10 fois plus de temps qu'une de niveau 1. Le sudoku le plus difficile connu atteint actuellement un indice de 3,6. Les chercheurs ignorent si des grilles encore plus complexes existent.

Bien que l'application pratique aux sudokus soit limitée—le plaisir du jeu réside dans l'effort mental—les auteurs envisagent des applications bien plus larges de leur algorithme pour résoudre des problèmes d'optimisation rencontrés en industrie, informatique et biologie. Leurs travaux s'inscrivent dans l'étude plus générale des problèmes SAT (satisfiabilité booléenne).