Résoudre des sudokus les yeux fermés

Des scientifiques ont créé un algorithme capable de résoudre un sudoku tout en évaluant sa réelle difficulté.

Un sudoku est composé d’une grille carrée de neuf cases de côté, avec des sous-grilles de 3×3, à l’intérieur de laquelle certains chiffres ont été écrits. L’objectif est de remplir toutes les cases restantes avec un chiffre compris entre 1 et 9 inclus de telle sorte que chaque chiffre ne se retrouve pas plus d’une fois par ligne, colonne et diagonale. La résolution d’un problème comme le sudoku possède une complexité polynomiale. Il est donc possible de le résoudre brutalement, tout simplement en essayant toutes les combinaisons possibles. Efficace, mais peu élégant.

Dans leurs travaux publiés dans Nature Physics, Zoltan Toroczkai et Maria Ercsey-Ravasz ont mis au point un algorithme qui recherche une solution le plus efficacement possible. Pour y arriver, le programme doit analyser la structure du problème et non pas se contenter de tester la validité d’une hypothèse. L’avantage ne réside donc pas dans la possibilité de résoudre un sudoku, cela fait longtemps que de tels programmes existent, mais plutôt dans la rapidité d’établissement de la solution. En effet, tester une par une toutes les combinaisons possibles prend du temps, alors que s’attacher à comprendre le problème pour le solutionner va beaucoup plus vite. L’objectif initial des chercheurs était de tester leur programme utilisable pour les problèmes SAT (boolean satisfiability problem), dont font partie les sudokus.

Leur approche a surtout permis de classifier les différents sudokus selon leur niveau de difficulté, cette échelle comptant quatre niveaux, de facile à très difficile. Car selon eux, ce qui fait la difficulté d’une grille est le temps mis pour la résoudre. C’est précisément la quantification du niveau de difficulté d’un problème de ce type qui est au cœur de leur recherche. D’après leur échelle, il faut dix fois plus de temps pour résoudre une grille de niveau 2 qu’une grille de niveau 1.

A quand un algorithme qui prend en compte le manque de sommeil, le taux d’alcoolémie ou encore le nombre de cafés avalés ?