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 par l’AmĂ©ricain Howard Garns, mais 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 la 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 × 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)

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 Magazines, 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 appelons 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

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 6×6, Ă  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 9×9 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 Palm OS[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).

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 × 3 parcelles, dans chacune des six lignes et dans chacune des six colonnes. Il s’agit strictement d’un sudoku 6 × 6.

Le sudoku classique n’est donc rien d’autre qu’un carrĂ© latin magique 9 × 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 britannique 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 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.
  • En 2006, AurĂ©lie DelbĂšque et Olivier Delbeke ont publiĂ© la premiĂšre grille 3D en 8×8×8, ils l’ont appelĂ© Kuboku[10].
  • 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[11]. Le Wordoku[12] 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[13] conçu par Steve Schaefer contient une phrase complĂšte, alors que le Super Wordoku[14] 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Ă©[15] que ce nombre de grilles Ă©tait de :[16]

\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[17].

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[18],[19]. 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] 16 RĂ©vĂ©lĂ©s ?

Exemple de sudoku ne comportant que 17 rĂ©vĂ©lĂ©s (avec sa solution prĂ©sentĂ©e sous forme d’animation)

Un rĂ©vĂ©lĂ© Ă©tant une case dont le contenu est visible sur une grille de Sudoku, se pose le problĂšme de leur nombre minimal. Aujourd’hui on sait qu’il existe un trĂšs grand nombre de problĂšmes comportant 17 rĂ©vĂ©lĂ©s (voir un exemple ci-contre avec sa solution) mais on ne sait pas s’il est possible d’en dĂ©finir un ne comportant que 16 rĂ©vĂ©lĂ©s.

[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[20].

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[21], 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 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[22],[23], 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] Méthodes de résolution utilisées par les joueurs

[modifier] Remarques préliminaires

1) Il existe de nombreuses approches de la résolution des Sudokus, dont certaines ne sont praticables que par ordinateur. Il ne sera question ici que des méthodes utilisées par les joueurs.

2) Il ne s’agit pas de donner une liste exhaustive de ces mĂ©thodes (ce qui nĂ©cessiterait un livre volumineux), mais un simple aperçu. De nombreuses variantes et extensions existent, comme les poissons Ă  nageoires (finned fish), trop spĂ©cialisĂ©es pour ĂȘtre dĂ©taillĂ©es ici.

3) Quelles mĂ©thodes de rĂ©solution sont-elles admissibles par un joueur ? Toute rĂ©ponse Ă  cette question ayant une composante subjective, ne pas reconnaĂźtre d’emblĂ©e ce fait ne pourrait que conduire Ă  des querelles stĂ©riles. La plupart des joueurs refusent les essais et erreurs, ou hypothĂšses.

4) Il existe un site de rĂ©fĂ©rence, Sudopedia, prĂ©sentant de maniĂšre consensuelle le vocabulaire standard du Sudoku et les rĂšgles de rĂ©solution les plus connues. En anglais uniquement, il fonctionne selon les mĂȘmes principes que Wikipedia.

5) La notion de candidat n’est pas inhĂ©rente au problĂšme du Sudoku, mais doit ĂȘtre introduite par le joueur pour mettre en Ɠuvre la plupart des mĂ©thodes de rĂ©solution. Lorsqu’un chiffre n’est pas a priori impossible dans une cellule, on dit qu’il est candidat. Alors que les dĂ©voilĂ©s sont les donnĂ©es initiales fixes d’un puzzle, l’ensemble des candidats Ă©volue au cours du processus de rĂ©solution. Il ne peut que diminuer ; et cela se produit lorsqu’on a dĂ©montrĂ© (par les diverses mĂ©thodes dĂ©crites plus bas) qu’un candidat (qu’on ne savait jusque lĂ  pas encore impossible) est en fait impossible. Les fondements logiques formels de cette notion (qui n’est pas aussi Ă©vidente qu’il paraĂźt) ont Ă©tĂ© dĂ©finis et Ă©tudiĂ©s en dĂ©tail dans « La logique cachĂ©e du Sudoku Â», un livre en anglais (The Hidden Logic of Sudoku[21])) ; ils font appel Ă  la logique Ă©pistĂ©mique. L’article From Constraints to Resolution Rules, Part I: Conceptual Framework[24], librement disponible sur les pages web de son auteur, expose aussi cette logique dans le cadre gĂ©nĂ©ral des problĂšmes de satisfaction de contraintes.

6) Comment introduire les candidats

Un exemple de la notation pointée

Il y a deux notations utilisĂ©es pour les candidats : 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] Essais et erreurs, ou hypothĂšses

La mĂ©thode la plus rapide pour un ordinateur consiste Ă  essayer systĂ©matiquement, l’un aprĂšs l’autre, tous les candidats restant. AppliquĂ©e rĂ©cursivement, elle peut rĂ©soudre tous les puzzles. Mais cette mĂ©thode, fort peu Ă©lĂ©gante, est rejetĂ©e par quasiment tous les joueurs. Tout au plus est-elle acceptĂ©e comme ultime recours, quand plus rien d’autre ne marche.

[modifier] RÚgles élémentaires

Quand un puzzle peut ĂȘtre rĂ©solu en n’utilisant que les rĂšgles Ă©lĂ©mentaires de cette section, des joueurs expĂ©rimentĂ©s peuvent se dispenser de l’écriture explicite des candidats.

[modifier] propagation de contraintes élémentaires

Si un nombre est affirmĂ© comme Ă©tant nĂ©cessairement la valeur d’une cellule, supprimer tous les autres candidats de cette cellule et supprimer ce nombre comme candidat de toutes les autres cellules de la mĂȘme ligne, de la mĂȘme colonne et du mĂȘme bloc.

[modifier] singletons nus et cachés

Singleton nu : si une cellule contient un unique candidate, alors c’est la valeur de cette cellule.

Singleton cachĂ© : si un candidat apparaĂźt une fois et une seule sur une ligne (respectivement une colonne, un bloc), alors c’est la valeur de la cellule oĂč il apparaĂźt.

[modifier] interactions ligne-bloc et colonne-bloc

Si, sur une ligne L coupant un bloc B, un nombre n’apparaĂźt pas comme candidat Ă  l’extĂ©rieur de B, supprimer ce nombre comme candidat partout dans B sauf sur L.

Si, dans un bloc B coupĂ© par une ligne L, un nombre n’apparaĂźt pas comme candidat ailleurs que sur L, supprimer ce nombre comme candidat partout sur L Ă  l’extĂ©rieur de B.

Si, sur une colonne C coupant un bloc B, un nombre n’apparaĂźt pas comme candidat Ă  l’extĂ©rieur de B, supprimer ce nombre comme candidat partout dans B sauf sur C.

Si, dans un bloc B coupĂ© par une colonne C, un nombre n’apparaĂźt pas comme candidat ailleurs que sur C, supprimer ce nombre comme candidat partout sur C Ă  l’extĂ©rieur de B.

[modifier] Méthodes basées sur des figures (patterns) simples prédéfinies

[modifier] Paires, triplets et quadruplets nus

Paires nues sur une ligne : si, sur une ligne L, il existe deux cellules diffĂ©rentes qui ont pour candidats les mĂȘmes deux nombres diffĂ©rents, alors supprimer ces deux nombres comme candidats de toutes les autres cellules de la ligne.

Paires nues sur une colonne : si, sur une colonne C, il existe deux cellules diffĂ©rentes qui ont pour candidats les mĂȘmes deux nombres diffĂ©rents, alors supprimer ces deux nombres comme candidats de toutes les autres cellules de la colonne.

Paires nues dans un bloc : si, dans un bloc B, il existe deux cellules diffĂ©rentes qui ont pour candidats les mĂȘmes deux nombres diffĂ©rents, alors supprimer ces deux nombres comme candidats de toutes les autres cellules du bloc.


Triplets (resp. quadruplets) nus sur une ligne : si, sur une ligne L, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 [resp, 4] nombres diffĂ©rents, alors supprimer ces 3 [resp, 4] nombres comme candidats de toutes les autres cellules de la ligne.

Triplets [resp. quadruplets] nus sur une colonne : si, sur une colonne C, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 [resp, 4] nombres diffĂ©rents, alors supprimer ces 3 [resp, 4] nombres comme candidats de toutes les autres cellules de la colonne.

Triplets (resp. quadruplets) nus dans un bloc : si, dans un bloc B, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 {resp, 4] nombres diffĂ©rents, alors supprimer ces 3 [resp, 4] nombres comme candidats de toutes les autres cellules du bloc.

[modifier] Paires, triplets et quadruplets cachés

Paires cachĂ©es sur une ligne : si, sur une ligne L, il existe deux cellules diffĂ©rentes qui ont deux candidats communs n’apparaissant pas ailleurs sur la ligne (chacune des 2 cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.

Paires cachĂ©es sur une colonne : si, sur une colonne C, il existe deux cellules diffĂ©rentes qui ont deux candidats communs n’apparaissant pas ailleurs sur la colonne (chacune des 2 cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.

Paires cachĂ©es dans un bloc : si, dans un bloc B, il existe deux cellules diffĂ©rentes qui ont deux candidats communs n’apparaissant pas ailleurs dans le bloc (chacune des 2 cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.


Triplets (resp. quadruplets) cachĂ©s sur une ligne : si, sur une ligne L, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont 3 [resp, 4] candidats communs n’apparaissant pas ailleurs sur la ligne (chacune des 3 [resp, 4] cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.

Triplets [resp. quadruplets] cachĂ©s sur une colonne : si, sur une colonne C, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont 3 [resp, 4] candidats communs n’apparaissant pas ailleurs sur la colonne (chacune des 3 [resp, 4] cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.

Triplets (resp. quadruplets) cachĂ©s dans un bloc : si, dans un bloc B, il existe 3 [resp, 4] cellules diffĂ©rentes qui ont 3 [resp, 4] candidats communs n’apparaissant pas ailleurs dans le bloc (chacune des 3 [resp, 4] cellules pouvant avoir d’autres candidats), alors supprimer tous les autres candidats de ces deux cellules.

[modifier] Fish ou Poissons (X-Wing, Swordfish, Jellysfish)

X-Wing en ligne : Ă©tant donnĂ© un nombre n, si, sur deux lignes diffĂ©rentes, il n’apparaĂźt comme candidat que sur deux colonnes, le supprimer comme candidat partout sur les deux colonnes ailleurs que sur les deux lignes.

Swordfish en ligne : Ă©tant donnĂ© un nombre n, si, sur trois lignes diffĂ©rentes, il n’apparaĂźt comme candidat que sur trois colonnes, le supprimer comme candidat partout sur les trois colonnes ailleurs que sur les trois lignes.

Jellyfish en ligne : Ă©tant donnĂ© un nombre n, si, sur quatre lignes diffĂ©rentes, il n’apparaĂźt comme candidat que sur quatre colonnes, le supprimer comme candidat partout sur les quatre colonnes ailleurs que sur les quatre lignes.

Il existe bien entendu les rĂšgles homologues X-Wing en colonne, Swordfish en colonne et Jellyfish en colonne, dont l’énoncĂ© est obtenu Ă  partir des prĂ©cĂ©dents en permutant les mots « ligne Â» et « colonne Â».

Nota bene : il n’existe pas de rĂšgle homologue pour les blocs.

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

Dans The Hidden Logic of Sudoku[21], 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, entre les colonnes et les nombres et entre les blocs et les nombres. Une nouvelle mĂ©thode de rĂ©solution a Ă©tĂ© dĂ©veloppĂ©e, basĂ©e sur leur exploitation systĂ©matique. Les espaces rn, cn et bn (complĂ©mentaires de l’espace usuel rc) ont ainsi Ă©tĂ© introduits (p. 35 de la premiĂšre Ă©dition). Une grille de rĂ©solution Ă©tendue a Ă©tĂ© conçue, qui fait apparaĂźtre les liens de conjugaison comme des cases (de l’espace rc, rn, cn ou bn) Ă  deux candidats et peut faciliter l’application de la mĂ©thode. De la sorte, les sous-ensembles cachĂ©s, ainsi que les X-wings, Swordfish et Jellysfish, 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 et ultĂ©rieurement les chaĂźnes nrczt. 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] Figures plus complexes : chaĂźnes

Quand les techniques d’élimination de candidats basĂ©es sur des figures (ou patterns) simples ne suffisent pas, il faut recourir Ă  des figures plus complexes, par exemple les chaĂźnes. Une chaĂźne simple est une suite de candidats tels que chacun est liĂ© au prĂ©cĂ©dent. On peut dĂ©finir plusieurs types de chaĂźnes, qui peuvent tous ĂȘtre considĂ©rĂ©s comme des gĂ©nĂ©ralisations d’un unique type de base, la chaĂźne xy.

[modifier] chaĂźnes xy

Une « chaĂźne xy Â» de longueur n a 2n candidats groupĂ©s par 2 dans n cellules bivaluĂ©es (c’est-Ă -dire ayant chacune exactement 2 candidats).

Exemple de chaĂźne xy de longueur 4 : {a b} - {b c} - {c d} - {d a}. Un « {... } Â» symbolise le contenu d’une cellule (i.e. l’ensemble de ses candidats) et un « - Â» symbolise que les cellules de chaque cĂŽtĂ© sont liĂ©es (i.e. diffĂ©rentes mais sur la mĂȘme ligne, la mĂȘme colonne ou dans le mĂȘme bloc).

Il est trĂšs facile de voir, par l’absurde, que tout nombre a dans une cellule n’appartenant pas Ă  la chaĂźne mais liĂ©e Ă  la fois Ă  la premiĂšre et Ă  la derniĂšre cellules de la chaĂźne peut ĂȘtre Ă©liminĂ© : si a Ă©tait vrai dans cette cellule « cible Â», alors a serait faux dans la premiĂšre cellule de la chaĂźne, dont la valeur ne pourrait donc ĂȘtre que b ; mais alors b serait faux dans la deuxiĂšme cellule, dont la valeur ne pourrait donc ĂȘtre que c ; 
 ; on arriverait ainsi Ă  la conclusion que la valeur de la derniĂšre cellule de la chaĂźne ne pourrait ĂȘtre que a ; ce qui serait contradictoire avec le fait que a soit la valeur de la cellule cible.

Quand on a compris les chaßnes xy et ce raisonnement, on a compris la logique inhérente à tous les types de chaßnes.

[modifier] GĂ©nĂ©ralisations des chaĂźnes xy : chaĂźnes d'ALS et chaĂźnes nrczt

Parmi les gĂ©nĂ©ralisations logiques « naturelles Â» des chaĂźnes xy, on a :

- les chaĂźnes d’ALS (Almost Locked Sets), les plus anciennes et de loin les plus utilisĂ©es par les joueurs sur les forums de Sudoku ; un maillon de ces chaĂźnes n’est plus un candidat mais un ALS (Almost Locked Sets), c’est-Ă -dire un ensemble de k cellules (sur une mĂȘme ligne, une mĂȘme colonne ou dans un mĂȘme bloc) dont les candidats appartiennent Ă  un ensemble de k+1 nombres ;

- les chaĂźnes xyt, xyz et xyzt ainsi que leurs homolgues « cachĂ©s Â» dans les espaces rn, cn et bn (dĂ©finies dans la premiĂšre Ă©dition de The Hidden Logic of Sudoku) ; les chaĂźnes nrczt, ou chaĂźnes supersymĂ©triques, qui gĂ©nĂ©ralisent les prĂ©cĂ©dentes en combinant toutes les cellules des espaces rc, rn, cn et bn (dĂ©finies dans la seconde Ă©dition de The Hidden Logic of Sudoku[21])) ;

- une combinaison des deux, dont on peut trouver de nombreux exemples sur le forum sudoku-factory.

[modifier] RÚgles résultant de l'hypothÚse d'unicité

On exige en gĂ©nĂ©ral d’un puzzle, qu’on dit alors bien formĂ©, qu’il ait une solution et une seule. De toute Ă©vidence, cette exigence concerne d’abord le crĂ©ateur de puzzles.

L’exigence qu’il y ait une solution ne pose pas de problĂšme pour le joueur. Si elle n’est pas satisfaite par le crĂ©ateur, le joueur pourra en gĂ©nĂ©ral montrer la contradiction. Les rĂšgles mentionnĂ©es ci-dessus doivent en rĂ©alitĂ© s’interprĂ©ter de maniĂšre un peu plus subtile que sous la forme (usuelle) oĂč elles ont Ă©tĂ© Ă©noncĂ©es. La vĂ©ritable interprĂ©tation est : « s’il y a une solution et si le candidat C est vrai, alors on a une contradiction Â». D’oĂč l’on conclue « s’il y a une solution, alors C est faux Â», et on Ă©limine C des candidats. De cette maniĂšre, si le puzzle est contradictoire, on est certain qu’on ne trouvera pas de solution.

L’exigence d’unicitĂ© est plus dĂ©licate. Elle s’impose au crĂ©ateur, mais le joueur ne peut d’aucune façon la contrĂŽler. En pratique, cela signifie que, si un puzzle qui a plusieurs solutions est proposĂ© mais que le joueur applique des rĂšgles dĂ©coulant de l’hypothĂšse d’unicitĂ©, il peut faire ainsi des Ă©liminations non justifiĂ©es (et rater des solutions alternatives ou aboutir Ă  une situation oĂč il croit qu’il n’y a pas de solution). Ce problĂšme tend Ă  disparaĂźtre en pratique car les crĂ©ateurs de puzzles vĂ©rifient dĂ©sormais plus sĂ©rieusement l’unicitĂ©.

[modifier] Le principe du rectangle interdit

ConsidĂ©rons quatre cellules formant un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs. Si le contenu de ces quatre cellules est :

ab ab

ab ab

alors pour toute solution du puzzle ayant les valeurs

a b

b a

pour les cellules de ce rectangle, il existe une autre solution ayant les valeurs

b a

a b

et le puzzle ne peut donc avoir une solution unique.

La configuration initiale s’appelle rectangle interdit. À partir de lĂ , on peut dĂ©finir plusieurs rĂšgles visant Ă  empĂȘcher que cette situation se produise. Ces rĂšgles ne sont valables que sous l’hypothĂšse d’unicitĂ©.

[modifier] Exemples de rĂšgle reposant sur l'exploitation du rectangle interdit

RĂšgle UR1 : dans la configuration (oĂč les quatre cellules forment un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs) :

ab ab

ab abc

éliminer a et b de la derniÚre cellule.

RĂšgle UR2-H : dans la configuration (oĂč les quatre cellules forment un rectangle s’étalant sur deux lignes, deux colonnes et seulement deux blocs) :

ab abc

ab abc

oĂč les deux cellules de droite sont dans le mĂȘme bloc, Ă©liminer c de toute autre cellule liĂ©e aux deux cellules de droite.

Il existe de nombreuses variantes de ces rĂšgles.

[modifier] Classification des puzzles

Il n’existe pas de classification universelle des diffĂ©rents puzzles : toute classification repose sur le choix d’un ensemble de mĂ©thodes de rĂ©solution. On peut cependant distinguer les classifications Ă  large couverture (SER, SXT, NRCZT, etc.) et les classifications en quatre ou cinq niveaux (de « simple Â» Ă  « diabolique Â»), comme ceux qui sont publiĂ©s dans les journaux. Ces derniĂšres ne couvrent en gĂ©nĂ©ral que des puzzles relativement simples, de SER ne dĂ©passant pas 5 ou 6.

Il faut noter que chaque classification n’a de valeur qu’indicative et que, pour un joueur, deux puzzles ayant la mĂȘme valeur dans une classification peuvent prĂ©senter des difficultĂ©s trĂšs diffĂ©rentes.

[modifier] Préambule sur les puzzles minimaux et les statistiques de classification des puzzles

Une notion gĂ©nĂ©rale trĂšs utile d’un point de vue thĂ©orique est celle de puzzle minimal. Un puzzle est dit minimal (ou, plus rarement, « localement minimal Â») s’il a une solution unique et si, chaque fois qu’on essaie de lui ĂŽter un dĂ©voilĂ©, le puzzle obtenu (qui a toujours Ă©videmment au moins une solution) se retrouve avoir plusieurs solutions.

Quand on veut faire des statistiques sur la classification des puzzles, il faut toujours se rĂ©fĂ©rer Ă  des ensembles de puzzles minimaux, faute de quoi ces statistiques n’ont pas grand sens : en effet, en ajoutant autant de dĂ©voilĂ©s qu’on veut, choisis parmi ses valeurs solutions, Ă  un puzzle minimal, on peut obtenir de trĂšs nombreux puzzles qui auront Ă©videmment la mĂȘme solution, la plupart Ă©tant triviaux Ă  rĂ©soudre.

À noter qu’il est trĂšs facile et rapide de gĂ©nĂ©rer par ordinateur des ensembles alĂ©atoires de milliers de puzzles minimaux (avec, par exemple, le logiciel libre suexg. (Pour plus de dĂ©tails sur la crĂ©ation de puzzles, voir plus loin).

La minimalitĂ© est une exigence annexe parfois attendue du crĂ©ateur de puzzles. Elle est sans effet pour le joueur. Cependant elle peut ĂȘtre difficile Ă  concilier avec d’autres exigences annexes, comme des exigences esthĂ©tiques, par exemple de symĂ©trie, Ă  savoir que les dĂ©voilĂ©s se situent dans un ensemble de cellules prĂ©sentant une certaine forme de symĂ©trie. Il est plus difficile de gĂ©nĂ©rer des puzzles qui Ă  la fois soient minimaux et aient certaines symĂ©tries (en particulier, suexg ne le fait pas).

[modifier] SER (Sudoku Explainer Rating)

Le SER (Sudoku Explainer Rating) est de loin la classification la plus utilisĂ©e. Sudoku Explainer est un logiciel libre (en java), dĂ©veloppĂ© par Nicolas Juillerat et tĂ©lĂ©chargeable sur le web. Il peut ĂȘtre utilisĂ© pour rĂ©soudre des puzzles mais aussi pour produire une estimation de leur difficultĂ©, nommĂ©e leur SER. Celui-ci prend des valeurs de 1 Ă  11,7 (valeur maximale connue Ă  ce jour).

Les rĂšgles qu’il utilise (dont certaines reposent sur l’hypothĂšse d’unicitĂ©) sont passablement hĂ©tĂ©rogĂšnes et les valeurs affectĂ©es passablement ad hoc. À titre d’illustration, voici les niveaux associĂ©es Ă  quelques-unes des rĂšgles dĂ©finies plus haut.

1.0 Ă  2.3 Divers singletons
3.0 Paires Nues 
3.4 Paires Cachées 
3.6 Triplets Nus
3.8 Swordfish
4.0 Triplets Cachés
5.0 Quadruplets Nus
5.2 Jellyfish
5.4 Quadruplets Cachés 

11.6 Dynamic + Dynamic Forcing Chains (145-192 nodes) Cell Forcing Chains

11.7 Dynamic + Dynamic Forcing Chains (193-288 nodes) Double Forcing Chains

Ces Dynamic Forcing Chains sont une forme d’essais et erreurs.

[modifier] Classification NRCZT

Cette classification, dĂ©finie dans The Hidden Logic of Sudoku[21], est basĂ©e sur la longueur maximale de la chaĂźne nrczt nĂ©cessaire pour rĂ©soudre un puzzle. Contrairement au SER, un seul type de rĂšgle (les chaĂźnes nrczt de diverses longueurs) est ici utilisĂ© et cette classification, purement logique, indĂ©pendante de l’hypothĂšse d’unicitĂ© et indĂ©pendante de toute implĂ©mentation, est compatible avec toutes les symĂ©tries du jeu.

Bien que reposant sur des rĂšgles qui sont donc fort diffĂ©rentes de celles Ă  la base du SER, cette classification est Ă©troitement corrĂ©lĂ©e Ă  celui-ci : une Ă©tude faite sur 10 000 puzzles minimaux diffĂ©rents (obtenus avec le gĂ©nĂ©rateur pseudo-alĂ©atoire suexg) donne un coefficient de corrĂ©lation est de 0,89. Cela signifie que ces deux classifications saisissent effectivement un aspect important de ce qui fait la complexitĂ© d’un puzzle.

[modifier] Statistiques de la classification nrczt

Ces statistiques sont disponibles dans le livre The Hiden Logic of Sudoku[21] ou l’article From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E[25] (sur la base de 10 000 puzzles minimaux alĂ©atoires).

La rĂ©partition par niveaux nrczt de ces mĂȘmes 10 000 puzzles se fait ainsi :

niveau 1 : 5 382

niveau 2 : 1 391

niveau 3 : 1 642

niveau 4 : 1 243

niveau 5 : 255

niveau 6 : 62

niveau 7 : 16

niveau 8 : 6

niveau 9 : 1

niveau 10 : 0

niveau 11 : 1

niveau 12 : 0

niveau 13 : 1

Sachant que la complexitĂ© effective d’un puzzle croĂźt de maniĂšre quasi exponentielle avec son SER ou son NRCZT, ces chiffres montrent que :

1) une trĂšs grande majoritĂ© des puzzles peut se rĂ©soudre par des techniques relativement simples (ici, des chaĂźnes courtes) ;

2) il reste malgrĂ© tout des puzzles de trĂšs grande complexitĂ©, ce qui justifie que les joueurs experts recherchent en permanence de nouvelles rĂšgles qui permettraient de simplifier les solutions obtenues avec les rĂšgles connues Ă  ce jour ;

3) les puzzles exceptionnellement complexes (comme le fameux Easter Monster) ont trĂšs peu de chances d’ĂȘtre trouvĂ©s par un gĂ©nĂ©rateur alĂ©atoire et certains joueurs essaient en permanence de crĂ©er de nouveaux exemples « Ă  la main Â».

[modifier] Classifications des puzzles « grand public Â»

La plupart des auteurs des manuels sur le sudoku sont d’accord sur le fait que plusieurs facteurs influent sur la difficultĂ© de ces problĂšmes dont 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 × ligne, rĂ©gion × colonne ou colonne × ligne ;
  • du nombre de groupes indĂ©pendants de multiples numĂ©riquement liĂ©s, traitables suivant les trois dimensions Ă  la fois ; rĂ©gion × ligne × 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.

Cependant, cette question de difficultĂ© fait toujours 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 si l'on hiĂ©rarchise, du simple au complexe, les techniques et procĂ©dĂ©s que l'on peut utiliser pour rĂ©ussir une grille, et si l'on considĂšre notre maniĂšre de jouer (observer certaines rĂšgles d'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).

Mais, 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Ă© :

[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 pas Ă  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 × rĂ©gion ou colonne × 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 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 × colonnes, lignes × rĂ©gions et/ou colonnes × 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 × colonnes × 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 telles ! 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. Bien entendu, l’unicitĂ© de la solution pour la grille est 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] 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 Ă©lĂ©gant, il est certain de trouver une solution s’il en existe. 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 (voir (en) Algorithmics of Sudoku#Solving sudokus by a brute-force algorithm).

Une implĂ©mentation alternative du backtracking est de recourir Ă  la programmation logique, telle qu’implantĂ©e dans 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. Si l’on admet que la grille a 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[26]), et qui se révÚle trÚs efficace pour résoudre ce type des Sudokus en quelques millisecondes.

Il existe aussi de nombreux programmes librement disponibles sur le web, basĂ©s sur l’implĂ©mentation de rĂšgles utilisĂ©es par les joueurs : Sudocue, Sudoku Explainer, Sudoku Susser, Sadman, le solveur de gsf. Le programme SudoRules, non public, est basĂ© sur des techniques d’Intelligence Artificielle.

[modifier] Construction de grilles

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 ou 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.

Le logiciel libre (suexg) permettant de construire des puzzles minimaux (plusieurs dizaines Ă  la seconde) est disponible sur le Web.

La minimalitĂ© est une exigence annexe parfois attendue du crĂ©ateur de puzzles, bien qu’elle soit sans effet pour le joueur. Elle peut ĂȘtre difficile Ă  concilier avec d’autres exigences annexes, comme des exigences esthĂ©tiques, par exemple de symĂ©trie, Ă  savoir que les dĂ©voilĂ©s se situent dans un ensemble de cellules prĂ©sentant une certaine forme de symĂ©trie. Il est plus difficile de gĂ©nĂ©rer des puzzles qui Ă  la fois soient minimaux et aient certaines symĂ©tries (en particulier, suexg ne le fait pas).

[modifier] Voir aussi

[modifier] Bibliographie

  • Narendra Jussien, PrĂ©cis de Sudoku, HermĂšs Lavoisier, 2006, 188 pages (ISBN 2-7462-1559-4)
  • Denis Berthier, The Hidden Logic of Sudoku, Lulu Publishers ; 1re Ă©dition, Mai 2007, 384 pages (ISBN 978-1-84753-472-9) ; deuxiĂšme Ă©dition, Novembre 2007, 416 pages (ISBN 978-1-84799-214-7)
  • « Le tsunami du sudoku Â», Pour la Science, no 338, dĂ©cembre 2005, p. 144.
  • Denis Berthier, From Constraints to Resolution Rules, Part I: Conceptual Framework, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008.
  • Denis Berthier, From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008.

[modifier] Notes et références

  1. ↑ CarrĂ©s magiques en Chine
  2. ↑ (en)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 datĂ© du 3 juin 2006.
  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) G2, home of the discerning Sudoku addict,The Guardian, publiĂ© le 13 mai 2005
  8. ↑ (en) The World’s Largest Sudoku Puzzle: Win ÂŁ5000, Sky One, consultĂ© le 28 mai 2009
  9. ↑ (en) http://sudoku.top-notch.co.uk/gattai5.asp
  10. ↑ (fr) http://www.kuboku.com/
  11. ↑ (en) http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html
  12. ↑ (en) http://sudoku.top-notch.co.uk/wordoku.asp
  13. ↑ (en) http://www.mathrec.org/sudoku
  14. ↑ (en) http://sudoku.top-notch.co.uk/superwordoku.asp
  15. ↑ Sudoku enumeration problems
  16. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/ et suite A107739 de l’OEIS
  17. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et suite A109741 de l’OEIS
  18. ↑ (ja)ăƒ—ăƒ­ă‚°ăƒ©ăƒŸăƒłă‚°ăƒ‘ă‚șăƒ«é›‘è«‡ă‚łăƒŒăƒŠăƒŒ
  19. ↑ (en)Minimum Sudoku
  20. ↑ (en) [pdf]
  21. ↑ a  b  c  d  e  f  (en)Berthier, Denis : The Hidden Logic of Sudoku, Lulu Publishers, ISBN 978-1-84753-472-9 (16 mai 2007). ConsultĂ© le 16 mai 2007.
  22. ↑ (ja) http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
  23. ↑ (en) http://www.csse.uwa.edu.au/~gordon/sudokumin.php
  24. ↑ Denis Berthier, From Constraints to Resolution Rules, Part I: Conceptual Framework, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008
  25. ↑ Denis Berthier, From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008
  26. ↑ (en)Knuth: Preprints

[modifier] Articles connexes

  • 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

Sur les autres projets Wikimedia :


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.


cours particuliers - cours de maths haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2009