Sudoku

Piste verte Le 22 novembre 2008  - Ecrit par  François Sauvageot Voir les commentaires (1)

Le jeu est un reflet de l’activité humaine, en ce sens qu’il met en scène une situation et permet donc de s’y plonger, de la vivre concrètement et, si on le désire, y réfléchir. Le mathématicien s’intéresse au jeu principalement parce qu’il est un bon vecteur, un moyen de faire comprendre des maths et aussi des phénomènes de la société contemporaine à des personnes a priori rétives ou étrangères à cette vision.

En 1783 un mathématicien suisse, Léonhard Euler, pose le problème des officiers : comment placer dans un carré 6 officiers de 6 régiments différents, de sorte que dans chaque ligne et chaque colonne, il n’y ait qu’un seul représentant de chaque régiment et de chaque grade ?

Ce problème est à l’origine de l’intérêt des mathématiciens et des
informaticiens pour l’ancêtre du Sudoku, le carré latin. C’est un architecte retraité de 74 ans, Howard Garn, qui crée le puzzle, qu’il nomme Number Place, pour la revue américaine Dell Magazine. Le jeu est popularisé au Japon dans les années 80, cinq ans après la mort de Garn, dans la revue Monthly Nikolist sous le nom de « Suuji Wa Dokushin Ni Kagiru »
(les nombres doivent être uniques), et le jeu devint populaire. Kaji Maki, président de Nikoli, abrévia le nom en Sudoku (nombre unique) et déposa le nom. Comme le jeu était populaire, les concurrents gardèrent le nom original Nanpure (nombre placé). Encore maintenant des magazines japonais donnent le nom Number place, tandis qu’aux Etats-Unis et ailleurs on parle de Sudoku..

Les jeux de lettres, comme les mots croisés, sont bien moins porteurs au Japon. C’est en 2004 que l’engouement pour ce jeu est devenu total au Japon. Cette ferveur s’est ensuite répandue au Royaume Uni via les quotidiens nationaux. S’il y a des explications sur ce phénomène, elles viennent peut-être des commentaires suivants.

Il faut bien comprendre que le Sudoku n’est pas un puzzle arithmétique. On pourrait substituer n’importe quoi aux nombres, mais ce qui marche le mieux est probablement les nombres, car la collection de référence la plus commune pour neuf choses est probablement la liste des neuf premiers nombres. Le nombre a quelque chose d’universel : Pythagore (mathématicien, philosophe et astronome grec du VIème siècle avant notre ère) disait « Tout est nombre ». De plus tout le monde sait appréhender les nombres de 1 à 10. Les grilles 16x16, avec des petits carrés 4x4, ont nettement moins de succès.

Le Sudoku est un dérivé des carrés latins, problème qui consiste à remplir un carré de taille arbitraire en utilisant les mêmes symboles sur chaque ligne, mais de sorte qu’aucun n’apparaisse deux fois dans une même colonne. C’est comme un Sudoku, sauf qu’il n’y a pas la contrainte sur les petits carrés. Les carrés latins ont un intérêt mathématique. En effet ils correspondent à des tables de multiplication un peu spéciales. En voici un exemple.

Prenons les nombre de 1 à 4 et écrivons la table de multiplication comme on le fait (à la suite de Pythagore) en CM1 :

1234
2468
36912
481216

Et maintenant prenons le reste de la division par 5 dans toutes les cases. Par exemple pour 12, on a « 12 divisé par 5 égale 2 et il reste 2 », soit 12=2x5+2, et nous écrivons 2 à la place de 12. Voici le résultat :

1234
2413
3142
4321

C’est un carré latin ! Magique ? Pas du tout, nous venons d’écrire la table de multiplication du groupe cyclique à quatre éléments.

On peut faire des Sudoku avec des grilles élémentaires rectangulaires de taille arbitraire. Par exemple on peut mettre les nombres de 1 à 6 dans un rectangle 2x3 et essayer de remplir une grille formée de six rectangles, avec les règles usuelles du Sudoku. Ces Sudoku avec six nombres sont plus accessibles que ceux avec neuf nombres.

Ceux plus grands, comme les 16x16, sont en revanche souvent plus difficiles. En fait la complexité des Sudoku peut être étudiée d’un point de vue algorithmique et on touche là à l’informatique et à la logique.
Symboliquement, remplir un Sudoku revient à se promener sur une route avec des croisements en patte d’oie et à avancer quand on peut (i.e. quand on peut mettre un nombre sans enfreindre une des règles) ou à reculer vers l’embranchement précédent quand on est bloqué. Remplir un Sudoku de cette façon est donc purement un exercice de logique (et de ténacité !).

Néanmoins quand on étudie les Sudoku de taille arbitraire, l’exercice devient de plus en plus complexe au fur et à mesure que la taille augmente. En fait résoudre un Sudoku de taille arbitraire est aussi difficile que de trouver un algorithme pour casser la sécurité des protocoles de cryptographie utilisés sur internet ou dans les cartes à puce. On parle de problème NP-complet.

Vous pouvez consulter également l’article de Wikipédia.

Article édité par François Sauvageot

Partager cet article

Pour citer cet article :

François Sauvageot — «Sudoku» — Images des Mathématiques, CNRS, 2008

Commentaire sur l'article

  • Sudoku

    le 24 mars 2009 à 18:58, par youness

    le jeu de sudoku c’est un jeux qui se base sur l’esprit ouvert et aussi d’essayer de faire plusieurs types de sudoku dés le plus facile jusqu’à le difficile
    et bonne chance à tous

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM