Le jeu de SUDOKU
La grille de jeu est un carré de neuf cases de côté, subdivisé en autant de sous-grilles carrées identiques, appelés régions.
La règle du jeu générique donnée en début d'article se traduit ici simplement : 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, symbole… peut être utilisé sans changer les règles du jeu. Dell Magazine, le premier à publier des grilles, a utilisé des chiffres dans ses publications.
Par contre, Scramblets, de Penny Press, et Sudoku Word, de Knight Features Syndicate, utilisent tous les deux des lettres.
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. Le sudoku entre maintenant dans certains cursus universitaires.
Des grilles sont publiées dans des journaux, mais peuvent aussi être générées par ordinateur comme sur sudoku-gratuit.
Origine du sudoku
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
Le sudoku a des ancêtres français qui remontent à 1895.
Le jeu n'est apparemment pas une invention récente comme beaucoup le pensaient. À la fin du XIXe siècle, les Français jouaient en effet à remplir des grilles 9x9 divisées en 9 régions, très proches de ce jeu (mais les grilles initiales comprenaient des contraintes supplémentaires sur la solution), qui étaient publiées dans les grands quotidiens de l'époque, révèle Pour la Science dans son édition de juin 2006.
Selon le magazine, la grille la plus proche d'un sudoku, qui a été retrouvée par le Français Christian Boyer, est celle de B. Meyniel, publiée dans le quotidien La France du 6 juillet 1895, et une variante proche a été publiée peu avant, en novembre 1892, dans Le Siècle, variante qui utilisait des nombres à deux chiffres.
En 1979, un pigiste spécialisé dans les casse-tête, Howard Garns, crée le premier jeu tel que nous le connaissons aujourd'hui. Dell Magazines l'introduit cette même année dans une publication destinée au marché new-yorkais, 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.
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.
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 anglaiset, 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. Le Temps, autre quotidien helvétique publie quant à lui des grilles de sudoku depuis septembre.
Un autre ancêtre du sudoku : le carré latin magique
Les expériences agronomiques en champ, généralement constituées d'un certain nombre de parcelles carrées ou rectangulaires, sont souvent organisées sous la forme de blocs aléatoires complets, c'est-à-dire de groupes de parcelles voisines au sein desquels les différents éléments à comparer (différentes fumures par exemple) sont tous présents et répartis au hasard.
Quand le nombre total de parcelles disponibles est égal à un carré (16, 25, 36, etc.), une autre possibilité correspond à la notion de carré latin, qui est tel que les différents éléments à comparer sont présents dans chacune des lignes et dans chacune des colonnes de parcelles.
La superposition de ces deux dispositifs peut donner naissance à ce qui a été appelé carré latin magique, notamment par W.T. Federer en 1955. Dans l'exemple cité, chacun des six éléments étudiés (par exemple six fumures différentes) est présent dans chacun des six blocs de 2 x 3 parcelles, dans chacune des six lignes et dans chacune des six colonnes. Il s'agit strictement d'un sudoku 6 x 6.
Le sudoku classique n'est donc rien d'autre qu'un carré latin magique 9
Source : Wikipédia
|
