La grille de jeu est un carré de neuf cases de côté, subdivisé
en autant de carrés identiques, appelés régions (voir figure). La règle du jeu est simple : chaque ligne, colonne et région ne
doit contenir qu'une seule fois tous les chiffres de un à neuf. Formulé
autrement, chacun de ces ensembles doit contenir tous les chiffres de un à
neuf.
Les chiffres ne sont utilisés que par convention, les relations arithmétiques
entre eux ne servant pas. N'importe quel ensemble de signes distincts : lettre,
forme, couleur,... peut être utilisé sans changer les règles
du jeu.
L'intérêt du jeu réside dans la simplicité de ses
règles, et dans la complexité de ses solutions. Les grilles publiées
ont souvent un niveau de difficulté indicatif. L'éditeur peut
aussi indiquer un temps de résolution probable. Quoique en général,
les grilles contenant le plus de chiffres préremplis fussent les plus
simples, l'inverse n'est pas systématiquement vrai. La véritable
difficulté du jeu réside plutôt dans la difficulté
à trouver la suite exacte de chiffres à ajouter.
Ce jeu a déjà inspiré plusieurs versions électroniques
qui apportent un intérêt différent à la résolution
des grilles de Sudoku. Sa forme en grille et son utilisation ludique le rapprochent
d'autres casse-tête publiés dans les journaux, tels les mots croisés
et les problèmes d'échecs.
Des professeurs recommandent la pratique du Sudoku comme un entraînement
aux raisonnements logiques. Le niveau de difficulté peut dans ce cas
être adapté au public.
Historique
Le problème des officiers
En 1782, le mathématicien suisse Leonhard Euler imagine un problème
dans une grille. Certains attribuent la paternité du Sudoku au Suisse
bien que les travaux d'Euler concernaient les carrés latins et la théorie
des graphes.
On considère six régiments différents, chaque régiment
possède six officiers de grades distincts. On se demande maintenant comment
placer les 36 officiers dans une grille de 6x6, à raison d'un officier
par case, de telle manière que chaque ligne et chaque colonne contienne
tous les grades et tous les régiments.
Il s'agit en d'autres termes d'un carré gréco-latin d'ordre 6
(la combinaison de deux carrés latins, un carré latin pour les
régiments, un carré latin pour les grades), problème dont
la résolution est impossible. Euler l'avait déjà pressenti
à l'époque, sans toutefois donner une démonstration formelle
à sa conjecture. Il dira :
Or, après toutes les peines qu’on s’est données
pour résoudre ce problème, on a été obligé
de reconnaître qu’un tel arrangement est absolument impossible,
quoiqu’on ne puisse pas en donner de démonstration rigoureuse.
En 1901, le Français Gaston Tarry démontre l'impossibilité
du résultat grâce à une recherche exhaustive des cas et
par croisement des résultats.
Le lien entre le Sudoku et le problème des 36 officiers est la contrainte
qui empêche la répétition du même élément
dans la grille, tout en arrivant au final à un jeu qui emploie le principe
du carré latin (combinaison de deux carrés latins dans le cas
du carré gréco-latin, carré latin subdivisé en plusieurs
régions dans le cas du Sudoku).
La version moderne du Sudoku
En 1979, un pigiste spécialisé dans les casse-tête, Howard
Garns, crée le premier jeu. Dell Magazines l'introduit cette même
année dans une publication destinée au marché newyorkais,
le Dell Pencil Puzzles and Word Games, sous le nom de Number Place. Nikoli l'introduit
au Japon en avril 1984 dans le magazine Monthly Nikolist et le nomme Suji wa
dokushin ni kagiru (que l'on peut traduire par « le chiffre doit être
unique » ou « survient une seule fois »). C'est le président
de Nikoli qui le nomme ainsi. Plus tard, le nom change et devient Sudoku, respectant
ainsi la tradition de former un mot plus court en prenant le premier kanji de
la paraphrase.
En 1986, Nikoli introduit deux nouveautés, qui rendront le jeu populaire
: le nombre de dévoilés est au plus de 30 et les grilles sont
symétriques, c'est-à-dire que les dévoilés sont
symétriquement distribués autour du centre de la grille. Aujourd'hui,
la plupart des journaux importants au Japon, tel Asahi Shimbun, publient ce
jeu. Au Japon, Nikoli est toujours propriétaire du nom Sudoku ; ses concurrents
utilisent un autre nom.
En 1989, Loadstar et Softdisk publient DigitHunt pour le Commodore 64, probablement
le premier logiciel pour ordinateur personnel à générer
des Sudoku. Il existe une entreprise qui continue à utiliser ce nom.
En 1995, Yoshimitsu Kanai publie un générateur logiciel sous
le nom de Single Number (traduction anglaise de Sudoku), pour le Macintosh,
en japonais et en anglais et, en 1996, il récidive pour le Palm.
En 2005, Dell Magazines publie également deux magazines dédiés
aux Sudoku : Original Sudoku et Extreme Sudoku. De plus, Kappa Publishing Group
reprend les grilles de Nikoli dans GAMES Magazine sous le nom de Squared Away.
Les journaux New York Post, USA Today et San Francisco Chronicle publient aussi
ce jeu. Des grilles apparaissent dans certaines anthologies de jeux, telles
que The Giant 1001 Puzzle Book (sous le nom de Nine Numbers).
C'est en juillet 2005 que le sudoku arrive en France, publié par Sport
cérébral, éditeur spécialisé dans les jeux
de réflexion. Le premier numéro se vendra à 20 000 exemplaires
soit deux fois plus qu'à l'accoutumée lors de la sortie d'un nouveau
jeu, un record selon Xavier de Bure, directeur général de l'éditeur.
Le Figaro publie les premières grilles quotidiennes dès le début
juillet, suivi au cours de l'été 2005 par Libération, La
Provence, Nice Matin, 20 Minutes, Métro et Le Monde. Le magazine 1, 2,
3... Sudoku sortit son premier numéro en novembre 2005.
Le phénomène a également gagné la Suisse, Wayne
Gould fournit des grilles au quotidien francophone Le Matin qui a vendu cette
année 150 000 livres de sudoku et envisage par ailleurs de produire une
émission télévisée sur ce thème. Le Temps,
autre quotidien helvétique publie quant à lui des grilles de sudoku
depuis septembre.
Il semble que les Japonais aient développé le jeu du Sudoku parce
que leur alphabet comportait trop de signes pour pouvoir produire à grande
échelle des mots croisés.