logo

Sudoku


Sudoku : encyclopédie mathématiques

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.
Aller Ă  : Navigation, Rechercher

Le sudoku (prononcé /sudoku/ en français, /sɯːdokɯ/ en japonais), est un jeu en forme de grille défini en 1979 et inspiré du carré latin ainsi que du problÚme des 36 officiers du mathématicien suisse Leonhard Euler.

Le but du jeu est de remplir cette grille avec une sĂ©rie de chiffres (ou de lettres ou de symboles) tous diffĂ©rents, qui ne se trouvent jamais plus d'une fois sur une mĂȘme ligne, dans une mĂȘme colonne ou dans une mĂȘme sous-grille.

La plupart du temps, les symboles sont des chiffres allant de 1 à 9, les sous-grilles étant alors des carrés de 3 x 3.

Quelques symboles sont déjà disposés dans la grille, ce qui autorise une résolution progressive du problÚme complet.

Sommaire

[modifier] Présentation

Une grille 9×9 de sudoku (cliquer sur l'image pour voir la solution, qui apparaüt au bas)
Une grille 9×9 de sudoku (cliquer sur l'image pour voir la solution, qui apparaüt au bas)

La grille de jeu présentée à droite, à titre d'exemple, est un carré de neuf cases de cÎté, subdivisé en autant de sous-grilles carrées identiques, appelées 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 - lettres, formes, couleurs, symboles - 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. Quoiqu'en gĂ©nĂ©ral les grilles contenant le plus de chiffres prĂ©remplis soient les plus simples, l'inverse n'est pas systĂ©matiquement vrai. La vĂ©ritable difficultĂ© du jeu rĂ©side plutĂŽt dans la difficultĂ© de trouver la suite exacte des 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 tests universitaires.

Des grilles sont publiĂ©es dans des journaux, mais peuvent aussi ĂȘtre gĂ©nĂ©rĂ©es Ă  la demande sur Internet.

[modifier] Étymologie

Le nom sudoku (æ•°ç‹Ź) est nĂ© de l'abrĂ©viation de la rĂšgle du jeu japonaise « SĆ«ji wa dokushin ni kagiru Â» (æ•°ć­—ăŻç‹Źèș«ă«é™ă‚‹?), signifiant « il ne peut y avoir qu'un seul et unique chiffre Â» (par case et par ligne). Cette abrĂ©viation associe les caractĂšres SĆ« (数) chiffre et Doku (独) unique. Ce nom est une marque dĂ©posĂ©e au Japon de l'Ă©diteur Nikoli Corporation Ltd.. En japonais, ce mot est prononcĂ© [sɯːdokÉŻ] ; en français, il est couramment employĂ© avec une prononciation francisĂ©e, c'est-Ă -dire en ignorant la voyelle longue prĂ©sente sur le premier « u Â» et en modifiant lĂ©gĂšrement le timbre des voyelles « u Â» : [sudoku]. Au Japon, Nikoli est toujours propriĂ©taire du nom sudoku ; ses concurrents utilisent donc un autre nom : ils peuvent renvoyer au jeu par le nom amĂ©ricain original « Number Place Â» (anglais : Place NumĂ©rale), ou encore par le mot « Nampure Â», plus court. Quelques Ă©diteurs non japonais orthographient le titre « Su Doku Â».

[modifier] Historique

[modifier] Antiquité

Un des ancĂȘtres du sudoku Ă©tait un carrĂ© de neuf cases Ă  remplir par trois lettres (A, B et C) sans qu'une mĂȘme lettre apparaisse deux fois dans la mĂȘme colonne, ligne ou diagonale.

[modifier] Inde et Chine

Les plus anciens « carrĂ©s magiques Â» numĂ©riques connus se trouvent en Chine (nommĂ© Luoshu 掛äčŠ, le livre de la riviĂšre Luo ) oĂč les chiffres Ă©taient reprĂ©sentĂ©s par diffĂ©rentes formes gĂ©omĂ©triques contenant n ronds[1] (vers -300), et en Inde oĂč furent inventĂ©s ce que nous appellons les chiffres arabes. Ils ont Ă  l'origine des significations divinatoires.

[modifier] Moyen Âge

Ce sont les arabes qui au Xe siĂšcle auraient donnĂ© les premiers une application purement mathĂ©matique et non plus sacrĂ©e aux carrĂ©s magiques.

[modifier] Renaissance

[modifier] En occident

Cornelius Agrippa (1486-1535), utilise des carrés magiques toujours dans un but ésotérique.

Le mathématicien français Pierre de Fermat (1601(ou 1607)-1665) travailla sur les carrés magiques et les étendit aux cubes magiques.

En 1691 Simon de La LoubĂšre explique le fonctionnement du carrĂ© magique utilisĂ© au Siam, dans son ouvrage Du Royaume de Siam, oĂč celui-ci possĂšde une fonction sacrĂ©e.

[modifier] Le problĂšme des officiers

ProblĂšme des 36 officiers : un carrĂ© grĂ©co-latin d'ordre 6 est impossible Ă  rĂ©soudre
ProblĂšme des 36 officiers : un carrĂ© grĂ©co-latin d'ordre 6 est impossible Ă  rĂ©soudre

En 1782, le mathématicien suisse Leonhard Euler imagine un problÚme dans une grille. Certains attribuent donc la paternité du sudoku au Suisse, bien que les travaux d'Euler concernassent 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).

[modifier] 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. Une variante proche avait été publiée peu avant, en novembre 1892, dans Le SiÚcle, variante qui utilisait des nombres à deux chiffres.[2]

En 1979, un pigiste spĂ©cialisĂ© dans les casse-tĂȘtes, 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 : les cases dĂ©voilĂ©es sont symĂ©triquement distribuĂ©es autour du centre de la grille et leur nombre est au plus de 30. Cependant, on ignore toujours Ă  cette Ă©poque, les autres symĂ©tries possibles sur la grille dont l'axe de symĂ©trie est l'une des deux diagonales ou des deux mĂ©dianes (la colonne et la ligne centrales). Aujourd'hui, la plupart des journaux importants au Japon, tel Asahi Shimbun, publient le jeu sous cette forme de symĂ©trie centrale. Mais en dĂ©pit de cet aspect esthĂ©tique, les grilles sont gĂ©nĂ©ralement de mauvaise qualitĂ©, car les trois propriĂ©tĂ©s concernant la symĂ©trie, l'unicitĂ© de la solution et l'irrĂ©ductibilitĂ© ne peuvent ĂȘtre rĂ©alisĂ©es en mĂȘme temps!

En 1989, Loadstar et Softdisk publient DigitHunt pour le Commodore 64, probablement le premier logiciel pour ordinateur personnel à générer des Sudoku. Une entreprise continue d'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[3] et, en 1996, il récidive pour le Palm[4].

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, publié par Sport cérébral, éditeur spécialisé dans les jeux de réflexion, arrive en France. 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. La Provence publie les premiÚres grilles quotidiennes le 27 juin 2005, suivi au cours de l'été 2005 par Le Figaro |Libération]], 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-lĂ  150 000 livres de sudoku. Le Temps, autre quotidien helvĂ©tique publie quant Ă  lui des grilles de sudoku depuis septembre 2005.

[modifier] Un autre ancĂȘtre du sudoku : le carrĂ© latin magique

Exemple d'expérience en carré latin magique relative à la comparaison de six éléments (par exemple six fumures différentes, numérotées de 1 à 6).
Exemple d'expérience en carré latin magique relative à la comparaison de six éléments (par exemple six fumures différentes, numérotées de 1 à 6).

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[5]. Dans l'exemple présenté ci-contre, 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 x 9[6].

[modifier] Popularité dans les médias

DÚs 1997, Wayne Gould, un Néo-Zélandais et juge à la retraite de Hong Kong, est intrigué par une grille partiellement remplie dans une librairie japonaise. Pendant six ans, il développe un programme qui génÚre automatiquement ces grilles. Sachant que les journaux britanniques publient des mots croisés et autres jeux semblables depuis longtemps, il promeut le sudoku auprÚs du journal The Times, lequel publie pour la premiÚre fois une grille le 12 novembre 2004.

Trois jours plus tard, The Daily Mail publie aussi une grille sous le nom Codenumber. The Daily Telegraph introduit sa premiĂšre grille le 19 janvier 2005, suivi par les autres publications du Telegraph Group. Le 20 mai 2005, le Daily Telegraph de Sydney publie pour la premiĂšre fois une grille.

C'est lorsque le Daily Telegraph publie des grilles sur une base quotidienne, Ă  partir du 23 fĂ©vrier 2005, tout en promouvant celui-ci sur sa page une, que les autres journaux britanniques commencent Ă  y prĂȘter attention. Le Daily Telegraph a continuĂ© sa campagne de promotion lorsqu'il a rĂ©alisĂ© que ses ventes augmentaient simplement par la prĂ©sence d'une grille de sudoku. The Times Ă©tait plutĂŽt discret sur l'immense popularitĂ© qui entourait son concours de sudoku. Il avait dĂ©jĂ  prĂ©vu de tirer avantage de son avance en publiant un premier livre sur le sudoku.

En avril et mai 2005, le jeu était suffisamment populaire pour que plusieurs journaux nationaux le publient sur une base réguliÚre. Au nombre de ceux-ci, on retrouve The Independent, The Guardian, The Sun (intitulé Sun Doku) et The Daily Mirror. Lorsque le mot Sudoku devient populaire au Royaume-Uni, le Daily Mail l'adopte à la place de Codenumber. DÚs lors, les journaux ont rivalisé d'imagination pour pousser leurs grilles. The Times et Daily Mail affirment qu'ils sont les premiers à avoir publié une grille de sudoku, alors que The Guardian affirme, ironiquement, que ses grilles construites à la main, obtenues de Nikoli, apportent une meilleure expérience que les grilles générées à l'aide d'un logiciel.

La subite popularité du sudoku au Royaume-Uni a attiré son lot de commentaires dans les médias (voir Sources ci-dessous) et des parodies ont suivi, par exemple la section G2 du journal The Guardian' s'annonce comme le premier supplément avec une grille par page[7]. Le sudoku est devenu particuliÚrement visible tout de suite aprÚs les élections de 2005 au Royaume-Uni, incitant quelques commentateurs à affirmer qu'il remplissait un besoin chez le lectorat politique. Une autre explication suggÚre qu'il attire et retient l'attention des lecteurs, plusieurs se sentant de plus en plus satisfaits lorsque la solution se dessine. The Times estime que les lecteurs apprécient à la fois les grilles faciles et difficiles. En conséquence, il les publie cÎte à cÎte depuis le 20 juin 2005.

La tĂ©lĂ©vision britannique s'est empressĂ©e de surfer sur la vague de popularitĂ© et Sky One diffuse la premiĂšre Ă©mission sur le sudoku, Sudoku Live, le 1er juillet 2005, que le mathĂ©maticien Carol Vorderman prĂ©sente. Neuf Ă©quipes de neuf joueurs, dont une vedette, chacune reprĂ©sentant une rĂ©gion gĂ©ographique, tentent de complĂ©ter une grille de sudoku. Chaque joueur a en main un appareil qui lui permet de saisir un chiffre dans l'une des quatre cellules dont il est responsable. Échanger avec les autres membres de l'Ă©quipe est permis mais, la familiaritĂ© manquant, les compĂ©titeurs ne le font pas. Également, l'auditoire Ă  la maison participe Ă  une autre compĂ©tition interactive en mĂȘme temps. Sky One a tentĂ© de crĂ©er un engouement[8] pour son Ă©mission par le biais d'une Ă©norme grille de 84 m de cĂŽtĂ©. Cependant, il avait 1 905 solutions.

Cette brusque augmentation de popularitĂ© dans les journaux britanniques et internationaux fait que le sudoku est considĂ©rĂ© comme le « cube de Rubik du XXIe siĂšcle Â» (traduction libre de « the Rubik's cube of the 21st century Â»). À titre d'exemple, Wayne Gould fournit fin 2005 des grilles pour environ 70 quotidiens dans 27 pays. Le dĂ©veloppement de cette sociĂ©tĂ© a Ă©tĂ© financĂ© en partie par le gouvernement anglais qui y voit un moyen de prĂ©vention des maladies sĂ©niles (Alzheimer en particulier).

Le 28 novembre 2005, la TĂ©lĂ©vision suisse romande lance une Ă©mission tĂ©lĂ©visĂ©e quotidienne, Su/do/ku, oĂč deux candidats s'affrontent sur 5 jours, Ă  raison de 3 manches de 8 minutes chaque jour. Toutefois, la difficultĂ© pour faire passer ce genre de jeu Ă  la tĂ©lĂ©vision entraĂźnera l'arrĂȘt de l'Ă©mission aprĂšs quelques semaines.

Des championnats nationaux sont également organisés comme le 1er championnat de France de sudoku (Paris, 18 décembre 2005) remporté par Juliette Thery, 19 ans. Cette compétition organisée par Sport cérébral récompense le meilleur joueur de l'année. C'est l'agence de communication Décollage vertical qui a mis en place cet évÚnement unique en France. Depuis, de nombreux autres tournois ont été organisés en France.

[modifier] Variantes

Un sudoku diagonal résolu. Les chiffres varient de 1 à 9 en diagonale, ce qui apporte une aide supplémentaire pour le résoudre.
Un sudoku diagonal résolu. Les chiffres varient de 1 à 9 en diagonale, ce qui apporte une aide supplémentaire pour le résoudre.
Un sudoku irrégulier
Un sudoku irrégulier

Bien que les grilles classiques soient les plus communes, plusieurs variantes existent :

  • 2×2 ou "Sudoku binaire", contenant des rĂ©gions 1×1 (version pleine d'ironie) ;
  • 4×4 contenant des rĂ©gions 2×2 (gĂ©nĂ©ralement pour les enfants) ;
  • 5×5 contenant des rĂ©gions en forme de pentamino ont Ă©tĂ© publiĂ©s sous le nom Logi-5;
  • 6×6 contenant des rĂ©gions 2×3 (proposĂ©e lors du World Puzzle Championship) ;
  • 7×7 avec six rĂ©gions en forme d'hexamino et une rĂ©gion disjointe (proposĂ©e lors du World Puzzle Championship) ;
  • 9×9 avec des rĂ©gions en forme de ennĂ©amino ;
  • 16×16 avec des rĂ©gions 4×4 (appelĂ©es Number Place Challenger et publiĂ©es par Dell, ou appelĂ©es parfois Super Sudoku), (ou encore Sudoku HexadĂ©cimal utilisant une notation en base 16 (Chiffre de 0 Ă  9 + lettres de A Ă  F) ;
  • 25×25 avec des rĂ©gions 5×5 (appelĂ©es Sudoku the Giant et publiĂ©es par Nikoli) ;
  • une variante impose de plus que les chiffres dans les diagonales principales soient uniques. Le Number Place Challenger, mentionnĂ© prĂ©cĂ©demment, et le Sudoku X du Daily Mail, une grille 6×6, appartiennent Ă  cette catĂ©gorie ;
  • 8×8 contenant des rĂ©gions 2×4 et 4×2, et oĂč les rangĂ©es, les colonnes, rĂ©gions et les diagonales principales contiennent un chiffre unique
  • une mĂ©ta-grille composĂ©e de cinq grilles 9×9 en quinconce qui se chevauchent aux coins est publiĂ©e au Japon sous le nom de Gattai 5 (qui signifie « cinq fusionnĂ©s Â») ou SamuraĂŻ. Dans le journal The Times, cette forme est appelĂ©e le Samurai Su Doku[9].
  • des grilles Ă  rĂ©gions rectangulaires : si une rĂ©gion est de dimensions L×C cases, la grille globale se dĂ©compose en C×L rĂ©gions ; les valeurs Ă  remplir vont alors de 1 Ă  C×L ;
  • Dion Church a créé une grille 3D, que le Daily Telegraph a publiĂ©e en mai 2005. Le logiciel ksudoku appelle de telle grilles roxdoku et les gĂ©nĂšre automatiquement.
  • le kamaji est une dĂ©rivation rĂ©cente de sudoku basĂ© sur le principe des sommes de chiffres.
  • irrĂ©gulier, avec des formats diffĂ©rents.
  • diagonal, avec l'obligation de caser les chiffres de 1 Ă  9 en diagonale, en plus des rĂšgles "classiques".

Au Japon, d'autres variantes sont publiĂ©es. En voici une liste incomplĂšte :

  • Grilles connectĂ©es sĂ©quentiellement : plusieurs grilles 9×9 sont rĂ©solues consĂ©cutivement, mais seul la premiĂšre a suffisamment de dĂ©voilĂ©s pour permettre de rĂ©soudre logiquement. Une fois rĂ©solue, certains chiffres sont copiĂ©s vers le suivant. Cette formule impose au joueur de faire des allers et des retours entre des grilles partiellement rĂ©solues.
  • Grilles trĂšs grandes qui consistent en de multiples grilles qui se chevauchent (habituellement 9×9). Des grilles constituĂ©es de 20 Ă  50, ou plus, sont courantes. La taille des rĂ©gions qui se chevauchent varie (deux grilles 9×9 peuvent partager 9, 18 ou 36 cellules). Souvent, il n'y a aucun dĂ©voilĂ© dans ces rĂ©gions.
  • Grilles habituelles oĂč un chiffre est membre de quatre groupes, au lieu des trois habituels (rangĂ©es, colonnes et rĂ©gions) : les chiffres situĂ©s aux mĂȘmes positions relatives dans une rĂ©gion ne doivent pas correspondre. Ces grilles sont habituellement imprimĂ©es en couleur, chaque groupe disjoint partageant une couleur pour faciliter la lecture.

La trousse de jeux pour participer au World Puzzle Championship de 2005 contient une variante intitulĂ©e Digital Number Place : plutĂŽt que de contenir des dĂ©voilĂ©s, la plupart des cellules contiennent un chiffre partiellement dessinĂ© qui emprunte Ă  la graphie de l'affichage Ă  sept segments.

Le 31 aoĂ»t 2005, The Times a entamĂ© la publication du Killer Su Doku, aussi nommĂ© Samunamupure (qui signifie « lieu de sommation Â»), lequel indique la somme de cellules regroupĂ©es, ce qui ajoute un supplĂ©ment de difficultĂ© dans la recherche de la solution, bien que cela puisse aider Ă  rĂ©soudre. Les autres rĂšgles s'appliquent.

[modifier] Variantes alphabétiques

Des variantes alphabétiques, qui utilisent des lettres plutÎt que des chiffres, sont aussi publiées. The Guardian les appelle Godoku et les qualifie de démoniaques. Knight Features lui préfÚre le terme Sudoku Word[10]. Le Wordoku[11] de Top Notch dévoile les lettres, dans le désordre, d'un mot qui court du coin gauche supérieur au coin droit inférieur. Un joueur ayant une bonne culture peut le trouver et utiliser sa découverte pour avancer vers la solution.

En français, cette variante alphabĂ©tique porte divers noms comme Sudoku lettres, Mokitu (TĂ©lĂ© 7 jours) ou Mysmo (LibĂ©ration). Certaines grilles se limitent aux mots ne comportant que des lettres diffĂ©rentes. D'autres acceptent des mots comportant plusieurs fois la mĂȘme lettre auquel cas elle a Ă  chaque fois une graphie diffĂ©rente, par exemple : MAHaRADJa.

Le Code Doku[12] conçu par Steve Schaefer contient une phrase complĂšte, alors que le Super Wordoku[13] de Top Notch contient deux mots de neuf lettres, chacun se trouvant sur l'une des diagonales principales. Ces jeux ne sont pas considĂ©rĂ©s comme de vrais sudoku par les puristes, car la logique n'est pas suffisante pour les rĂ©soudre, mĂȘme s'ils ont une solution unique. Top Notch affirme que ces jeux sont conçus de façon Ă  bloquer les solutions composĂ©es par des logiciels de rĂ©solution automatique.

Article dĂ©taillĂ© : Mojidoku.

[modifier] Nombre de grilles complĂštes possibles

Il est évident que le nombre de grilles complÚtes est inférieur au nombre de façons de placer neuf chiffres 1, neuf chiffres 2..., neuf chiffres 9 dans une grille de 81 cases. Le nombre de grilles est donc trÚs inférieur à

 \frac{81!}{9!^9} \approx 5,31306887 \times 10^{70}

En effet, dans ce décompte, on ne tient compte d'aucune des contraintes d'unicité.

Le nombre de grilles complÚtes possibles est également inférieur au nombre de carrés latins de cÎté 9.

Enfin, le nombre de grilles complÚtes possibles est inférieur à 9!9 qui correspond au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.

En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvĂ©[14] que ce nombre de grilles Ă©tait de :[15]

\mathbb{N} = 6\;670\;903\;752\;021\;072\;936\;960 \approx 6,67 \times 10^{21}

Ce nombre \mathbb{N} est Ă©gal Ă  :

9!×722×27×27 704 267 971

Le dernier facteur est un nombre premier. Ce résultat a été prouvé grùce à une recherche exhaustive. Frazer Jarvis a ensuite considérablement simplifié la preuve grùce à une analyse détaillée. La démonstration a été validée de maniÚre indépendante par Ed Russell. Jarvis et Russell ont par la suite montré qu'en tenant compte des symétries, il y avait 5 472 730 538 solutions[16].

Quant au problĂšme suivant, il semble non rĂ©solu : si on s'intĂ©resse au nombre de problĂšmes proposables, ce nombre est inconnu ; en revanche, on sait qu'il est nettement plus important que le nombre \mathbb{N} indiquĂ© ci-dessus car il existe de trĂšs nombreuses façons de prĂ©senter des grilles initiales dont la solution (unique) conduit Ă  la mĂȘme grille terminĂ©e (complĂšte) (en revanche, il est facile de montrer, sur certains exemples de grilles complĂštes, Ă  quel point on peut, pour une mĂȘme grille complĂšte, prĂ©senter des grilles initiales de difficultĂ©s tout Ă  fait contrastĂ©es, depuis les grilles pour dĂ©butants jusqu'aux grilles dites diaboliques ; il est en tout cas trĂšs facile, connaissant une grille initiale diabolique, de fabriquer une grille pour dĂ©butant dont la solution unique complĂšte soit identique Ă  celle de la grille diabolique choisie !).

Autre problĂšme non rĂ©solu : Ă  cette date, aucun rĂ©sultat n'existe sur le nombre de grilles complĂštes dans un super sudoku (grille 16 × 16).

Le problÚme de savoir combien de cases initiales remplies sont nécessaires pour conduire à une solution unique est, à ce jour, sans réponse sûre. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie. [17]'[18]. Rien ne dit que ce ne soit pas possible avec moins de nombres.

Enfin, Gordon Royle considĂšre, Ă  juste titre, que deux rĂ©solutions sont considĂ©rĂ©es comme diffĂ©rentes si elles ne peuvent pas ĂȘtre transformĂ©es l'une en l'autre (ou l'inverse) grĂące Ă  une combinaison quelconque des six opĂ©rations suivantes :

  1. permutations des 9 nombres
  2. échange des lignes avec les colonnes (transposition)
  3. permutation des lignes dans un seul bloc
  4. permutation des colonnes dans un seul bloc
  5. permutation des blocs sur une ligne de blocs
  6. permutation des blocs sur une colonne de blocs

On remarque l'analogie avec les opérations matricielles en algÚbre linéaire.

[modifier] Mathématiques

Le problĂšme de placer des chiffres sur une grille de nÂČ×nÂČ comprenant n×n rĂ©gions est prouvĂ© NP-complet[19].

Le problĂšme de la rĂ©solution de tout sudoku peut ĂȘtre formalisĂ© de façon Ă©quivalente par un problĂšme de coloration de graphe : le but, dans la version classique du jeu, est d'appliquer 9 couleurs sur un graphe donnĂ©, Ă  partir d'un coloriage partiel (la configuration initiale de la grille). Ce graphe possĂšde 81 sommets, un par cellule. Chacune des cases du sudoku peut ĂȘtre Ă©tiquetĂ©e avec un couple ordonnĂ© (x, y), oĂč x et y sont des entiers compris entre 1 et 9. Deux sommets distincts Ă©tiquetĂ©s par (x, y) et (x’, y’) sont reliĂ©s par une arĂȘte si et seulement si :

  • x = x’ (les deux cellules appartiennent Ă  la mĂȘme ligne) ou,
  • y = y’ (les deux cellules appartiennent Ă  la mĂȘme colonne) ou,
  • \left\lceil {\frac{x-1}{3}} \right\rceil = \left\lceil \frac{x'-1}{3} \right\rceil et \left\lceil \frac{y-1}{3} \right\rceil = \left\lceil \frac{y'-1}{3} \right\rceil (les deux cellules appartiennent Ă  la mĂȘme rĂ©gion). La grille se complĂšte en affectant un entier entre 1 et 9 pour chaque sommet, de façon que tous les sommets liĂ©s par une arĂȘte ne partagent pas le mĂȘme entier.


Une grille solution est aussi un carré latin. La relation entre les deux théories est désormais complÚtement connue, depuis que D. Berthier a démontré, dans "The Hidden Logic of Sudoku"[20], qu'une formule logique du premier ordre qui ne mentionne pas les blocs (ou régions) est valide pour le Sudoku si et seulement si elle est valide pour les carrés latins.

Il y a notablement moins de grilles solutions que de carrĂ©s latins, car le sudoku impose des contraintes supplĂ©mentaires (Voir ci dessus point 4 : nombre de grilles complĂštes possibles).

Le nombre maximum de dĂ©voilĂ©s sans qu'une solution unique apparaisse immĂ©diatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et que exactement deux cellules sont dans une rĂ©gion, alors il existe deux façons d'inscrire les candidats. L'opposĂ© de ce problĂšme, Ă  savoir le nombre minimum de dĂ©voilĂ©s pour garantir une solution unique, est un problĂšme non rĂ©solu, bien que des enthousiastes japonais aient dĂ©couvert une grille 9×9 sans symĂ©trie qui contient seulement 17 dĂ©voilĂ©s[21]'[22], alors que 18 est le nombre minimum de dĂ©voilĂ©s pour les grilles 9×9 symĂ©triques.

Article dĂ©taillĂ© : MathĂ©matiques du Sudoku.

[modifier] RĂšgles et terminologie

La plupart du temps, le jeu est proposĂ© sous la forme d'une grille de 9×9, et composĂ© de sous-grilles de 3×3, appelĂ©es « rĂ©gions Â». Quelques cellules contiennent des chiffres, dits « dĂ©voilĂ©s Â». Le but est de remplir les cellules vides, un chiffre dans chacune, de façon Ă  ce que chaque rangĂ©e, chaque colonne et chaque rĂ©gion soient composĂ©es d'un seul chiffre allant de 1 Ă  9. En consĂ©quence, chaque chiffre dans la solution apparaĂźt une seule fois selon les trois « directions Â», d'oĂč le nom « chiffre unique Â». Lorsqu'un chiffre peut s'inscrire dans une cellule, on dit qu'il est candidat.

[modifier] Méthode de résolution

La région en haut à droite doit contenir un 5. En éliminant les rangées et les colonnes en regard qui contiennent un 5, le joueur élimine toutes les cellules vides qui ne peuvent contenir ce 5. Il ne reste donc qu'une seule cellule d'accueil, en vert.
La région en haut à droite doit contenir un 5. En éliminant les rangées et les colonnes en regard qui contiennent un 5, le joueur élimine toutes les cellules vides qui ne peuvent contenir ce 5. Il ne reste donc qu'une seule cellule d'accueil, en vert.

La mĂ©thode de rĂ©solution (voir l'article dĂ©diĂ©) se ramĂšne Ă  trois procĂ©dĂ©s : recherche, candidature et analyse. L'approche de l'analyse peut ĂȘtre diffĂ©rente selon les concepts qu'elle met en Ɠuvre et selon les reprĂ©sentations sur lesquelles elle s'appuie.

[modifier] Recherche

La recherche est faite au dĂ©but du jeu et pĂ©riodiquement pendant le remplissage de la grille. Plusieurs recherches sont souvent nĂ©cessaires entre deux moments d'analyse. Cette recherche fait appel Ă  deux techniques simples :

  • RĂ©duction par croix : il s'agit, pour chaque chiffre, d'Ă©liminer les cellules oĂč il ne peut pas se trouver. Pour cela, le chercheur trace un trait, imaginaire, sur chaque colonne et chaque ligne oĂč le chiffre apparaĂźt dĂ©jĂ . Les cases qui ne sont pas traversĂ©es par un trait sont celles oĂč le chiffre peut encore ĂȘtre insĂ©rĂ©. Cette mĂ©thode peut ĂȘtre utilisĂ©e pour remplir les cellules « les plus simples Â» en premier. Pour gagner du temps, le chercheur peut commencer par les chiffres les plus nombreux parmi les dĂ©voilĂ©s, mais il est important de l'appliquer Ă  chaque chiffre. Pour minimiser le temps de recherche aux autres Ă©tapes, cette Ă©tape doit ĂȘtre faite de façon systĂ©matique, en vĂ©rifiant pour tous les chiffres.
  • DĂ©compte de 1 Ă  9 pour chaque rĂ©gion, chaque rangĂ©e et chaque colonne. Cette Ă©tape permet de trouver les chiffres manquants (Le faire selon le dernier chiffre trouvĂ© peut rendre plus rapide la recherche). Dans les grilles difficiles, le chiffre Ă  inscrire peut ĂȘtre dĂ©terminĂ© en faisant un dĂ©compte inversĂ©, c'est-Ă -dire en tentant de trouver les chiffres qui ne peuvent apparaĂźtre dans la cellule, ce qui permet de connaĂźtre les chiffres candidats.

Les joueurs experts recherchent les « contingences Â» pendant la recherche, c'est-Ă -dire qu'ils tentent de dĂ©terminer les cellules candidates (au nombre de deux ou trois) pour un chiffre en particulier. Quand ces cellules sont toutes dans la mĂȘme rangĂ©e (ou colonne), et une rĂ©gion, elles sont mises Ă  profit pendant la rĂ©duction par croix et le dĂ©compte (voir (en) exemple). Les grilles les plus difficiles demandent de reconnaĂźtre les multiples contingences, souvent dans des directions diffĂ©rentes ou aux intersections. Ce qui oblige les joueurs Ă  inscrire les candidats (mĂ©thode dĂ©crite ci-dessous).

Les grilles que l'on peut résoudre par la réduction par croix seulement sont considérées comme faciles, les plus difficiles exigent de faire appel à d'autres techniques.

[modifier] Candidature

Un exemple de la notation pointée

La recherche cesse lorsque aucun nouveau chiffre n'est inscrit. C'est Ă  partir de ce moment qu'une autre technique doit prendre place. Plusieurs joueurs trouvent utile d'inscrire les chiffres candidats dans les cellules vides. Il y a deux notations utilisĂ©es : indicĂ©e et pointĂ©e.

  • Pour la notation indicĂ©e, les candidats sont inscrits dans une cellule, chaque chiffre occupant ou non une place prĂ©cise. L'inconvĂ©nient de cette mĂ©thode est que les journaux publient des grilles de petite taille, ce qui rend difficile l'inscription de plusieurs chiffres dans une mĂȘme cellule. Plusieurs joueurs reproduisent Ă  plus grande Ă©chelle de telles grilles ou ont recours Ă  un crayon Ă  pointe fine.
  • Pour la notation pointĂ©e, les joueurs inscrivent des points dans les cellules vides. La position relative du point indique le chiffre manquant. Par exemple, pour indiquer 1, un point apparaĂźt en haut Ă  gauche dans la cellule. Cette notation permet de jouer directement avec une grille imprimĂ©e dans un journal. Cependant, elle demande une certaine dextĂ©ritĂ©, il est possible de mal placer un point dans un moment d'inattention et une petite marque faite par erreur peut mener Ă  de la confusion. Certains joueurs prĂ©fĂšrent utiliser un stylo pour limiter les fautes.

[modifier] Analyse

Les deux thĂšmes de ce procĂ©dĂ© sont l'Ă©limination et l'hypothĂšse (ce dernier procĂ©dĂ© peut ĂȘtre Ă©vitĂ© si l'on est suffisamment entraĂźnĂ©).

  • Élimination : la recherche de la solution se fait en Ă©liminant successivement les candidats d'une cellule de façon Ă  ne retenir qu'un seul candidat. Une fois ce candidat trouvĂ©, une autre recherche devrait ĂȘtre effectuĂ©e de façon Ă  dĂ©terminer les consĂ©quences sur les autres cellules. Il y a plusieurs techniques d'Ă©limination qui s'appuient sur les rĂšgles ci-dessous, lesquelles ont d'utiles corollaires :
  1. Un ensemble donnĂ© de n cellules dans une rangĂ©e, une colonne ou une rĂ©gion, ne peut recevoir que n chiffres diffĂ©rents. Cette rĂšgle est Ă  la base de la technique d' « Ă©limination du candidat orphelin Â», discutĂ©e ci-dessous.
  2. Chaque candidat doit ultimement appartenir Ă  un modĂšle auto-consistant et indĂ©pendant. Cette rĂšgle est Ă  la base des techniques d'analyse avancĂ©es, lesquelles demandent d'inspecter l'ensemble de toutes les possibilitĂ©s pour un candidat. Il n'y a qu'un nombre fini de « circuits fermĂ©s Â» ou possibilitĂ©s de grilles « n×n Â» qui existent. Cette rĂšgle a donnĂ© naissance aux mĂ©thodes X-wing et Swordfish, entre autres. Si un tel modĂšle est identifiĂ©, alors l'Ă©limination de candidats est souvent possible.
  3. Un chiffre donné ne peut recevoir qu'une seule position dans sa case, ligne ou colonne, les autres emplacements candidats entrant en contradiction avec les éliminations déjà effectuées.
  • L'une des techniques les plus utilisĂ©es est l' « Ă©limination du candidat orphelin Â». Les cellules avec un mĂȘme ensemble de candidats sont dites couplĂ©es si le nombre de candidats dans chacune d'elle est Ă©gal au nombre de cellules qui peuvent les accueillir. Par exemple, deux cellules sont couplĂ©es si elles contiennent une paire unique de candidats (p, q) dans une rangĂ©e, une colonne ou une rĂ©gion; trois cellules sont dites couplĂ©es si elles contiennent un triplet unique de candidats (p, q, r). Ces chiffres ne peuvent apparaĂźtre ailleurs, car il y aurait conflit selon la rangĂ©e, la colonne ou la rĂ©gion. Pour cette raison, les candidats (p, q, r) qui se trouvent dans les autres cellules sont Ă  Ă©liminer. Ce principe vaut avec des sous-ensembles de candidats : si trois cellules ont seulement { (p, q, r), (p, q), (q, r) }, ou { (p, r), (q, r), (p, q) }, tous les candidats de cet ensemble qui se trouvent dans les autres cellules sont Ă  Ă©liminer.
    • Un deuxiĂšme principe dĂ©coule du principe prĂ©cĂ©dent. Si le nombre de cellules dans une rangĂ©e, une colonne ou une rĂ©gion, est Ă©gal Ă  la taille d'un ensemble de candidats (on parle alors de groupe de multiples numĂ©riquement liĂ©s), les cellules et les chiffres sont couplĂ©s et seulement ces chiffres apparaĂźtront dans les cellules. Tous les autres candidats sont Ă  Ă©liminer. Par exemple, si (p, q) peut seulement apparaĂźtre dans deux cellules (d'une rangĂ©e, d'une colonne ou d'une rĂ©gion), les autres candidats sont Ă  Ă©liminer.

Le premier principe s'appuie sur le concept de « chiffres couplĂ©s uniquement Â», alors que le second s'appuie sur le concept de « cellules couplĂ©es uniquement Â». Les techniques avancĂ©es s'appuient sur ces concepts et englobent de multiples rangĂ©es, de multiples colonnes et de multiples rĂ©gions.

  • Avec l'approche par hypothĂšse, une cellule avec seulement deux candidats est choisie et l'un des deux chiffres est inscrit dans la cellule. Les Ă©tapes prĂ©cĂ©dentes sont rĂ©pĂ©tĂ©es et mĂšnent soit Ă  une contradiction (chiffre dupliquĂ© ou cellule sans candidat), soit Ă  une proposition valide. Évidemment, dans le cas d'une contradiction, le deuxiĂšme chiffre fait partie de la solution. L'algorithme de Nishio est une forme Ă©purĂ©e de cette approche : Pour chaque candidat d'une cellule, est-ce qu'insĂ©rer un chiffre en particulier prĂ©vient l'inscription de ce candidat ailleurs dans la grille ? Si la rĂ©ponse est oui, alors le candidat est Ă©liminĂ©.

L'approche par hypothĂšse demande d'utiliser un crayon et une gomme Ă  effacer. Les puristes la rejettent, car elle est une approche par essais et erreurs, alors que la plupart des grilles publiĂ©es font appel Ă  la logique seulement pour ĂȘtre rĂ©solues. Cependant, cette approche a le mĂ©rite de souvent mener Ă  la solution plus rapidement.

C'est Ă  chaque joueur de trouver une mĂ©thode qui lui donne les meilleurs rĂ©sultats. Certains dĂ©velopperont une mĂ©thode qui rĂ©duit les inconvĂ©nients des propositions prĂ©cĂ©dentes. Par exemple, certains trouveront ennuyeux de devoir inscrire tous les candidats dans toutes les cellules. L'approche par hypothĂšse demande d'ĂȘtre organisĂ©. L'idĂ©al est de trouver une façon de faire qui minimise le dĂ©compte, le nombre de candidats et le nombre d'hypothĂšses.

En principe, ces trois procĂ©dĂ©s (candidat unique par croisement+candidat unique par comptage et Ă©limination+groupes indĂ©pendants de multiples numĂ©riquement liĂ©s traitĂ©s selon une ou plusieurs dimensions) suffisent pour rĂ©ussir intĂ©gralement une grille. Mais il y a des situations oĂč il semble qu’il n’est plus possible d’avancer. Voici un dĂ©but d’exemple :

Vous avez trouvĂ© Ă  partir des chiffres dĂ©jĂ  rĂ©vĂ©lĂ©s selon les rĂ©gions et les colonnes, les multiples 123-12-1456-479-23-56-2456-178-89 Ă©crits sur toute une ligne pour une certaine grille. D’abord, on relĂšve les 123, 12 et 23 numĂ©riquement liĂ©s ; trois multiples formĂ©s des trois chiffres 1, 2 et 3, qui vont occuper chacun l’une des trois cases. Donc la ligne se simplifie en 123-12-456-479-23-56-456-78-89. Ensuite, on considĂšre les multiples 456, 56 et 456 qui sont aussi numĂ©riquement liĂ©s, mais leur groupe est indĂ©pendant de celui des multiples formĂ©s Ă  la base des chiffres 1, 2 et 3.Pour la mĂȘme raison, la ligne se simplifie en 123-12-456-79-23-56-456-78-89. Il reste donc trois multiples 79, 78 et 89 qui sont numĂ©riquement liĂ©s, mais constituent un troisiĂšme groupe indĂ©pendant des deux premiers. À ce niveau, on dira que l’on a rempli la ligne de façon optimale. Les simplifications ainsi effectuĂ©es vont se rĂ©percuter sur les rĂ©gions, les colonnes puis sur les autres lignes puis de nouveau sur les rĂ©gions, les colonnes et les lignes si l’on arrive Ă  dĂ©gager chaque fois, de nouveaux groupes indĂ©pendants. S’il reste toujours des cases sans candidat unique, alors, on pourra attaquer par traitement des multiples en considĂ©rant deux dimensions Ă  la fois; colonnes X lignes (principe de l'unicitĂ©, X-Wing par exemple), colonnes X rĂ©gions (doublons, jumeaux par exemple), lignes X rĂ©gions (idem). Si la solution n'apparaĂźt pas toujours, alors, dĂ©sormais, vous ĂȘtes invitĂ© Ă  utiliser les techniques de traitement Ă  trois dimensions (lignes X colonnes X rĂ©gions) dont par exemple, celles dĂ©coulant de l'utilisation des chemins (thĂ©orie basĂ©e sur la logique bivalente; il y est ou il n'y est pas).

Et si votre labeur n'aboutit pas toujours Ă  la grille-solution, alors, c’est Ă  cause de l’une des deux raisons suivantes :

  • Vous vous ĂȘtes bien appliquĂ© et vous avez rempli entiĂšrement la grille de façon optimale par des chiffres uniques dans certaines cases et par des multiples dans les autres. Mais, tous les groupes des multiples que vous avez inscrits sont indĂ©pendants. Dans ce cas, Vous avez affaire Ă  une grille prĂ©sentant plusieurs solutions ! Ce n’est pas un « bon Â» Su-Doku et le problĂšme ne devait pas ĂȘtre proposĂ©, malheureusement !
  • Toutes les cases de votre grille ont des candidats uniques ou multiples, mais, faute d’expĂ©rience, vous n’arrivez pas Ă  discerner facilement des groupes indĂ©pendants de multiples numĂ©riquement liĂ©s. Dans ce cas, vous pouvez procĂ©der par la disjonction de l’un des multiples. C’est-Ă -dire faire une hypothĂšse sur ses chiffres, et voir l’effet qui va se rĂ©percuter sur les autres multiples. Si vous avez vraiment un « bon Â» jeu de Su-Doku, alors un seul chiffre du multiple en question conduira Ă  la solution du problĂšme, tandis que pour tous les autres, on aboutira Ă  des situations de blocage ! Dans le cas contraire, le problĂšme ne mĂ©rite pas d’ĂȘtre posĂ© ! Par principe !

Mais le fait de formuler une hypothĂšse sur le chiffre Ă  choisir parmi ceux d'un multiple donnĂ© ne garantit pas toujours la simplification des autres multiples et risque d'aboutir sur de nouvelles hypothĂšses Ă  faire, ce qui augmente rapidement le nombre de grilles Ă  examiner successivement! Pire encore, les grilles obtenues peuvent ĂȘtre d'un niveau mĂ©diocre et donc sans intĂ©rĂȘt intellectuel!

[modifier] Symétries généralisées et tableau de résolution étendu

Dans "La logique cachĂ©e du Sudoku", un livre en anglais ("The Hidden Logic of Sudoku"[20]) basĂ© sur une formalisation logique systĂ©matique du jeu, toutes ses symĂ©tries gĂ©nĂ©ralisĂ©es ont Ă©tĂ© explicitĂ©es, en particulier entre les lignes et les nombres, et entre les colonnes et les nombres. Une nouvelle mĂ©thode de rĂ©solution a Ă©tĂ© dĂ©veloppĂ©e, basĂ©e sur leur exploitation systĂ©matique. Une grille de rĂ©solution Ă©tendue (comportant trois grilles au lieu d'une seule) a Ă©tĂ© conçue, qui fait apparaĂźtre les liens de conjugaison comme des cases Ă  deux candidats et peut faciliter l'application de la mĂ©thode (sans ĂȘtre absolument nĂ©cessaire). De la sorte, les sous-ensembles cachĂ©s ainsi que les X-wings, Swordfish et Jellysfish, mais pas TPU (la technique dĂ©coulant du principe de l'unicitĂ© de la solution), apparaissent tous comme de simples Paires, Triplets ou Quadruplets. Dans un cadre gĂ©nĂ©ral pour traiter des chaĂźnes, ces symĂ©tries ont Ă©tĂ© utilisĂ©es pour introduire de nouvelles rĂšgles de rĂ©solution, comme les chaĂźnes xy cachĂ©es. Cette mĂ©thode a Ă©tĂ© implĂ©mentĂ©e dans un solveur, SudoRules, basĂ© sur des techniques d'Intelligence Artificielle et simulant un joueur humain.

[modifier] Grille-Conjointe; changer de situation pour résolution plus poussée

La stratégie des symétries généralisées entre lignes, colonnes et chiffres omet un quatriÚme angle d'attaque pour résoudre d'autres cas de figures plus complexes: considérer une région et un chiffre et repérer la bonne cellule. Farid MITA, l'auteur du manuel "Stratégie de résolution d'une grille de Sudoku"[23] propose l'utilisation de la Grille-Conjointe; c'est un tableau de 9 rangées horizontales (une rangée par chiffre) croisées avec 9 rangées verticales (une rangée par région) dont les cellules reçoivent les coordonnées de la case associée au chiffre et région donnés dans la grille normale du problÚme proposé. De par sa construction, la grille-conjointe englobe les techniques de résolution les plus efficaces dont X-wing, Swordfish et bien d'autres inconnues par le commun des joueurs, mais "ignore" la TPU (technique découlant du principe de l'unicité de la solution), comme d'ailleurs la stratégie des Symétries généralisées. L'auteur suggÚre de classer la TPU dans une catégorie à part!

[modifier] Stratégie des chemins; résoudre des cas plus complexes

Si l'adoption du tableau Ă©tendu de rĂ©solution utilisant les symĂ©tries gĂ©nĂ©ralisĂ©es et/ou de la grille-conjointe permettent de rĂ©soudre les grilles frĂ©quemment proposĂ©es dans les journaux, magazines et sites, il existe bien des cas de figure oĂč ces deux stratĂ©gies butent sans pouvoir atteindre la solution finale. Avouons que ces deux stratĂ©gies ont le mĂ©rite de nous faire dĂ©couvrir de nouveaux procĂ©dĂ©s de rĂ©solution mettant en jeu deux dimensions (lignes X colonnes, lignes X rĂ©gions et colonnes X rĂ©gions) sur la grille-problĂšme normale ou initiale, alors qu'il ne met en oeuvre qu'une seule dimension (rangĂ©e horizontale ou verticale dans chacun des deux tableaux additionnels de la stratĂ©gie des symĂ©tries gĂ©nĂ©ralisĂ©es ou sur la grille-conjointe) dont le traitement est relativement facile Ă  mener manuellement et Ă  programmer sur les logiciels (Ă©limination Ă  cause des multiples nues ou dĂ©voilement par dĂ©graissage de multiples).

La stratégie adoptée pour ces cas de figures plus complexes consiste à prendre en considération les trois dimensions à la fois (lignes X colonnes X régions). Il faut pouvoir " sauter" d'une région à une autre, à travers les cases, en utilisant des "passerelles" matérialisées soit par une ligne, une colonne ou une région. Bref, il faut se créer des "chemins" entre les différentes cases. Ainsi, on reconnaßtra des procédés similaires à ceux déjà utilisés par traitement à deux dimensions dont le X-Wing par exemple (les sommets ne sont plus ceux d'un rectangle, mais parmi ceux d'un polygone).

Précisons que cette stratégie est basée sur la logique bivalente (pour un chiffre N fixé et une case donnée de multiples, p:"N est la valeur" et non(p): "N n'est pas la valeur").

Vu d'un certain angle, il s'agit de faire superposer deux ou plusieurs grilles sur la mĂȘme grille-problĂšme initiale, de faire une conjugaison logique des diffĂ©rentes propositions (concrĂ©tisĂ©es par des chemins) et de dĂ©terminer celles des grilles qui aboutissent Ă  une contradiction avec l'une des rĂšgles qui rĂ©gissent le jeu sudoku. C'est donc comme si l'on procĂ©dait par formulation par hypothĂšse, mais d'une maniĂšre "cachĂ©e" ! Il faut avouer que cette maniĂšre de faire procure plus de plaisir Ă  jouer et Ă  appliquer des procĂ©dĂ©s que d'Ă©mettre des hypothĂšses pour obtenir des grilles "pauvres" au niveau intellectuel.

[modifier] Une technique « Ă  part Â» : principe de l’unicitĂ© de la solution

Il existe une classe de techniques, bien qu’en mettant en jeu deux dimensions seulement (lignes X colonnes, lignes X rĂ©gions ou colonnes X rĂ©gions) ne peuvent ĂȘtre retrouvĂ©es ni traduites d’une certaine maniĂšre dans le tableau Ă©tendu de rĂ©solution ou sur la grille-conjointe. On cite comme exemple, la technique dĂ©coulant du principe de l’unicitĂ© de la solution. Le cas de figure est le suivant : dans quatre cases, sommets d’un rectangle, on trouve trois mĂȘme paires ab, ab, ab et cette mĂȘme paire mĂȘlĂ©e avec d’autre chiffres x,
..,z sous forme abx
.z. Alors, en vertu du principe de l’unicitĂ© de la solution, dans ce quatriĂšme sommet, on peut chasser sans risque les deux chiffres a et b. Car au cas contraire, la grille aboutirait Ă  au moins deux solutions.

Dans certains cas, cette technique peut ĂȘtre utilisĂ© sans le savoir, s’il est possible de suivre un chemin (ici une boucle) de l’un des sommets vers lui-mĂȘme. Parfois, on est amenĂ© Ă  utiliser cette mĂȘme technique sur des polygones au lieu d’un rectangle ; une gĂ©nĂ©ralisation est donc possible, mais utilisant la stratĂ©gie des chemins.

[modifier] StratĂ©gie de dernier recours : formulation claire et nette des hypothĂšses

Certains journaux, magazines, sites et logiciels nous livrent des grilles dites « diaboliques Â». En gĂ©nĂ©ral, il n’en est rien ! Ces grilles peuvent ĂȘtre rĂ©solues par les techniques mises au point jusqu’à ce jour. Une grande majoritĂ© peut ĂȘtre remplie « mentalement Â» mĂȘme !

Bref, une dĂ©finition s’impose : une grille diabolique est celle qui ne peut ĂȘtre rĂ©solue par aucun des procĂ©dĂ©s mis au point jusqu’à ce jour, sauf par la formulation d’une ou de plusieurs hypothĂšses sur les chiffres Ă  mettre dans une ou plusieurs casescases, l’unicitĂ© de la solution pour la grille Ă©tant bien-entendu requise.

DĂ©sormais, c’est le seul moyen pour aboutir Ă  la solution, en attendant l’élaboration de nouveaux procĂ©dĂ©s « manuels Â».

[modifier] Solutions logicielles

Pour un informaticien, programmer la recherche d'une solution par le biais des contingences ou de multiples contingences (tel qu'exigé pour les problÚmes les plus difficiles) est une tùche relativement simple. Un tel programme imite un joueur humain qui recherche une solution sans recourir au hasard.

Il est aussi relativement simple de concevoir un algorithme de recherche par backtracking. De façon habituelle, il suffit Ă  l'algorithme de choisir 1 pour la premiĂšre cellule, puis 2 pour la prochaine, ainsi de suite tant qu'aucune contradiction n'apparaĂźt. Lorsqu'une contradiction apparaĂźt, l'algorithme essaie une autre valeur pour la cellule qui amĂšne la contradiction. Une fois toutes les possibilitĂ©s Ă©puisĂ©es pour cette cellule, l'algorithme « revient sur ses pas Â» et recommence avec l'avant-derniĂšre cellule.

Bien que cet algorithme ne soit pas trĂšs efficace en thĂ©orie, il trouvera une solution s'il dispose de suffisamment de temps. Une grille 9×9 est habituellement rĂ©solue en moins de trois secondes avec un ordinateur personnel moderne qui a recours Ă  un interprĂ©teur, et en quelques millisecondes avec un langage compilĂ©. Cependant, il existe des grilles qui sont particuliĂšrement difficiles Ă  rĂ©soudre par backtracking.Algorithmics of Sudoku#Solving sudokus by a brute-force algorithm

Cependant, un programme plus efficace s'appuiera sur les candidats potentiels pour chaque cellule, éliminant les candidats impossibles jusqu'à ce qu'un seul chiffre demeure. Connaissant ce chiffre, il peut trouver un autre chiffre pour une autre cellule, et ainsi de suite.

Une alternative au backtracking est de recourir aux mĂ©thodes prĂ©conisĂ©es par la programmation logique, telle qu'implantĂ©e par Prolog. Dans ce cas, le concepteur fournit au programme les contraintes de la grille (un chiffre par rangĂ©e, par colonne et par rĂ©gion ; les chiffres dĂ©voilĂ©s) ; ce programme prendra les dĂ©cisions pour rĂ©soudre le problĂšme. Sachant que la plupart des grilles ont une solution unique, la recherche est certaine d'aboutir.

Donald Knuth a mis au point un algorithme qui fait appel aux listes doublement chaßnées (les dancing links [24]), et qui se révÚle trÚs efficace pour résoudre ce type de problÚme. Il est démontré que cet algorithme est tout indiqué pour la résolution d'un Sudoku, ne prenant que quelques millisecondes. Grùce à sa vitesse, il est maintenant préféré par la plupart des concepteurs logiciels.

[modifier] Degrés de difficulté

Les grilles publiĂ©es mentionnent souvent un degrĂ© de difficultĂ©. Celui-ci est calculĂ© selon la facilitĂ© de rĂ©solution par une mĂ©thode logique. Étonnamment, le nombre de dĂ©voilĂ©s n'a presque aucune incidence sur la difficultĂ© d'une grille. Des grilles avec un petit nombre de chiffres peuvent ĂȘtre facilement rĂ©solues, alors que d'autres qui contiennent un nombre plus Ă©levĂ© de dĂ©voilĂ©s que la moyenne peuvent ĂȘtre trĂšs difficiles Ă  rĂ©soudre.

Connaissant la complexité des rÚgles, les logiciels de résolution automatique peuvent estimer la difficulté pour un humain à trouver une solution. Cette estimation est en général suffisamment précise pour permettre aux éditeurs de la fournir. Quelques éditeurs en ligne fournissent également cette estimation.

Plusieurs facteurs influent sur la difficulté de ces problÚmes . L'équation de base tient compte modulo une certaine pondération:

  • du nombre de cellules Ă  remplir ;
  • du nombre de cellules remplies par Ă©limination ;
  • du nombre de groupes indĂ©pendants de multiples numĂ©riquement liĂ©s, traitables suivant une seule dimension; rĂ©gion, ligne ou colonne ;
  • du nombre de groupes indĂ©pendants de multiples numĂ©riquement liĂ©s, traitables suivant deux dimensions Ă  la fois; rĂ©gion X ligne, rĂ©gion X colonne ou colonne X ligne  ;
  • du nombre de groupes indĂ©pendants de multiples numĂ©riquement liĂ©s, traitables suivant les trois dimensions Ă  la fois; rĂ©gion X ligne X colonne;
  • du nombre d'hypothĂšses Ă  faire en cas de blocage momentanĂ© ;
  • du nombre d’itĂ©rations de l’heuristique de rĂ©solution ;
  • du nombre de recherches Ă  faire pour complĂ©ter la grille.

La question de la difficultĂ© est trĂšs difficile et fait l’objet de nombreux dĂ©bats dans les forums sur le Sudoku, car elle est liĂ©e aux concepts et reprĂ©sentations visuelles que chacun est prĂȘt Ă  adopter. Mais elle peut ĂȘtre complĂštement Ă©lucidĂ©e par l'adoption d'une hiĂ©rarchie (du simple au complexe) des techniques et procĂ©dĂ©s que l'on peut utiliser pour rĂ©ussir une grille, et par notre maniĂšre de jouer en observant certaines rĂšgles de handicap, comme par exemple la rĂ©solution intĂ©grale par raisonnement mental uniquement, ou l'interdiction absolue de reproduire la grille-problĂšme en plusieurs grilles en faisant des hypothĂšses, etc.

En outre, il ne faut pas confondre "le niveau du joueur" avec "le degré de difficulté d'une grille". Certains joueurs sont capables de réussir une grille en raisonnant mentalement, sans écrire de multiples dans les cases qui ne reçoivent par la suite, chacune, que le bon chiffre, alors que d'autres peinent avec des cases présentant plusieurs candidats, ou avec plusieurs grilles provenant des hypothÚses gratuitement émises, ou élaborées selon les catégories (lignes, colonnes et régions) dont la grille-conjointe par exemple, qui englobe en fait un certain tableau étendu de résolution. C'est pourquoi on préfÚre classer les grilles-problÚmes en cinq types, au sein desquels, on retrouve différents niveaux de difficulté(voir la typologie des grilles-problÚmes de Su-Doku élaborée par Farid MITA)"[25]:

[modifier] Type 1

Utilisation des techniques simples dont « la recherche de la bonne case pour un chiffre et une rĂ©gion donnĂ©s Â» par rĂ©duction par croix, et « la recherche, du bon chiffre pour une cellule donnĂ©e Â», par dĂ©compte, bien que cette derniĂšre soit un peu plus fastidieuse que la premiĂšre. En principe, pour ce type de grilles, le raisonnement se fait mentalement, sans que l'on soit obligĂ© d'inscrire les candidats Ă©ventuels dans une cellule donnĂ©e, et le remplissage de la grille se fait progressivement en suivant l'une des innombrables pistes ou enchaĂźnements qui se prĂ©sentent. C'est ce type de grilles que vous trouvez frĂ©quemment dans les sites, journaux et magazines ou gĂ©nĂ©rĂ©es par des logiciels, classant Ă  tort certaines d'entre elles, dans la catĂ©gorie des "difficiles" ou mĂȘme "diaboliques" ! La raison en est qu'il existe une classe de grilles de type 1, vraiment difficile Ă  rĂ©ussir par calcul mental. Et donc, ne sous-estimez pas les grilles de type 1 : il y en a des "faciles", "moyennes" et mĂȘme "difficiles".

[modifier] Type 2

Utilisation des techniques permettant le traitement des cellules-Ă -candidats-multiples selon une seule dimension ; ligne, colonne ou rĂ©gion, dont « l’élimination Ă  cause des paires nues Â», «le dĂ©graissage des candidats cachĂ©s Â» et « le dĂ©graissage des paires camouflĂ©es Â». Certaines grilles de type 2 peuvent ĂȘtre rĂ©ussies, comme pour le type 1, mentalement. D’autres, d’un niveau supĂ©rieur, nĂ©cessitent que l’on inscrive, au fur et Ă  mesure, les candidats dans les cellules d’une rĂ©gion, une ligne ou une colonne, sans toutefois le faire pour toutes les cellules vides, et voir si l’on peut simplifier les multiples par l’une des trois techniques prĂ©cĂ©dentes. Les plus difficiles des grilles de ce type 2 ne se prĂȘtent Ă  la rĂ©solution qu’une fois toutes les cellules contiennent leurs candidats probables. Dans ce cas, il faut essayer d’arriver Ă  la situation optimale de la grille : dans chaque catĂ©gorie (ligne, colonne et rĂ©gion), les groupes des « multiples numĂ©riquement liĂ©s Â» doivent ĂȘtre « indĂ©pendants». D’autres techniques simples de traitement selon une seule dimension peuvent ĂȘtre utilisĂ©es, dont « l’élimination Ă  cause des triplets nus Â» et « le dĂ©graissage des triplets camouflĂ©s Â». Cette derniĂšre est plus pĂ©nible Ă  faire ! On pourra Ă©galement Ă©liminer certains chiffres par une technique simple de traitement, cette fois-ci, Ă  deux dimensions ligne X rĂ©gion ou colonne X rĂ©gion : «la rĂ©partition d'un blocs en quatre domaines complĂ©mentaires ou alternĂ©s». Donc, si vous optez pour un exercice mental, ce type de grilles vous en propose de bien difficiles. Et si vous vous permettez d’inscrire les multiples dans les cellules, vous avez lĂ  de trĂšs beaux exercices d’entraĂźnement sur la stratĂ©gie de traitement des « groupes indĂ©pendants de multiples numĂ©riquement liĂ©s Â».

[modifier] Type 3

Utilisation des techniques permettant la simplification des cellules-Ă -candidats-multiples, d’abord comme pour le type 2, selon une seule dimension ; ligne, colonne ou rĂ©gion, mais avec une taille plus grande dont « l’élimination Ă  cause des quadruplets et quintuples nus Â» et «le dĂ©graissage des quadruplets et quintuples cachĂ©s Â». ProcĂ©der par cette derniĂšre technique, qui est d’ailleurs plus fastidieuse Ă  mener, c’est en fait utiliser « l’élimination Ă  cause d’un ou de deux groupes nus Â» mais de taille infĂ©rieure !

Certaines grilles de type 3 nĂ©cessitent un traitement selon deux dimensions (lignes X colonnes, lignes X rĂ©gions et/ou colonnes X rĂ©gions) en utilisant des procĂ©dĂ©s beaucoup plus astucieux, mais justifiables dont X-Wing, Swordfish, Jellyfish, Squirmbag ou la TPU, la technique dĂ©coulant du «principe de l’unicitĂ© de la solution Â». Donc pour ce type de grilles, il ne faut pas espĂ©rer aboutir Ă  la solution rien qu’en raisonnant mentalement, sans avoir dorĂ©navant mis tous les candidats possibles dans toutes les cellules. Trois degrĂ©s de difficultĂ© sont possibles, selon la taille des groupes nus ou camouflĂ©s, mais aussi selon leur nombre.

[modifier] Type 4

La stratĂ©gie adoptĂ©e pour les grilles de ce type, prĂ©sentant des cas de figures plus complexes, consiste Ă  prendre en considĂ©ration simultanĂ©ment les trois dimensions (lignes X colonnes X rĂ©gions). Il faut donc pouvoir "sauter" d'une rĂ©gion Ă  une autre, Ă  travers les cases, en utilisant des "passerelles" matĂ©rialisĂ©es soit par une ligne, une colonne ou une rĂ©gion. Bref, il faut se crĂ©er des "chemins" entre les diffĂ©rentes cases. Ainsi, on reconnaĂźtra des procĂ©dĂ©s similaires Ă  ceux dĂ©jĂ  utilisĂ©s par traitement Ă  deux dimensions dont le X-Wing par exemple (les sommets ne sont plus ceux d'un rectangle, mais parmi ceux d'un polygone). PrĂ©cisons que cette stratĂ©gie est basĂ©e sur la logique bivalente (pour un chiffre N fixĂ© et une case donnĂ©e de multiples, p :"N est la valeur" ou non(p) : "N n'est pas la valeur").

Vu d'un certain angle, il s'agit de superposer deux ou plusieurs grilles sur la mĂȘme grille-problĂšme initiale, de faire une conjugaison logique des diffĂ©rentes propositions (concrĂ©tisĂ©es par des chemins) et de dĂ©terminer celles des grilles qui aboutissent Ă  une contradiction avec l'une des rĂšgles qui rĂ©gissent le jeu sudoku, pour dĂ©couvrir la bonne solution. C'est donc comme si l'on procĂšde par formulation par hypothĂšse, mais d'une maniĂšre dĂ©tournĂ©e ! Il faut avouer que cette maniĂšre de faire procure plus de plaisir Ă  jouer et Ă  appliquer des procĂ©dĂ©s que d'Ă©mettre des hypothĂšses pour obtenir des grilles "pauvres" au niveau intellectuel ! Utilisez des crayons de couleur. Ceux qui sont dĂ©jĂ  initiĂ©s Ă  cette technique reconnaĂźtront des grilles faciles, moyennes et mĂȘme difficiles.

[modifier] Type 5

Certains journaux, magazines, sites et logiciels nous livrent des grilles dites « diaboliques Â». Le plus souvent, il n’en est rien de tel ! Ces grilles peuvent ĂȘtre rĂ©solues par les techniques mises au point jusqu’à ce jour. Une grande majoritĂ© peut ĂȘtre remplie « mentalement Â» mĂȘme !

Bref, une dĂ©finition s’impose : une grille diabolique est celle qui ne peut ĂȘtre rĂ©solue par aucun des procĂ©dĂ©s mis au point jusqu’à ce jour, sauf par la formulation d’une ou de plusieurs hypothĂšses sur les chiffres Ă  mettre dans une ou plusieurs cases, l’unicitĂ© de la solution pour la grille Ă©tant bien-entendu requise.

DĂ©sormais, c’est le seul moyen pour aboutir Ă  la solution, en attendant l’élaboration de nouveaux procĂ©dĂ©s « manuels Â».

Signalons enfin, qu’au niveau de la construction des grilles-problĂšmes, il est frĂ©quemment plus facile d’obtenir une grille de type 1, et presque rare de tomber sur une grille de type 4 ou 5. Les logiciels Ă©laborĂ©s jusqu’à ce jour partent bien sĂ»r des diffĂ©rents procĂ©dĂ©s de rĂ©solution, pour fabriquer un problĂšme, mais le niveau souhaitĂ© baisse, hĂ©las, gĂ©nĂ©ralement d’un ou mĂȘme de deux degrĂ©s ! Statistiquement, on relĂšve que la distribution de la frĂ©quence par type tourne autour de 46%, 32%, 11%, 8% et 3%, du premier type au cinquiĂšme.

[modifier] Construction

Il semblerait que les grilles de Dell Magazines, le pionnier dans le domaine de la publication, soient générées par ordinateur. Elles sont habituellement composées de 30 chiffres dévoilés répartis au hasard. L'auteur des grilles est inconnu. Durant l'hiver 2000, Wei-Hwa Huang a affirmé qu'il était l'auteur du programme qui génÚre ces grilles; selon lui, les grilles antérieures étaient construites à la main. Le générateur serait écrit en C++ et, bien qu'il offre certaines options pour satisfaire le marché japonais (symétrie et moins de chiffres), Dell préfÚre ne pas les utiliser. Certains spéculent que Dell continue à utiliser ce programme, mais aucune preuve ne soutient leur affirmation.

Les sudoku de Nikoli, important crĂ©ateur de sudoku au Japon, sont construits Ă  la main, le nom de l'auteur apparaissant avec chaque grille publiĂ©e ; les dĂ©voilĂ©s sont toujours prĂ©sentĂ©s de façon symĂ©trique. Cet exploit est possible en connaissant Ă  l'avance l'endroit oĂč seront les dĂ©voilĂ©s et en affectant par la suite un chiffre aux cellules ainsi choisies. Le Number Place Challenger de Dell affiche aussi le nom de l'auteur. Les grilles publiĂ©es dans la plupart des journaux britanniques seraient gĂ©nĂ©rĂ©es automatiquement, mais font appel Ă  la symĂ©trie, ce qui laisserait sous-entendre qu'un humain les crĂ©e. The Guardian affirme que ses grilles sont créées Ă  la main par des Japonais, mais aucune mention de l'auteur n'est faite. Elles seraient construites par des gens de Nikoli. The Guardian a affirmĂ© que puisqu'ils sont construits Ă  la main, ils contiennent de « subtiles allusions Â» hautement improbables dans les grilles construites par ordinateur.

Il est possible de construire des grilles avec de multiples solutions et sans solution, mais celles-ci ne sont pas considérées comme d'authentiques sudoku. Comme pour les autres jeux logiques, une solution unique est requise. Une grande attention est donc nécessaire lors de la construction d'une grille, puisqu'un seul chiffre mal placé risque de rendre la résolution de celle-ci impossible.

Rappelons que le principe fondamental du Su-Doku rĂ©side dans le fait que seules sont permises comme problĂšmes Ă  rĂ©soudre, les grilles qui aboutissent Ă  une et une seule solution ! Cependant, certains sites et magazines spĂ©cialisĂ©s publient des grilles-problĂšmes proposant moins de donnĂ©es au dĂ©part et prĂ©sentant mĂȘme des symĂ©tries pouvant ĂȘtre plus attrayantes, parfois fantaisistes, mais admettant plus d’une solution. Mais, il n'y a pas que le problĂšme de l'unicitĂ© de la solution, certains joueurs expĂ©rimentĂ©s ont remarquĂ© que, pour certaines grilles, un ou plusieurs chiffres sont rĂ©vĂ©lĂ©s de façon "gratuite", car ils peuvent ĂȘtre dĂ©duits logiquement en considĂ©rant le reste des chiffres de la grille. Ce qui veut dire qu'on pouvait proposer la grille avec moins de chiffres tout en garantissant l'aboutissement Ă  la mĂȘme et unique solution. C'est une question d'optimisation des grilles-problĂšmes: moins de chiffres dont aucun ne peut ĂȘtre dĂ©duit Ă  partir des autres. C'est pourquoi, Farid MITA "[26] retient trois critĂšres pour classer les grilles-problĂšmes en Ă©nonçant: "Une grille-problĂšme est dite de bonne qualitĂ© si d'abord, elle aboutit Ă  une seule solution, ensuite si elle est irrĂ©ductible et enfin, si sa rĂ©solution ne nĂ©cĂ©ssite Ă  aucun moment la formulation d'hypothĂšse."

[modifier] Voir aussi

Pages sur ce thĂšme sur les projets Wikimedia :

[modifier] Articles connexes

Présentation globale et détaillée des diverses méthodes de résolution d'un sudoku
Mathématiques du Sudoku


Hors origine japonaise

  • Nombres flĂ©chĂ©s
  • CarrĂ© latin
  • Ă©nigmes gĂ©omĂ©triques.

Créateurs et éditeurs de jeux

  • Michael Mepham
  • Wayne Gould
  • Nikoli
  • Dell Magazines

[modifier] Liens externes

[modifier] Bibliographie

  • PrĂ©cis de sudoku, Narendra Jussien, HermĂšs Lavoisier, 2006, 188 pages (ISBN 2-7462-1559-4)
  • The Hidden Logic of Sudoku, Denis Berthier, Lulu Publishers, May 2007, 384 pages (ISBN 978-1-84753-472-9)

[modifier] Sources

[modifier] Notes et références

  1. ↑ CarrĂ©s magiques en Chine
  2. ↑ Origine retrouvĂ©e dans les journaux français dans les annĂ©es 1890 jusque vers les annĂ©es 1930, relevĂ©e dans un article britannique du Times.
  3. ↑ (en) http://www.mathsisfun.net/SingleNumber.sit
  4. ↑ (en) http://www.mathsisfun.net/SingleNumber.prc
  5. ↑ Walter T. Federer. Experimental design: theory and application. Macmillan, New York, 1955, 544 + 47 p.
  6. ↑ Pierre Dagnelie. Avant le sudoku: le carrĂ© latin magique. Document PDF, 2006, 4 p.
  7. ↑ (en) http://www.guardian.co.uk/g2/story/0,,1482817,00.html
  8. ↑ (en) [http://www.skyone.co.uk/programme/pgefeature.aspx?pid=48&fid=129
  9. ↑ (en) http://sudoku.top-notch.co.uk/gattai5.asp
  10. ↑ (en) http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html
  11. ↑ (en) [http://sudoku.top-notch.co.uk/wordoku.asp
  12. ↑ (en) http://www.mathrec.org/sudoku
  13. ↑ (en) http://sudoku.top-notch.co.uk/superwordoku.asp
  14. ↑ Sudoku enumeration problems
  15. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/ et la sĂ©quence A107739 de l'OEIS
  16. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et la sĂ©quence A109741 de l'OEIS
  17. ↑ ăƒ—ăƒ­ă‚°ăƒ©ăƒŸăƒłă‚°ăƒ‘ă‚șăƒ«é›‘è«‡ă‚łăƒŒăƒŠăƒŒ
  18. ↑ Minimum Sudoku
  19. ↑ (en) http://www.phil.uu.nl/~oostrom/cki20/02-03/japansepuzzles/ASP.pdf
  20. ↑ a  b  Berthier, Denis : The Hidden Logic of Sudoku, Lulu Publishers (2007-05-16). ConsultĂ© le 2007-05-16.
  21. ↑ (en) http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
  22. ↑ (en) http://www.csse.uwa.edu.au/~gordon/sudokumin.php
  23. ↑ Mita, Farid : StratĂ©gie de rĂ©solution d'une grille de Sudoku, BibliothĂšque Nationale du Maroc, N° dĂ©pĂŽt lĂ©gal 2006/1875 (2006-07-31).
  24. ↑ Knuth: Preprints
  25. ↑ Mita, Farid : Une typologie des grilles-problùmes de Su-Doku.
  26. ↑ Mita, Farid : RĂ©duction des grilles de Su-Doku.



wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.