Sudoku

Préambule sur les jeux mathématiques

Les questions qui suivent m'ont été posées par une journaliste. Je ne suis pas à proprement parler fan de jeux mathématiques, mais il est important pour moi que le grand public comprenne les enjeux de la science d'aujourd'hui et des mathématiques en particulier. Une très grande partie de la société est mathématisée, même si c'est souvent invisible ou mal compris, que ce soit par les politiques et par les media. Et c'est pour cela qu'il est important, pour moi, que les mathématicien-ne-s donnent leur point de vue sur la société. Je pense donc vital que les journaux n'aient pas peur de diffuser des mathématiques, ce qui sous-entend un minimum de profondeur. Par contre, je pense aussi qu'il ne faut pas croire d'une part que les maths ne sont pas dynamiques et actuelles, ni d'autre part que les seules choses que les matheux peuvent transmettre à leurs semblables sont les jeux ... Derrière un jeu, il y a souvent des problèmes profonds, et le Sudoku n'échappe pas à la règle. Pour moi le jeu (mathématique ou pas) est l'essence 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. Je ne m'intéresse donc au jeu (mathématisable, ce qui est le cas de presque tout, comme le proclamait Pythagore) 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.

Comment expliquer le succès remporté par les grilles Sudoku, dans le monde entier et aujourd'hui chez nous en France ?

Même si le jeu tel qu'on le connaît existait déjà au Royaume Uni, il doit sa popularité au Japon. 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 de mes commentaires suivants. Remarquons également que des jeux semblables, mais avec autre chose que les nombres de 1 à 9, existaient dans des temps encore plus reculés.

Quelle est la force du concept de ce jeu, la recette clef de son succès auprès de personnes de toutes cultures et de tous niveaux sociaux ?

Il faut bien comprendre que le Sudoku N'EST PAS un puzzle arithmétique ou mathématique. 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. Et le nombre a quelque chose d'universel. Pythagore (mathématicien, philosophe et astronome grec du VIème siècle avant JC) disait « Tout est nombre ». De plus tout le monde sait appréhender les nombres de 1 à 10, et je ne suis pas sûr que le jeu aurait autant de succès si on avait affaire à des petits carrés 4x4, c'est-à-dire des grilles 16x16. Remarquons deux ou trois choses en marge :

  • La première est que 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, eux, un intérêt mathématique. En effet ils correspondent aux tables de multiplication de ce que les mathématiciens appellent des quasi-groupes. Un exemple ? Prenons les nombres de 1 à 4 et écrivons la table de multiplication comme on le fait (à la suite de Pythagore) en CM1 :
    1 2 3 4
    2 4 6 8
    3 6 9 12
    4 8 12 16
    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 :
    1 2 3 4
    2 4 1 3
    3 1 4 2
    4 3 2 1
    C'est un carré latin ! Magique ? Pas du tout, nous venons d'écrire la table de multiplication du « groupe cyclique à quatre éléments ».
  • La seconde est qu'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é !). Et c'est aussi pourquoi les mathématicien-ne-s ne trouvent que peu d'intérêt à le pratiquer ainsi ...
  • Mais on peut se poser une question supplémentaire. Bien sûr il n'y a qu'un nombre fini de Sudoku, en fait exactement 6 670 903 752 021 072 936 960, soit plus de 6 trilliards ! Par contre, si on étudie des Sudoku de taille arbitraire, on peut se demander comment varie le nombre de Sudoku en fonction de la taille de la grille, ou mieux comment varie la difficulté à le résoudre. C'est ce qu'on appelle la complexité du problème. Cette complexité est importante puisque la résolution d'un Sudoku de taille arbitraire est un problème NP-complet. Késako ? Cela veut dire que l'on peut vérifier facilement qu'une solution est correcte, mais qu'en revanche en trouver une est ardu. Très grossièrement cela veut dire que l'on ne peut pas espérer construire un algorithme pour qu'un ordinateur puisse résoudre ce problème. (Rappelons que je parle de grilles de taille arbitraire.) Autrement dit 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.
  • Enfin c'est difficile à condition que la conjecture P=NP soit fausse. Cette fameuse conjecture fait l'objet d'un prix de un million de dollards, offert par le Clay Institute pour chacun des sept problèmes du millénaire. En résumé les Sudoku deviennent très intéressants pour les mathématicien-ne-s (et les informaticien-ne-s) dès qu'on veut chercher une façon automatique de les résoudre dans des tailles arbitraires. Cela peut même rapporter un million de dollars ! Mais ce n'est probablement pas le principal, car pratiquement tous les problèmes de la vie quotidienne liés à l'informatique dépendent étroitement de la conjecture P=NP : connexions sécurisées, recherche de parcours optimaux (pour les GPS) etc.

Cette "Sudokumania", n'est-ce pas un effet de mode qui va s'estomper au fil du temps ? Les gens ne vont-ils pas se lasser de ce jeu ?

Je ne suis pas devin ! Si on compare les Sudoku aux mots croisés, je dirais que non. D'ailleurs les habituels recueils de jeux logiques pour l'été ont un public. Les Sudoku vont y figurer en bonne place. Ayant de par mon métier l'habitude d'exercer ma logique, je ne suis guère intéressé par ce jeu, bien moins que par les mots croisés, mais pour ceux qui n'en ont pas l'usage fréquent, c'est assurément un bon exercice, que l'on peut sans doute pratiquer chaque jour ! Pour revenir à ce qui précède, la plupart des Sudoku sont créés par ordinateur. En effet, il est assez compliqué de dire si oui ou non un Sudoku a une solution et encore moins s'il n'en a qu'une. Des algorithmes de recherche (pour les Sudoku classiques, par pour ceux de taille arbitraire) ont donc vu le jour et on leur confie cette partie. On les utilise même pour construire des Sudoku. Les sites internet proposant cela sont très nombreux. Le corollaire de cela est qu'il est très facile de créer des Sudoku et donc ceux qui animent les rubriques ne seront jamais en panne de problème. La mode durera donc aussi longtemps que le public sera présent.

Existe-t-il un autre jeu mathématique qui aurait connu une ampleur similaire, et dégagé de telles retombées économiques, à l'étranger ou en France ?

J'insiste sur le fait que le Sudoku N'EST PAS un jeu mathématique. En tout cas pas plus que les échecs ou le go. Vous avez donc une partie de la réponse : les échecs sont un exemple de succès de jeu ayant les qualités précédentes. Dans les jeux en solitaire, des jeux comme Tétrix relèvent du même degré de mathématisation que le Sudoku. Si l'on se restreint aux jeux purement cérébraux, citons les réussites, qui sont de même nature. Mais il y a peu de réussites qui demandent une expertise pour les créer, elles n'engendrent donc pas de phénomène économique. L'atout du Sudoku est qu'il faut réellement un ordinateur pour pouvoir créer à foison des problèmes (i.e. à solution unique). C'est ce qui fait qu'on peut le vendre. Cela posé, les accros qui ont accès à internet ou qui savent programmer n'ont pas besoin d'acheter un journal pour cela ... Dans les jeux réellement mathématiques qui ont eu du succès, je songe au cube de Rubik. C'est encore un problème de théorie des groupes, même si ceux qui battent des records de vitesse ne sont probablement pas initiés à la théorie des groupes. Mais, attention, contrairement à ce qu'on peut lire sur internet, le cube de Rubik n'a strictement aucun rapport avec le Sudoku. Voilà, pour clore, je vais vous raconter une petite histoire. Ce sont deux explorateurs qui partent en montgolfière et qui finissent par se perdre dans le brouillard. N'ayant plus aucune idée de l'endroit où ils sont, ils descendent près du sol pour trouver une bonne âme pour les aider. Ils finissent pas apercevoir une personne allongée contre un arbre. Ils se rapprochent d'elle et la hèle : «Hé ! L'ami ! Peux-tu nous dire où nous sommes ? » L'autre les dévisage longuement, si longuement que les deux explorateurs finissent par penser qu'il est sourd et commencent à faire des gestes pour s'expliquer. Un sourire vient aux lèvres de l'inconnu qui leur parle enfin : « Vous êtes dans une montgolfière ! » Les deux explorateurs se regardent avec effarement. Puis l'un des deux dit à l'autre : « Nous sommes tombés sur un mathématicien ! » Devant l'air surpris de son compagnon, il poursuit : « Il a mis très longtemps à nous répondre. Sa réponse est parfaitement exacte. Et elle ne nous sert à rien. » J'espère vous avoir apporté un peu plus que ce collègue n'a apporté aux deux explorateurs ! Tout scientifique a l'habitude de citer ses sources. En voici, que vous trouverez sur internet. Malheureusement (mais c'est une évidence) toutes ces références sont en anglais.