Christian Boyer - est spécialiste des récréations mathématiques et des carrés magiques.
Pour la Science, juin 2006

Autour des années 1890, plus d’un siècle avant le déferlement des sudokus, les Français jouaient déjà à remplir des grilles similaires, publiées dans des quotidiens et des magazines.
Depuis 2005, les grilles de sudokus sont un succès planétaire. Ce jeu est effectivement passionnant, et lorsqu’on s’attaque à une grille, il est bien difficile de la quitter avant sa résolution complète… Un sudoku, rappelons-le, est une grille carrée de 81 cases, divisée en 9 carrés comportant chacun 9 cases. Dans certaines cases figurent initialement des chiffres entre 1 et 9, et il s’agit de remplir les cases vides avec des chiffres de 1 à 9 de façon qu’aucun chiffre n’apparaisse deux fois dans une même ligne, une même colonne ou un même sous-carré.
Qui a inventé le sudoku ? Comme Jean-Paul Delahaye l’a décrit dans Pour la Science de décembre 2005, les premiers sudokus ont été publiés en 1979 par l’Américain Howard Garns, puis sont apparus dans des revues japonaises des années 1980 et 1990 où ils ont pris leur nom. Leur succès international a vraiment démarré grâce au Néo-zélandais Wayne Gould qui en a publiés dans le Times à partir de novembre 2004 et, depuis, les sudokus déferlent sur la planète. Mais y a-t-il eu des prémisses avant 1979 ? Nous allons voir que oui.
Dans son étude de 1782 publiée en français Recherche sur une nouvelle espèce de quarrés magiques, le grand mathématicien suisse Leonhard Euler a inventé les carrés latins. Un carré latin n x n est un carré comportant tous les entiers de 1 à n dans chaque ligne et chaque colonne. Tous les sudokus sont des carrés latins 9 x 9, mais la réciproque est fausse : les carrés latins 9 x 9 ne sont pas tous des sudokus, car ils ne sont pas nécessairement composés de sous-carrés 3 x 3 comportant tous les entiers de 1 à 9. Ainsi, les carrés latins 9 x 9 publiés par Euler ne sont pas des sudokus (voir ci-contre). Qui plus est, Euler n’a pas donné de côté ludique à son invention, ne laissant pas au lecteur le loisir de deviner des nombres manquants. Tel n’était pas son but.
Rien ne se serait passé entre 1782 et 1979 ? Si. À la fin du XIXe siècle, les quotidiens et magazines français – Le Siècle, La France, Gil Blas, L’Écho de Paris, Les Tablettes du Chercheur, la Revue des Jeux, etc. – foisonnent de jeux fondés sur des carrés magiques à compléter. Dans un carré magique, la somme des nombres inscrits dans chaque ligne, chaque colonne et chacune des deux diagonales est la même. Toutes les tailles de carrés étaient utilisées, y compris la taille 9 x 9 sur laquelle nous nous focaliserons.
Une particularité essentielle d’un sudoku est son découpage en sous-carrés 3 x 3. Parmi les variantes de carrés magiques publiées dans ces anciens journaux, certaines utilisent justement ce découpage. Il semble que la première grille 9 x 9 à compléter et organisée en sous-carrés 3 x 3 soit celle publiée par un dénommé H. Mary dans la Revue des Jeux en août 1891 (voir le problème 1, page 10). Un problème que la célèbre Colette a peut-être essayé de résoudre, elle qui tenait dans cet hebdomadaire une rubrique régulière de cancans mondains.
De très nombreuses autres grilles 9 x 9 compartimentées en sous-carrés 3 x 3 ont ensuite été publiées par divers auteurs et dans différents quotidiens ou magazines. Ces grilles y étaient souvent nommées « carrés à compartiments ».

Des grilles décomposables en deux sudokus

Parmi ces grilles figurent des carrés bimagiques. Un tel carré est un carré magique qui reste magique lorsqu’on élève au carré ses nombres. Le Français G. Pfeffermann a publié en 1890 le tout premier carré bimagique connu, qui était de taille 8 x 8. Il persévéra et publia en 1891 le premier carré bimagique 9 x 9. Comme les autres carrés, ces premiers carrés bimagiques paraissent sous la forme d’un jeu où il faut compléter les cases manquantes. Après l’ouverture de cette brèche par Pfeffermann, de nombreux autres carrés bimagiques 8 x 8 et 9 x 9 parurent dans divers quotidiens et revues.
Un exemple intéressant est le carré bimagique proposé en 1894 dans La France par Brutus Portier (voir le problème 5). Cette grille a une structure cachée remarquable : en décomposant chaque nombre N de la grille au moyen d’une écriture dans la base de numération 9 (on écrit N – 1 = 9(n1 – 1) + (n2 – 1), où n1 et n2 sont des entiers compris entre 1 et 9), on montre que le carré bimagique de Portier se décompose en deux sudokus, ce qui aide même à le résoudre. Il n’est d’ailleurs pas nécessaire qu’un carré soit bimagique pour être décomposable en deux sudokus, comme l’illustre le carré magique 9 x 9 proposé en 1892 dans Le Siècle par le commandant Coccoz (voir le problème 3).
Une telle décomposition est possible parce que l’on a affaire ici à des « carrés eulériens ». De quoi s’agit-il ? Dans son étude de 1782, Euler a posé un problème fameux, celui des 36 officiers : arranger une délégation de six régiments (chacun d'entre eux envoyant six officiers de grades différents) dans un carré 6 x 6 de façon à ce que chaque ligne et chaque colonne contienne un officier de chaque régiment et de chaque grade. C’est en côtoyant Portier en Algérie que Gaston Tarry, un fonctionnaire des impôts féru de récréations mathématiques, s’est intéressé aux carrés magiques et carrés latins. En 1900, Tarry fut le premier à prouver que le problème des 36 officiers n’a pas de solution. On sait aujourd’hui que pour tout n2 différent de 4 et de 36, le problème des n2 officiers admet des solutions, nommées aussi carrés eulériens n x n (ci-contre, un carré eulérien 3 x 3, ou solution au problème des 9 officiers notés grade.régiment).
Tout carré eulérien 9 x 9 n’est pas une combinaison de deux sudokus, c’est-à-dire de deux carrés latins structurés en sous-carrés. Mais avec leur décomposition en deux sudokus, les solutions du carré bimagique de Portier et du carré magique du commandant Coccoz (voir les problèmes 3 et 5) sont des carrés eulériens 9 x 9, solutions au problème des 81 officiers. La décomposition n’était pas mentionnée dans ces deux problèmes, mais le lien avec les 81 officiers était connu et signalé. Il a même fait l’objet d’un problème posé par A. Huber (voir le problème 4) ; sa solution, publiée en 1894 dans Les Tablettes du Chercheur, montre clairement que le carré 9 x 9 se structure en ce qu’on nomme aujourd’hui deux sudokus, puisque les deux carrés latins sont publiés en montrant bien leurs sous-carrés 3 x 3 remplis par tous les chiffres de 1 à 9.
C’est probablement en analysant la structure eulérienne et en sous-carrés de ces carrés bimagiques de Portier ou d’autres que Tarry a inventé une merveilleuse méthode générale pour construire des carrés multimagiques ; cette méthode est exposée pour la première fois dans un article de Tarry présenté par Henri Poincaré dans les Comptes-Rendus de l'Académie des Sciences en 1906. On trouve des détails de sa méthode, accompagnés de nombreuses constructions de carrés bimagiques 8 x 8 et 9 x 9, dans le livre du général Cazalas publié en 1934 (la méthode a d’ailleurs été légèrement améliorée par Cazalas). Une chose qui n’était pas signalée dans cet ouvrage, c’est que tous les carrés bimagiques 9 x 9 construits par la méthode de Tarry-Cazalas sont une combinaison de deux sudokus. Bien sûr, tous les couples de sudokus ne donnent pas un carré bimagique, et tous les carrés bimagiques (ceux non construits avec la méthode de Tarry-Cazalas, tel celui de Pfeffermann) ne proviennent pas d'un couple de sudokus.
Tous les problèmes mentionnés jusqu’ici sont des carrés magiques. Même si l’astuce sous-jacente des sudokus est là, ils ne laissent pas explicitement le lecteur jouer sur un simple carré latin en combinant seulement les chiffres 1 à 9, combinaisons qui font le charme et l’intérêt du sudoku. Pourtant, de purs carrés latins sont également présents dans les grilles proposées à l’époque. Ainsi, le problème posé par Portier dans Le Siècle du 31 décembre 1892 est un carré latin 9 x 9 à compléter… mais ce n’est pas un sudoku, puisqu’il n’y a pas de compartimentation en sous-carrés 3 x 3 (voir le problème 2). Le problème de B. Meyniel paru le 6 juillet 1895 dans le quotidien La France est peut-être le plus proche du but (voir le problème 6) : il s’agit d’un carré latin 9 x 9 à compléter, dont tous les entiers de 1 à 9 sont bel et bien regroupés dans les sous-carrés 3 x 3. Mais son auteur ne fait nulle part cette remarque, ce qui est bien dommage…

Tous les ingédiens des sudokus étaient présents

Nous avons ainsi vu quelques exemples, parmi les plus significatifs que j’ai pu trouver, de l’incroyable foisonnement au tournant du XXe siècle de ces problèmes variés et si proches du sudoku : des grilles 9 x 9 compartimentées en sous-carrés 3 x 3, des cases à compléter avec des nombres, et, pour certains, l’utilisation unique des chiffres de 1 à 9 dans chaque ligne, colonne, ou même sous-carré.
En d’autres termes, tous les ingrédients du sudoku y figuraient, et l’on peut s’étonner qu’aucun des nombreux et différents auteurs n’ait songé, avec le temps, à réunir tous ces éléments et à proposer un jeu de sudoku complètement identique au jeu que nous connaissons aujourd’hui. Le problème 6 en est tellement proche : marquez simplement ses sous-carrés, et vous aurez le plaisir de résoudre un sudoku conçu en 1895.
Ma recherche est toutefois loin d’avoir été exhaustive, sachant que les grilles et les journaux qui paraissaient à l’époque étaient très nombreux. Les lecteurs qui aiment fouiner dans les bibliothèques auront peut-être la chance d’y découvrir de véritables sudokus, conçus – et oubliés – depuis plus d’un siècle.