mardi 14 février 2017

Sudokus

Les Sudokus (prononcer soudokou) sont une invention récente, et c'est bien dommage car on aurait pu accumuler des tas de grilles intéressantes de Gauss ou d'Euler.

Quand il est bien fait, on peut vraiment apprécier la subtilité du raisonnement. A quand un sudoku au bac?

On en voit partout, généralement très faciles à résoudre : un carré 9*9, chaque case comprenant un chiffre entier de 1 à 9, avec les règles suivantes :

  • il n'y a qu'une fois le même nombre dans chaque ligne, dans chaque colonne, et dans chacune des 9 zones 3*3.
  • des cases sont affichées, et la résolution ne doit conduire qu'à une seule solution. 
Un sudoku ne doit donc pas conduire à 2 solutions possibles. Pour cela, on a montré qu'il fallait donner au moins 17 des 81 cases possibles. En voilà un à 17 clés :


Un nombre minimal de clés n'est pas nécessairement un indice de difficulté. On a trouvé un sudoku qualifié de "plus difficile du monde", c'est AI l'escargot, essayez pour voir :

Il y a  9! × 722 × 27 × 27,704,267,971 = 6,670,903,752,021,072,936,960 sudokus différents, mais puisque par permutations des chiffres, des lignes, des colonnes, par rotation, symétrie, etc, il n'y en a que 5,472,730,538 qui soient vraiment différents : plus de 5 milliards, de quoi s'occuper un bout de temps.

On peut compliquer le jeu. On peut faire une grille 16*16, en ajoutant les lettres ABCDEFG, mais ce n'est pas drôle : on perd en complication sans ajouter à la difficulté.

Plus amusant : le sudoku "killer" : là, on ne donne que des sommes partielles sur certaines zones. Par exemple, si vous avez 17 sur 2 cases, il y a obligatoirement 8 et 9. Là aussi, une seule solution possible.


Plus vicieux le, sudoku "greater" : on ne donne comme indication que des inégalités. La résolution est un peu mécanique, mais il y a de belles subtilités.



Enfin, on peut essayer le sudoku irrégulier :  les blocs de 9 cases ne sont plus carrées.



Je ne vous ai pas mis les références de tout ça : vous allez sur Qwant (pour embêter GGle - c'est aussi bien, français, sans pub, sans pistage), vous tapez sudoku, et vous trouvez tout. Le meilleur site est e-sudoku, on en trouve beaucoup, avec 4 niveaux de difficultés.


Aucun commentaire: