Jean-François Cliche

L’«art» des sudokus, c’est aussi l’art de les coter !

SCIENCE AU QUOTIDIEN / «Une question me turlupine depuis longtemps… Je me doute bien que les grilles de sudoku sont construites par ordinateur, mais comment fait-on pour déterminer à l’avance le niveau de difficulté d’une grille ?», demande Michelle Caron, de Québec.

Il n’existe pas de manière unique, ni même universellement partagée, d’établir le niveau de difficulté d’un sudoku. Dans certains cas, celui-ci est «mesuré» simplement en comptant le nombre de cases dans lesquelles un chiffre se trouve dès le départ : plus il y a de cases déjà remplies, plus on considère que le puzzle est facile à résoudre. Il est vrai qu’en règle générale, donner plus d’indices rend la tâche plus aisée, mais s’en tenir à cela ne donne vraiment qu’une mesure très, très grossière de la complexité de la grille.

À cause de cela, plusieurs générateurs de sudokus ont mis au point des manières beaucoup plus élaborées de noter la difficulté de leurs puzzles. Les échelles et les systèmes de pointage varient d’une compagnie à l’autre mais, en en consultant quelques-uns, on se rend vite compte que les mêmes principes de base reviennent constamment — voir notamment à ce sujet le site sudokuoftheday.com ou ce texte du Britannique Andrew C. Stuart, qui fabrique lui aussi des grilles et qui a écrit des livres sur l’«art» du sudoku.

Parmi ces principes, le plus fondamental est sans doute le niveau de complexité des techniques nécessaires pour compléter la grille. La plus élémentaire est celle qui consiste à simplement se servir des cases remplies pour trouver une ou des cases vides pour lesquelles il n’existe qu’un seul chiffre possible (ou un seul «candidat», comme on le dit parfois). Un sudoku qui peut se résoudre entièrement de cette manière est évidemment très facile — et formidablement ennuyant, ajouterais-je, mais c’est une autre question.

D’autres puzzles demandent de recourir à des techniques un peu plus élaborées, comme les «doubles cachés», c’est-à-dire quand deux cases de la même ligne ou colonne ne peuvent contenir que les deux mêmes chiffres-candidats. On ignore alors lequel des deux chiffres va dans quelle case, mais le fait de savoir qu’ils occupent nécessairement ces deux cases (peu importe dans quel ordre) constitue déjà un indice de plus.

Et il existe aussi des méthodes encore plus complexes, comme la technique dite du swordfish. Grosso modo, cela survient quand un même «candidat» apparaît dans deux cases vides de trois colonnes ET de trois lignes (cela donne 6 cases en tout). Si l’on parvient à déceler ce pattern, alors on sait que ce candidat sera forcément présent dans trois de ces six cases, et nulle part ailleurs dans ces trois colonnes/lignes. Cela permet d’éliminer d’autres possibilités et de continuer de progresser.

Encore une fois, chaque «fournisseur» de sudoku va coter la difficulté de ces techniques différemment. Certains vont tenir compte du fait qu’une technique doit obligatoirement être utilisée pour se sortir d’un cul-de-sac, du nombre de fois que chaque méthode doit obligatoirement être déployée, etc. Les résultats peuvent donc varier mais, dans l’ensemble, les résultats sont approximativement compatibles.

Fait intéressant, Andrew C. Stuart est allé jusqu’à mesurer le temps pris pour compléter ses sudokus en fonction de leur difficulté (telle qu’établie par son échelle à lui). Et il semble que sa manière de mesurer la complexité d’un sudoku soit tout-à-fait valable, puisque ses grilles «faciles» prennent autour de 15 et 20 minutes à remplir, ses «moyennes» entre 19 et 28 minutes, ses «difficiles» entre 25 et 45 minutes, et ses «diaboliques» entre 35 et 50 minutes.

Autre élément à mentionner : M. Stuart a compilé ces statistiques sur plusieurs milliers de ses sudokus. Des milliers ! Et pourquoi s’est-il donné tout ce mal ? «Nous avons tous des talents différents et à différents degrés, si bien que certains puzzles vont sembler faciles aux uns et difficiles aux autres, écrivait-il en 2007 dans un texte intitulé Sudoku Creation and Grading. (…) Bien coter la difficulté d’un sudoku est la principale préoccupation de tout faiseur de puzzles. Si trop de gens sont en désaccord avec votre cote, alors vous risquez fort de perdre votre public.»

D’où l’importance, pour les gens comme lui, de faire ce qu’il faut — peu importe la somme de travail que cela représente — pour bien noter ses grilles.

* * * * *

Vous vous posez des questions sur le monde qui vous entoure ? Qu’elles concernent la physique, la biologie ou toute autre discipline, notre journaliste se fera un plaisir d’y répondre. À nos yeux, il n’existe aucune «question idiote», aucune question «trop petite» pour être intéressante ! Alors écrivez-nous à : jfcliche@lesoleil.com.