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
Crystal Clear app fonts.svg Cette page contient des caractĂšres spĂ©ciaux. Si certains caractĂšres de cet article s’affichent mal (carrĂ©s vides, points d’interrogation, etc.), consultez la page d’aide Unicode.
Sudoku proposé par la presse.

Le sudoku (prononcĂ© soudokou en français, /sɯːdokÉŻ/Ă©couter 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

Présentation[modifier | modifier le code]

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

Étymologie[modifier | modifier le code]

Le nom sudoku (æ•°ç‹Ź) est nĂ© de l’abrĂ©viation de la rĂšgle du jeu japonaise « SĆ«ji wa dokushin ni kagiru Â» (æ•°ć­—ăŻç‹Źèș«ă«é™ă‚‹?), signifiant littĂ©ralement « Chiffre (æ•°ć­—) limitĂ© (限る) Ă  un seul (独èș«) Â» (sous entendu 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ÉŻ]Ă©couter ; 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 Â».

Histoire[modifier | modifier le code]

Une des plus anciennes grilles de sudoku connues, de 1895, dans le quotidien La France

Ce jeu est tout d'abord, probablement inspirĂ© par le carrĂ© magique, connus des mathĂ©maticiens chinois, Ă  partir de -650 sous le nom Luoshu (掛äčŠ, LuĂČ shĆ«, « livre de la riviĂšre Luo Â»). d'ordre 3, ils pouvaient alors ĂȘtre reprĂ©sentĂ©s par diffĂ©rents symboles et utilisĂ© dans le feng shui.

Ce sont visiblement les indiens, inventeurs des chiffres arabes qui les limitĂšrent Ă  des chiffres[1], puis par les arabes, probablement vers le VIIe siĂšcle, lorsque les armĂ©es arabes firent la conquĂȘte du nord-ouest de l'Inde.

Les premiers carrĂ©s magiques d'ordres 5 et 6 apparurent dans une encyclopĂ©die publiĂ©e Ă  Baghdad vers 983, l’EncyclopĂ©die de la FraternitĂ© de la puretĂ© (Rasa'il Ikhwan al-Safa)[1].

Au XIIIe siĂšcle, le mathĂ©maticien chinois Yang Hui (杚蟉 / 愊茝, YĂĄng HuÄ«, 12381298), qui a Ă©galement dĂ©fini le triangle de Pascal, travaille sur une approche structurelle du carrĂ© magique d'ordre 3.

Le mathĂ©maticien français Claude-Gaspard Bachet de MĂ©ziriac dĂ©crit une mĂ©thode pour rĂ©soudre le problĂšme du carrĂ© magique en prenant pour exemple un caviste qui veut ranger des bouteilles dans un casier 3 x 3, dans ses « ProblĂšmes plaisants et dĂ©lectables qui se font par les nombres Â», publiĂ© en 1612[2].

Le mathĂ©maticien suisse, Leonhard Euler (1707 - 1783), crĂ©e ou au moins cite le « CarrĂ© latin Â»[3], tableau carrĂ© de n lignes et n colonnes remplies de n Ă©lĂ©ments distincts dont chaque ligne et chaque colonne ne contient qu'un seul exemplaire.

En 1892, en France, dans le quotidien monarchiste Le SiĂšcle, apparaĂźt la plus ancienne grille connue de sudoku. Le 6 juillet 1895, toujours en France, le quotidien, « La France Â» publie une autre grille de ce jeu sur une grille de 9 × 9 cases, appelĂ© « CarrĂ© magique diabolique Â», et rĂ©alisĂ© par M.B. Meyniel.

En avril 1984, Kaji Maki (鍜æČ» 真蔷, nĂ© en 1951), directeur de la sociĂ©tĂ© Nikoli (ニコăƒȘ), publie pour la premiĂšre fois, dans sa revue mensuelle « Getsukan Nikoli suto Â» (æœˆćˆŠăƒ‹ă‚łăƒȘă‚čト), le jeu sous le nom « SĆ«ji wa dokushin ni kagiru Â» (æ•°ć­—ăŻç‹Źèș«ă«é™ă‚‹).

RĂšgles de base[modifier | modifier le code]

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.

Une rĂšgle non Ă©crite mais communĂ©ment admise veut Ă©galement qu’une bonne grille de sudoku, une grille valide, ne doit prĂ©senter qu’une et une seule solution. Ce n’est pas toujours le cas


Les chiffres ne sont utilisĂ©s que par convention, les relations arithmĂ©tiques entre eux ne servant pas (sauf dans la variante Killer Su Doku, voir ci-aprĂšs). 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. Le niveau de difficultĂ© peut ĂȘtre adaptĂ©, et des grilles sont publiĂ©es dans des journaux, mais peuvent aussi ĂȘtre crĂ©Ă©es Ă  la demande sur Internet.

Variantes[modifier | modifier le code]

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 6x6 irrégulier
Sudoku par comparaison et sa solution.
Killer Su Doku (détail)

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.
  • 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 . Le logiciel ksudoku appelle de telle grilles roxdoku et les crĂ©e 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[4].
  • 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.

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 , 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 et ne rĂ©vĂšle aucune case, 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.

Variantes alphabétiques[modifier | modifier le code]

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[5]. Le Wordoku[6] 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[7] conçu par Steve Schaefer contient une phrase complĂšte, alors que le Super Wordoku[8] 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 sudokus 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.

Précurseurs du Sudoku[modifier | modifier le code]

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

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[9] en 1955. 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[10].

Emplois historiques des carrés magiques[modifier | modifier le code]

Un des ancĂȘtres du sudoku dans l'AntiquitĂ© Ă©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.

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[11] (vers -300), et en Inde oĂč furent inventĂ©s ce que nous appelons les chiffres arabes. Ils ont Ă  l’origine des significations divinatoires.

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

Pendant la Renaissance, 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.

Le problĂšme des officiers[modifier | modifier le code]

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 concernent 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).

Version moderne du sudoku[modifier | modifier le code]

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 .

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 . Une variante proche avait Ă©tĂ© publiĂ©e peu avant, en , dans Le SiĂšcle, variante qui utilisait des nombres Ă  deux chiffres[12].

En 1979, un pigiste spĂ©cialisĂ© dans les casse-tĂȘte, Howard Garns, crĂ©e le premier jeu tel que nous le connaissons aujourd’hui. Dell Magazines l’introduit cette mĂȘme annĂ©e dans une publication destinĂ©e au marchĂ© new-yorkais, le Dell Pencil Puzzles and Word Games, sous le nom de Number Place. Nikoli l’introduit au Japon en 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 facilement en mĂȘme temps !

En 1989, Loadstar et Softdisk publient DigitHunt pour le Commodore 64, probablement le premier logiciel pour ordinateur personnel Ă  crĂ©er 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[13] et, en 1996, il récidive pour Palm OS[14].

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

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 .

Popularité dans les médias[modifier | modifier le code]

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 crée 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 .

Trois jours plus tard, The Daily Mail publie aussi une grille sous le nom Codenumber. The Daily Telegraph introduit sa premiĂšre grille le , suivi par les autres publications du Telegraph Group. Le , 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 , 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 , 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 crĂ©Ă©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 Liens externes 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[15]. 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 .

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 , 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[16] 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 , 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, ) remportĂ© par Juliette ThĂ©ry, 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.

Mathématiques[modifier | modifier le code]

Structure logique[modifier | modifier le code]

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

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[18], 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 qu'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[19],[20], 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.

Nombre de grilles possibles[modifier | modifier le code]

Symétries des grilles[modifier | modifier le code]

Gordon Royle considĂšre que deux grilles complĂštes doivent ĂȘtre considĂ©rĂ©es comme Ă©quivalentes si elles peuvent ĂȘtre transformĂ©es l’une en l’autre (ou l’inverse) grĂące Ă  une combinaison quelconque des opĂ©rations suivantes :

  1. Ă©change des lignes avec les colonnes (transposition - deux solutions)
  2. permutations des 9 nombres (9! solutions)
  3. permutation des trois lignes au sein d'un mĂȘme bloc (3!Âł solutions) ou des trois colonnes (3!Âł solutions)
  4. permutation des trois blocs sur une ligne de blocs (3! solutions) ou sur une colonne de blocs (3! solutions)

Une grille complĂšte permet ainsi de crĂ©er un total de 2x9!x(3!)^8 = 1 218 998 108 160 grilles essentiellement Ă©quivalentes. On remarque l’analogie avec les opĂ©rations matricielles en algĂšbre linĂ©aire.

Nombre de grilles complĂštes[modifier | modifier le code]

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é[21] que ce nombre de grilles était de[22]:

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

Nombre de grilles incomplĂštes[modifier | modifier le code]

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 effet, partant d'une grille complĂšte, on peut construire un problĂšme proposable par la mĂ©thode suivante :

  1. Au dĂ©part, aucune case de la grille complĂšte n'est « nĂ©cessaire Â».
  2. Choisir une case non « nĂ©cessaire Â» quelconque. Si la suppression de la case choisie conduit Ă  une grille Ă  plusieurs solutions, la marquer comme « nĂ©cessaire Â», sinon la supprimer.
  3. Si toutes les cases remplies sont « nĂ©cessaires Â», la grille incomplĂšte est un problĂšme proposable ; sinon rĂ©itĂ©rer l'Ă©tape prĂ©cĂ©dente.

On voit facilement que dans les premiĂšres Ă©tapes, aucune case n'est rĂ©ellement nĂ©cessaire, ce qui permet d'imposer un problĂšme diffĂ©rent d'un problĂšme « proposable Â» donnĂ©, simplement en vidant une des cases qui Ă©tait fournie dans ce problĂšme.

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 !

Cependant, il existe dĂ©sormais une estimation (basĂ©e sur une approche statistique) du nombre total de puzzles minimaux (voir la section « classification des puzzles Â»)

Le nombre maximal de « rĂ©vĂ©lĂ©s Â» dans une grille qui ne fournisse pas une solution unique est une grille complĂšte moins quatre : si dans une grille complĂšte deux occurrences de deux nombres sont supprimĂ©es, et que ces occurrences sont aux angles d'un rectangle, et que deux de ces cellules sont dans un mĂȘme groupe, alors il y a deux solutions pour complĂ©ter la grille. Ceci Ă©tant une caractĂ©ristique gĂ©nĂ©rale des carrĂ©s latins, la plupart des grilles de sudoku ont le mĂȘme maximum.

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[24],[25]. Rien ne dit que ce ne soit pas possible avec moins de nombres.

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

Minimum : 17 rĂ©vĂ©lĂ©s[modifier | modifier le code]

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). D'aprĂšs un article de Gary McGuire publiĂ© dans le site de prĂ©publication ArXiv il n'est pas possible d’en dĂ©finir un ne comportant que 16 rĂ©vĂ©lĂ©s et ayant une solution unique[26],[27].

Méthodes de résolution utilisées par les joueurs[modifier | modifier le code]

Remarques préliminaires[modifier | modifier le code]

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 sont les mĂ©thodes de rĂ©solution admissibles par un joueur ? Toute rĂ©ponse Ă  cette question aurait une composante subjective ; ne pas reconnaĂźtre d’emblĂ©e ce fait conduirait Ă  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 mĂ©thode la plus rapide pour un ordinateur consiste Ă  essayer systĂ©matiquement, l’un aprĂšs l’autre, tous les candidats restants. 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.

Pour de nombreuses mĂ©thodes, la discussion se fait sur l'appartenance Ă  une « rĂ©gion Â» qui peut ĂȘtre (par dĂ©finition) indiffĂ©remment une ligne, une colonne, ou un groupe.

Gestion des nombres candidats[modifier | modifier le code]

Un exemple de la notation pointée

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 un candidat. Alors que les dĂ©voilĂ©s sont les donnĂ©es initiales du problĂšme, 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 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[18])) ; ils font appel Ă  la logique Ă©pistĂ©mique. L’article From Constraints to Resolution Rules, Part I: Conceptual Framework[28], 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.

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. Quand un candidat est impossible, il est rayĂ© de la liste. 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. Il y a deux logiques possibles, opposĂ©es et mutuellement exclusives :
    • Quand un candidat s'avĂšre impossible, le point correspondant est noirci. Par exemple, pour indiquer que « 1 Â» ne peut pas ĂȘtre candidat, un point est marquĂ© en haut Ă  gauche dans la cellule. Cette notation permet de jouer directement avec une grille imprimĂ©e dans un journal, et prĂ©sente l'avantage de ne pas avoir Ă  effacer ses marques. Cependant, elle demande du soin : 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.
    • Quand un candidat s'avĂšre possible, le point correspondant est noirci. S'il s'avĂšre plus tard dans le raisonnement que cette hypothĂšse peut ĂȘtre Ă©liminĂ©e, il suffira alors de barrer ce point d'une petite croix.

Lorsqu'on peut dĂ©duire qu'un nombre est nĂ©cessairement la valeur d’une cellule :

  • on peut supprimer tous les autres candidats de cette cellule,
  • et on peut 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.

RÚgles élémentaires[modifier | modifier le code]

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. Ces puzzles correspondent Ă  des niveaux « facile Â» ou « Ă©lĂ©mentaire Â».

Singleton[modifier | modifier le code]

Le « singleton Â» correspond au cas oĂč il n'y a plus qu'une seule cellule vide dans une « rĂ©gion Â» (ligne, colonne ou bloc). Dans ce cas, la valeur de la cellule est Ă©videmment le seul nombre manquant dans la rĂ©gion : c'est le seul endroit oĂč le nombre manquant puisse ĂȘtre mis (singleton cachĂ©), et c'est la seule valeur que peut recevoir la cellule vide (singleton nu).

Cette configuration se rencontre surtout en fin de problÚme, quand presque toutes les cellules ont été remplies.

Plus gĂ©nĂ©ralement, le « singleton Â» correspond au cas oĂč il n'y a (localement) qu'une seule solution : une case ne peut recevoir qu'une seule valeur (singleton nu), ou bien une valeur ne peut ĂȘtre affectĂ©e qu'Ă  une seule case (singleton cachĂ©), tout autre choix conduisant Ă  une incohĂ©rence immĂ©diate. Il s'oppose aux « paires Â», « triplets Â» et « quadruplets Â», oĂč la discussion porte sur plusieurs valeurs simultanĂ©ment.

Élimination directe - Singleton cachĂ©[modifier | modifier le code]

Identification d'un singleton cachĂ© : il n'y a qu'une seule case possible pour un « 4 Â» dans le bloc supĂ©rieur droit

La recherche d'un « singleton cachĂ© Â» revient Ă  se poser la question « Dans cette rĂ©gion (ligne, colonne ou bloc), quelles sont les cases qui peuvent accueillir un 1 (2 ou 3 ou
 9)? Â» : si la position est unique dans la rĂ©gion considĂ©rĂ©e, alors le candidat devient valeur en cette position.

La recherche de singleton cachĂ© est d'autant plus facile que la valeur est frĂ©quente dans la grille : les contraintes de positionnement augmentent, alors que le nombre de positions possibles diminue.

Le marquage des cellules n'apporte qu'une faible plus-value pour la recherche des singletons cachĂ©s : il faut de toute maniĂšre balayer toute la rĂ©gion pour vĂ©rifier que la valeur recherchĂ©e n'y figure qu'une seule fois comme candidat. C'est pour cette raison que ces singletons sont qualifiĂ©s de « cachĂ©s Â».

Recherche des valeurs uniques - Singleton nu[modifier | modifier le code]

Exemple de grille avec un « singleton nu Â»

La recherche d'un « singleton nu Â» revient Ă  se poser la question « quelle peut ĂȘtre la valeur de cette cellule? Â», c'est-Ă -dire la recherche des candidats. Si une cellule contient un unique candidat, alors c’est la valeur de cette cellule.

La recherche des singletons nus est d'autant plus fructueuse que la cellule examinée se trouve à l'intersection de régions assez remplies, ce qui augmente les contraintes et restreint le nombre de valeurs possibles sur la cellule examinée.

Cette recherche est un peu plus laborieuse que la prĂ©cĂ©dente, et pour la conduire systĂ©matiquement, il est plus facile de marquer les cellules. Le marquage des cellules reflĂšte en effet directement la problĂ©matique des singletons nus, et permet facilement de les repĂ©rer visuellement : ils correspondent aux cellules qui n'ont qu'un seul candidat.

En général, ce marquage des cellules (qui permet de trouver tous les singletons nus présents) est un préalable aux étapes de recherche plus élaborées.

Cette appellation de « singleton nu Â» vient de ce que dans les logiciels d'aide Ă  la rĂ©solution des sudoku, quand la liste des candidats est affichĂ©e sur chaque cellule, ces cases sont immĂ©diatement visibles (nues) parce que ce sont les seules qui n'ont qu'un seul candidat (singleton)[29]. Pour l'anecdote, cette dĂ©signation de « singleton nu Â» (naked single, en anglais, soit littĂ©ralement « cĂ©libataire dĂ©nudĂ© Â») peut conduire certains filtres de contrĂŽle parental Ă  limiter l'accĂšs aux pages de discussion du sudoku[30]


Élimination indirecte - interactions ligne-bloc et colonne-bloc[modifier | modifier le code]

Le « 1 Â» dans le bloc centre droit ne peut qu'ĂȘtre sur la colonne g. Le « 1 Â» du bloc infĂ©rieur droit est donc nĂ©cessairement en Gj (en jaune).

L'Ă©limination indirecte est un prolongement de l'Ă©limination directe. Elle peut Ă©galement se faire sans marquage, mais demande plus de rĂ©flexion. La mĂ©thode se distingue en deux cas :

  • On peut dĂ©tecter dans un bloc B, un candidat qui n'apparait qu'en ligne (ou en colonne). Dans ce cas, cette derniĂšre rĂ©gion est vidĂ©e du candidat en question, exceptĂ© dans le bloc B.
  • Mais rĂ©ciproquement, il faut chercher les lignes L(ou colonnes C) oĂč un candidat n'apparait que dans des cases appartenant, par ailleurs, au mĂȘme bloc. Dans ce cas, c'est le bloc qui peut ĂȘtre vidĂ© du candidat, exceptĂ© dans L (ou C),

L'élimination indirecte peut se faire formellement sur des cellules marquées, mais sa détection n'est pas tellement facilitée par le marquage.

Méthodes basées sur des motifs simples prédéfinis[modifier | modifier le code]

Groupes nus[modifier | modifier le code]

Un groupe nu en colonne e : Le groupe des 2 cases Ce et Ge de la colonne e forme une paire nue dont les candidats sont 78 ; on peut donc Ă©liminer les candidats 7 et le 8 des autres cases de la colonne e (le 8 de la case Fe et les 7 et 8 des cases Ae, De et Je).

Le raisonnement est le mĂȘme que le groupe soit de deux, de trois, ou de quatre cases (et sera donnĂ© ici pour trois cases).

Si dans une mĂȘme rĂ©gion (ligne, colonne ou bloc), on observe trois cases pour lesquelles les candidats sont :
i) au nombre de trois, et
ii) de valeurs identiques ;
alors nĂ©cessairement, ces trois valeurs devront ĂȘtre prises sur ces trois cases, et ne peuvent pas aller ailleurs dans cette rĂ©gion. Par l'absurde, si l'une des valeurs Ă©tait affectĂ©e Ă  une case autre de cette rĂ©gion, alors il ne resterait plus que deux valeurs possibles pour remplir ces trois cases, conduisant Ă  une impossibilitĂ©. De ce fait, quand cette configuration de groupe est identifiĂ©e, les valeurs du groupe ne peuvent pas ĂȘtre prises par les cases qui n'appartiennent pas au groupe : dans le reste de la rĂ©gion, les candidats correspondants Ă  ces valeurs peuvent ĂȘtre supprimĂ©s.

Lorsque n est supĂ©rieur Ă  2, il arrive frĂ©quemment qu'au moins une des cases du groupe n'ait pas comme candidats l'ensemble des chiffres de la liste : on parle alors de groupe « incomplet Â», mais cela n'enlĂšve rien Ă  la validitĂ© de la manƓuvre d'Ă©limination.

Les groupes ne comprennent que deux, trois ou quatre Ă©lĂ©ments. On peut remarquer que le cas limite d'un « groupe nu Â» Ă  un Ă©lĂ©ment correspond au cas des singletons nus. Inversement, si un « groupe nu Â» a plus que quatre Ă©lĂ©ments, on constate qu'en pratique, il est associĂ© symĂ©triquement Ă  un « groupe cachĂ© Â» de moins de cinq Ă©lĂ©ments, qu'il est plus facile de rechercher.

De mĂȘme que dans le cas des « singletons nus Â», ces configurations tirent leur nom de ce qu'elles sont immĂ©diatement apparentes (dĂ©voilĂ©es, donc « nues Â») sur les grilles oĂč les candidats ont Ă©tĂ© marquĂ©s. En effet, ces « groupes nus Â» peuvent facilement ĂȘtre recherchĂ©s formellement sur une grille oĂč les candidats ont Ă©tĂ© marquĂ©s, et oĂč ces triplets ont ainsi Ă©tĂ© rendus plus visibles : dĂšs qu'une case n'a qu'un faible nombre de candidats, on recherche la possibilitĂ© d'un tel groupe, en regardant si d'autres cases de la mĂȘme rĂ©gion (ligne, colonne ou bloc) ont des contraintes similaires.

Le traitement formel des « groupes nus Â» est le suivant :

  • Triplets nus sur une ligne : si, sur une ligne L, il existe 3 cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 nombres diffĂ©rents, alors on supprime ces 3 nombres comme candidats de toutes les autres cellules de la ligne.
  • Triplets nus sur une colonne : si, sur une colonne C, il existe 3 cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 nombres diffĂ©rents, alors on supprime ces 3 nombres comme candidats de toutes les autres cellules de la colonne.
  • Triplets nus dans un bloc : si, dans un bloc B, il existe 3 cellules diffĂ©rentes qui ont tous leurs candidats parmi les mĂȘmes 3 nombres diffĂ©rents, alors on supprime ces 3 nombres comme candidats de toutes les autres cellules du bloc.

Groupes cachés[modifier | modifier le code]

Un groupe cachĂ© 124 en colonne f : Le groupe de 3 cases Af, Gf et Jf de la colonne f forme un trio camouflĂ© (incomplet) dont les candidats sont 124 ; on peut donc Ă©liminer les candidats 8 et 9 des cases Af et Gf, et les candidats 3 et 8 de la case Jf (ce qui fait apparaĂźtre dans le pavĂ© Zy un solitaire camouflĂ© 7 Ă  la case Gd).

Le raisonnement est le mĂȘme que le groupe soit de deux, trois, ou quatre candidats et sera donnĂ© ici pour trois candidats.

Pour rechercher un groupe cachĂ©, il faut chercher un groupe de valeurs dont les candidats n'apparaissent que sur certaines cases d'une mĂȘme rĂ©gion. Au sein de cet ensemble de cases, certaines ne contiennent pas le groupe au complet et peuvent contenir d'autres candidats Ă©trangers au groupe.

La logique est symĂ©trique de celle des groupes nus et le raisonnement par l'absurde est similaire, mais on recherche cette fois-ci des groupes G de n candidats, tels que les n cases qui ont un ou plusieurs candidats dans G font toutes partie du groupe H de cases ; alors que les 9 - n cases dans la rĂ©gion mais hors de H n'ont aucun de leurs candidats dans G.

Le marquage ne permet pas de les identifier rapidement, et une recherche systĂ©matique est nĂ©cessaire, ce qui est Ă  l'origine de la dĂ©signation de « groupe cachĂ© Â» : leur identification est beaucoup plus laborieuse que celle des « groupes nus Â», et conduit Ă  des sudoku de difficultĂ© plus importante. Il faut noter de plus que la difficultĂ© croĂźt trĂšs fortement avec le nombre de cases du groupe.

Quand les « candidats Â» sont marquĂ©s sur la grille, le traitement formel des « groupes cachĂ©s Â» est simple :

  • Triplets cachĂ©s sur une ligne : si sur une ligne L, il existe 3 cellules diffĂ©rentes qui ont 3 candidats communs n’apparaissant pas ailleurs sur la ligne (chacune des 3 cellules pouvant avoir d’autres candidats), alors on supprime tous les autres candidats de ces trois cellules.
  • Triplets cachĂ©s sur une colonne : si sur une colonne C, il existe 3 cellules diffĂ©rentes qui ont 3 candidats communs n’apparaissant pas ailleurs sur la colonne (chacune des 3 cellules pouvant avoir d’autres candidats), alors on supprime tous les autres candidats de ces trois cellules.
  • Triplets cachĂ©s dans un bloc : si, dans un bloc B, il existe 3 cellules diffĂ©rentes qui ont 3 candidats communs n’apparaissant pas ailleurs dans le bloc (chacune des 3 cellules pouvant avoir d’autres candidats), alors on supprime tous les autres candidats de ces trois cellules.

Recherche des groupes nus et cachés[modifier | modifier le code]

Les groupes nus et cachĂ©s correspondent Ă  des situations assez symĂ©triques : dans une mĂȘme rĂ©gion (ligne, colonne ou bloc), on recherche un groupe de trois (ou 2 ou 4) nombres et un groupe d'autant de cases prĂ©sentant une configuration remarquable oĂč les nombres du groupe n'apparaissent pas ailleurs, ou il n'y a que les nombres du groupe dans les cases :

  • Si les nombres du groupe n'apparaissent pas ailleurs, mais qu'il y a Ă©ventuellement d'autres nombres dans ces cases : il s'agit alors d'un groupe cachĂ© ;
  • S'il n'y a que les nombres du groupe dans les cases, mais que les nombres du groupe apparaissent Ă©ventuellement ailleurs : il s'agit alors d'un groupe nu.

Dans les deux cas, on peut Ă©liminer les candidats pour rĂ©duire la situation Ă  une exclusion mutuelle : les nombres du groupe n'apparaissent pas ailleurs, et il n'y a que les nombres du groupe dans les cases : si le groupe est nu, on peut le cacher, et s'il est cachĂ©, on peut le dĂ©nuder.

On voit que ces dĂ©finitions sont symĂ©triques : si un groupe de cases vides dans une rĂ©gion forment un groupe nu, le reste des cases vides formera un groupe cachĂ© (mais Ă©ventuellement de plus de quatre membres), et inversement. D'autre part, on voit que les groupes nus et cachĂ©s ne peuvent se trouver que dans les rĂ©gions ayant de nombreuses cases libres : au minimum, si dans une mĂȘme rĂ©gion il y a Ă  la fois un groupe nu (de deux cases ou plus) et un groupe cachĂ© (de deux cases ou plus), la rĂ©gion a nĂ©cessairement quatre cases libres ou plus. Une rĂ©gion de quatre cases libres contient au plus un groupe nu de deux nombres (mais ne peut pas contenir de groupe de trois), une rĂ©gion de cinq cases libres contient peut contenir un groupe nu d'au plus trois nombres, et ainsi de suite.

La recherche des groupes nus et cachĂ©s peut se faire systĂ©matiquement, rĂ©gion par rĂ©gion, pour examiner celles qui peuvent encore ĂȘtre rĂ©duites. Si une rĂ©gion a moins de quatre cases libres, elle ne peut plus ĂȘtre rĂ©duite ; si un sous-groupe a moins de quatre membres, il ne peut pas lui-mĂȘme ĂȘtre rĂ©duit ; et une fois qu'une rĂ©gion a Ă©tĂ© rĂ©duite, il n'est plus nĂ©cessaire de l'examiner par la suite.

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

X-wing sur les lignes F et J pour 8 : Les deux lignes F et J ont toutes leurs candidats 8 situĂ©s Ă  l'une des cases placĂ©es Ă  l'intersection avec les colonnes a et j (configuration dite X-wing); par rapport Ă  ces quatre sommets on peut donc Ă©liminer les candidats 8 des cases des lignes et colonnes qui ne sont pas sur les sommets (donc en Ha et Dj).

Pour rechercher ces configurations, on regarde si un candidat n'apparaßt que dans un nombre précis de lignes et colonnes, pour lesquelles le nombre d'intersections est déterminé .

Le raisonnement qui permet l'Ă©limination de candidats est le suivant dans le cas du X-Wing. Soient quatre cases a, b, c, d (ex. Fa, Fj, Jj, Ja) contenant toutes un candidat K commun et formant un rectangle. Si sur les deux lignes (ab) et (cd), le candidat ne peut ĂȘtre prĂ©sent qu'en a ou b, et en c ou d, alors on peut reprĂ©senter le X-Wing par le rectangle abcd, ou par ses diagonales (ac) et (bd) qui forment un X. Dans cette situation, l'ensemble des possibilitĂ©s se rĂ©sument Ă  deux cas. Dans le premier cas, K se trouve en a, donc il ne peut ĂȘtre ni en b, ni en d, ni sur la colonne de a. Comme K ne peut ĂȘtre en d, il se trouve nĂ©cessairement aussi en c, et ne peut donc pas apparaĂźtre dans la colonne de c. Dans le deuxiĂšme cas, K se trouve en b, donc il ne peut ĂȘtre en a, ni en c, ni dans la colonne de b. Donc K se trouve nĂ©cessairement aussi en d et ne peut apparaĂźtre dans la colonne de d. Dans les deux cas, sans savoir ou sera K, on voit qu'il ne peut apparaĂźtre ni dans la colonne de a, ni dans la colonne de b (sauf en a, b, c ou d), ce qui nous permet d'Ă©liminer des candidats. Un raisonnement similaire peut ĂȘtre menĂ© dans le cas symĂ©trique oĂč ce sont les lignes qui ne peuvent accueillir le candidat.

Le cas du Swordfish fait apparaĂźtre une figure non pas de 4 sommets comme le X-Wing, mais de six sommets. On peut le voir comme deux rectangles rattachĂ©s par un sommet. Ce sommet en commun n'a aucune utilitĂ© dans la figure, si bien qu'il ne reste que six sommets. Techniquement, il faut trouver 3 lignes (ou colonnes) oĂč un candidat K n'apparaĂźt qu'en deux cases. Ces cases Ă©tant alignĂ©es d'une ligne Ă  l'autre deux Ă  deux.

Une fois identifiĂ©, le traitement formel de ces groupes « marinĂ©s Â» est :

  • X-Wing en ligne : si sur deux lignes, un candidat n’apparaĂźt que sur les deux mĂȘmes colonnes, alors on supprime ce candidat sur les deux colonnes sauf sur les deux lignes. Pour le X-Wing en colonne, on effectue le traitement en ligne.
  • Swordfish : si sur trois lignes diffĂ©rentes, un candidat n’apparaĂźt que sur trois colonnes, alors on supprime ce candidat sur les trois colonnes sauf sur les trois lignes.

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

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

Dans The Hidden Logic of Sudoku[18], 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Ă© mise en Ɠuvre dans un rĂ©solveur, SudoRules, basĂ© sur des techniques d’Intelligence Artificielle et simulant un joueur humain.

Figures plus complexes : chaĂźnes[modifier | modifier le code]

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.

ChaĂźnes xy[modifier | modifier le code]

Une chaĂźne xy, est une suite de cases comportant uniquement des doublons, soit 2 candidats exactement. De plus ces cases doivent avoir un lien entre elles : on doit pouvoir passer de l'une Ă  l'autre en restant dans une mĂȘme rĂ©gion, tout en suivant « le fil Â» d'un candidat. Par exemple, pour une suite de quatre cases « bien disposĂ©es Â», on pourrait avoir les candidats suivants {1,9} {1,3} {3,6} {2,6}.

Dans les cas intĂ©ressants de chaĂźnes, deux approches permettent l'Ă©limination de candidats :

  • ChaĂźnes de type {a,b} {b,c} {c,d} {d,a}

Dans ce cas, on montre que pour toute case X, hors de la chaĂźne, contenant le candidat « a Â», et situĂ©e Ă  la fois dans la mĂȘme rĂ©gion que la premiĂšre case et dans la mĂȘme rĂ©gion que la derniĂšre case, alors cette case ne peut contenir le candidat « a Â». Si « a Â» Ă©tait vrai dans cette case, alors « a Â» serait faux dans la premiĂšre case de la chaĂźne, et la chaĂźne se rĂ©duirait Ă  {b} {c} {d} {a}. Or « a Â» ne peut ĂȘtre Ă  la fois dans X et dans la derniĂšre case de la chaĂźne. Donc X ne peut contenir « a Â».

  • Cas gĂ©nĂ©ral : chaĂźnes forcĂ©es

Partant d'une case A contenant {x,y} et que l'on voit deux « chemins Â» diffĂ©rents reposant sur des chaĂźnes du type {x,y}{y,z}{z,t}{t,u}... arrivant Ă  une case B contenant {t,u}, alors il se peut qu’indiffĂ©remment du choix de x ou de y dans la premiĂšre case, et donc du chemin que l'on suit pour Ă©liminer des candidats, un candidat soit systĂ©matiquement Ă©liminĂ©. Alors on vient de trouver une solution dans une case. Par exemple si le t de la derniĂšre case est Ă©liminĂ© dans le cas oĂč on choisit y en premiĂšre case et qu'on suit le chemin 1 : {x,y}{y,z}{z,t}{t,u}, mais aussi dans le cas oĂč on choisit x et qu'on suit le chemin 2 : {x,y}{x,v}{v,u}{u,w}{w,y}{y,t}{t,u}, alors u est la solution de la case B.

Ces raisonnements sont communs Ă  tous les type de chaĂźnes.

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

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 homologues « 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[18])) ;

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

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

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 conclut « 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Ă©.

Le principe du rectangle interdit[modifier | modifier le code]

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Ă©.

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

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.

Classification des puzzles[modifier | modifier le code]

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.

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

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 crĂ©er 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 crĂ©er des puzzles qui Ă  la fois soient minimaux et aient certaines symĂ©tries (en particulier, suexg ne le fait pas).

Au cours de l'annĂ©e 2008, il est apparu que les gĂ©nĂ©rateurs classiques de puzzles minimaux, qu'ils soient « bottom-up Â» ou « top-down Â» (c'est-Ă -dire qu'ils partent d'une grille vide et la remplissent petit Ă  petit ou qu'ils partent d'une grille complĂšte et Ă©liminent des indices un par un) Ă©taient tous fortement biaisĂ©s en faveur de puzzles avec peu d'indices. Une nouvelle sorte de gĂ©nĂ©rateurs a Ă©tĂ© introduite : les gĂ©nĂ©rateurs Ă  biais contrĂŽlĂ©. Eux aussi sont biaisĂ©s mais leur biais est connu et peut donc ĂȘtre corrigĂ©. Voir l'un des deux livres Constraint Resolution Theories[31], Pattern-Based Constraint Satisfaction and Logic Puzzles[32] ou l'article disponible sur le site de son auteur Unbiased Statistics of a CSP - A Controlled-Bias Generator'[33]

SER (Sudoku Explainer Rating)[modifier | modifier le code]

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

Les niveaux supĂ©rieurs font appel Ă  divers types de chaĂźnes :

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

Pour l'essentiel, la classification des puzzles les plus difficiles repose sur le nombre d'inférences élémentaires nécessaires pour l'élimination la plus difficile dans le cadre d'une procédure d'essais et erreurs à deux niveaux maximum (c-à-d autorisant de faire des hypothÚses sur un maximum de deux candidats simultanément). Ici, inférence élémentaire signifie soit un singleton (nu ou caché), soit l'élimination d'un candidat en contradiction directe avec une ou deux valeur(s) connue(s) ou supposée(s) par essais et erreurs.

Classification NRCZT[modifier | modifier le code]

Cette classification, dĂ©finie dans The Hidden Logic of Sudoku[18], 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 de 0,89. Cela signifie que ces deux classifications saisissent effectivement un aspect important de ce qui fait la complexitĂ© d’un puzzle.

Statistiques de la classification nrczt[modifier | modifier le code]

Les statistiques de la classification nrczt sont accessibles

- dans trois livres : The Hidden Logic of Sudoku[18], Constraint Resolution Theories[31] et Pattern-Based Constraint Satisfaction and Logic Puzzles[32]

- et dans deux articles du mĂȘme auteur : From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E[34] (sur la base de 10 000 puzzles minimaux alĂ©atoires) et Unbiased Statistics of a CSP - A Controlled-Bias Generator'[33].

Les résultats suivants sont basés sur le nouveau générateur à biais contrÎlé (et sur plusieurs millions de puzzles minimaux aléatoires) et sont non biaisées.

La rĂ©partition en pourcentage par niveaux nrczt se fait ainsi :

  • niveau 0 : 29,17
  • niveau 1 : 8,44
  • niveau 2 : 12,61
  • niveau 3 : 22,26
  • niveau 4 : 21,39
  • niveau 5 : 4,67
  • niveau 6 : 1,07
  • niveau 7 : 0,29
  • niveau 8 : 0,072
  • niveau 9 : 0,020
  • niveau 10 : 0,0055
  • niveau 11 : 0,0015

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[35]) 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 Â».

RĂ©sultats collatĂ©raux : la technique des gĂ©nĂ©rateurs Ă  biais contrĂŽlĂ© permet aussi d'estimer le nombre de puzzles minimaux (3,10 × 10^37) ainsi que le nombre de puzzles minimaux non Ă©quivalents (2,55 × 10^25).

Classifications des puzzles « grand public Â»[modifier | modifier le code]

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

Type 1[modifier | modifier le code]

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 crĂ©Ă©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 Â».

Type 2[modifier | modifier le code]

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 Â».

Type 3[modifier | modifier le code]

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.

Type 4[modifier | modifier le code]

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.

Type 5[modifier | modifier le code]

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.

Informatique et Sudoku[modifier | modifier le code]

Solutions logicielles[modifier | modifier le code]

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#Brute-force algorithm).

Une mise en Ɠuvre particuliĂšre 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[36]), et qui se révÚle trÚs efficace pour résoudre ce type de sudokus en quelques millisecondes.

Une autre solution, proposĂ©e en 2007 par le chercheur en mĂ©thodes formelles Nicolas Rapin du CEA LIST, consiste Ă  utiliser la structure de diagramme de dĂ©cision binaire (BDD en abrĂ©gĂ©) pour rĂ©soudre et reprĂ©senter au sein d'une structure unique l'espace des solutions d'une grille. L'idĂ©e consiste Ă  modĂ©liser la prĂ©sence du chiffre k en ligne i, colonne j, par la variable boolĂ©enne nommĂ©e x_i_j_k en prenant pour convention que la valeur vrai de cette variable reprĂ©sente la prĂ©sence du chiffre k en ligne i, colonne j et la valeur faux son absence. Il faut donc 9x9x9 variables boolĂ©ennes pour modĂ©liser une grille de sudoku 9x9. Les contraintes inhĂ©rentes au sudoku peuvent alors ĂȘtre Ă©crites directement sous la forme de formules boolĂ©ennes et passĂ©es Ă  une bibliothĂšque de BDD. Cette approche prĂ©sente l'avantage de pouvoir rĂ©soudre non seulement des grilles de sudoku bien formĂ©es (ayant une seule solution) mais aussi d'Ă©numĂ©rer toutes les solutions de grilles mal formĂ©es ayant plusieurs solutions (les solutions Ă©tant donnĂ©es par les chemins du diagramme menant Ă  la feuille 1) ou encore de prouver qu'une grille mal formĂ©e ne prĂ©sente aucune solution. Cette mĂ©thode peut donc ĂȘtre utile pour la rĂ©solution, l'Ă©laboration et la validation de grilles. En posant que → dĂ©note l'implication logique, ! la nĂ©gation et V la disjonction, voici un exemple de contrainte de rĂ©gion: x_1_1_1 → ! (x_1_2_1 V x_1_3_1 V x_2_1_1 V x_2_2_1 V x_2_3_1 V x_3_1_1 V x_3_2_1 V x_3_3_1). En langage naturel cette expression signifie : si le chiffre 1 est prĂ©sent en ligne 1, colonne 1, alors il n'est pas prĂ©sent ailleurs dans sa rĂ©gion. Les contraintes de colonne sont de la forme x_i_j_k → ! ( \vee_{h \neq i} x_h_j_k), celles de ligne de la forme x_i_j_k → ! ( \vee_{h \neq i} x_i_h_k) et celle de prĂ©sence d'un chiffre pour toute case i,j de la forme  \vee_{h \in [1,9]} x_i_j_h. Pour les cases remplies de la grille, les contraintes implicatives ci-dessus (rĂ©gion, ligne, colonne) se rĂ©duisent au consĂ©quent (terme Ă  droite de l'implication) puisque l'antĂ©cĂ©dent est vrai. Lors de la mise en Ɠuvre de cette solution, on observe que l'efficacitĂ© gĂ©nĂ©rale est trĂšs sensible Ă  l'ordre dans lequel les contraintes sont passĂ©es Ă  la bibliothĂšque de construction du BDD. Sur un PC standard (1,6 GHz, 1 Gio de RAM) la durĂ©e de rĂ©solution de grilles bien formĂ©es se situe entre 1 s et 2 min 30 s (selon les grilles).

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, Sudoktor, Sadman, le solveur de gsf. Le programme SudoRules, non public, est basĂ© sur des techniques d’Intelligence Artificielle.

Construction de grilles[modifier | modifier le code]

Il semblerait que les grilles de Dell Magazines, le pionnier dans le domaine de la publication, soient crĂ©Ă©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 crĂ©e 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 crĂ©Ă©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 crĂ©er des puzzles qui Ă  la fois soient minimaux et aient certaines symĂ©tries (en particulier, suexg ne le fait pas).

Notations[modifier | modifier le code]

Les solutions actuellement donnĂ©es pour les grilles de Sudoku ne sont pas satisfaisantes car elles donnent la rĂ©ponse mais ne donnent pas la dĂ©monstration. D'oĂč la nĂ©cessitĂ© d'un systĂšme de notations qui permette de comprendre leur rĂ©solution, de la mĂȘme façon qu'aux Échecs il existe un systĂšme de notations qui permet de reconstituer les parties au lieu de donner seulement la position « d'Echec et Mat Â». On trouvera dans la proposition ci-dessous la premiĂšre Ă©bauche d'un tel projet.

Proposition :

Les colonnes sont numĂ©rotĂ©es ABCDEFGHI. Les lignes sont numĂ©rotĂ©es de 123456789. Observons que les sens dans lequel sont faites ces indexations peuvent ĂȘtre pris comme on le veut dĂšs lors que la donnĂ©e de la grille et la donnĂ©e de sa rĂ©solution observent le mĂȘme repĂ©rage.

159 se lit « les chiffres 1 et 5 et 9 pris en bloc Â»

(D6E6F6) se lit « forcĂ©ment inclus dans les cases D6 et E6 et F6  Â»

)D6E6F6( se lit « forcĂ©ment exclus des cases D6 et E6 et F6  Â»

g se lit « en considĂ©rant la ligne oĂč on se trouve»

q se lit « en considĂ©rant le carrĂ© 3 × 3 oĂč on se trouve Â»

k se lit « en considĂ©rant la colonne oĂč on se trouve Â».

& se lit « joint au fait que Â»

>> se lit « ce qui implique forcĂ©ment que  Â»

= se lit « contient le chiffre Â»

w se lit « seul chiffre possible dans cette case Â»

x se lit « seule case oĂč ce chiffre peut se mettre Â»

et enfin les Ă©tapes de la rĂ©solution sont sĂ©parĂ©es les unes des autres par le symbole § qui se lit « Ă©tape suivante Â»

1° Exemple

Ainsi la notation : 78 )H5I5( q & 237(B9C9D9)g >> A8=7 xk se lira : CONSTAT : Les chiffres 7 et 8 sont forcĂ©ment exclus des cases H5 et I5 en considĂ©rant le carrĂ© 3x3 oĂč ils se trouvent, joint au fait que les chiffres 2,3, et 7 sont forcĂ©ment inclus dans les cases B9, C9, et D9 en considĂ©rant la ligne oĂč ils se trouvent ; DÉDUCTION : ces deux observations impliquent que la case A8 contient le chiffre 7, seule case oĂč ce chiffre peut se mettre, si on considĂšre la colonne oĂč on se trouve.

Appliquons alors cette notation à la résolution d'un Sudoku à 17 données seulement faisant partie de ceux qui sont actuellement considérés comme les plus difficiles.

2° Exemple

Grille donnĂ©e : A1=1§D1=4§E2=7§G2=8§A4=4§H4=1§I4=6§B5=5§ E5=3§A6=2§I6=4§C7=8§G7=7§H7=3§D8=2§F8=6§G9=5

Résolution F5=4g §H6=5q §H9=6q §41(G3G8)>>G1=6 §2(E4F4)q>>G5=2xk § 8(H5I5)q>>8(B4B6)q>>A3=8q §7(H5I5)q&7(D9F9)q>>A8=7xk § 3(D9F9)>>A2=3xk §A7=5k §A5=6xk §A9=9 §B7=6q §4(G8H8)>>24(B9C9)>>I7=2q § 13(B8C8)>>I9=1q §37(D9F9)&42(B9C9)>>E9=8g §F1=8q §E8=5q §G3=1q §E7=4g § G8=4k §E6=1k §C5=1q §78(H5I5)q>>D5=9g §F7=9g §D7=1g §F2=1q §E3=6k § D6=6k §E1=9k §E4=2 §F3=2q §F4=5k §D4=8k §F6=7q § F9=3k §D9=7q §D3=3q §D2=5q §I1=3g §C2=6g §C1=5g §I3=5k § I5=7k §H5=8g §I8=8k §I2=9k §H8=9q §B6=8g §C9=2k § B9=4g §C3=4k §H2=4g §H1=2k §H3=7q §B1=7g §B2=2g § B3=9q §B8=1k §C8=3q §B4=3k §C4=7k §C6=9k §G4=9k §G6=3q

Perspectives L'introduction d'une notation pour la rĂ©solution des Sudokus permet alors de poser des ProblĂšmes de Sudoku, oĂč sont prĂ©sentĂ©es les situations de blocage qui constituent la partie la plus intĂ©ressante de ce jeu.

Notes et références[modifier | modifier le code]

  1. ↑ a et b Mark Swaney, Magic Squares.
  2. ↑ ProblĂšme VI « ProblĂšmes plaisants et dĂ©lectables qui se font par les nombres Â»
  3. ↑ (de) Sudoku Anleitung
  4. ↑ (fr) http://www.kuboku.com/
  5. ↑ (en) « http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html Â» (Archive ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?). ConsultĂ© le 2013-03-30
  6. ↑ (en) http://sudoku.top-notch.co.uk/wordoku.asp
  7. ↑ (en) http://www.mathrec.org/sudoku
  8. ↑ (en) http://sudoku.top-notch.co.uk/superwordoku.asp
  9. ↑ Walter T. Federer. Experimental design: theory and application. Macmillan, New York, 1955, 544 + 47 p. 
  10. ↑ Pierre Dagnelie. Avant le sudoku : le carrĂ© latin magique. Revue Modulad 39, 172-175, 2008 (ou document PDF)
  11. ↑ CarrĂ©s magiques en Chine
  12. ↑ (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.
  13. ↑ (en) « http://www.mathsisfun.net/SingleNumber.sit Â» (Archive ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?). ConsultĂ© le 2013-03-30
  14. ↑ (en) « http://www.mathsisfun.net/SingleNumber.prc Â» (Archive ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?). ConsultĂ© le 2013-03-30
  15. ↑ (en) G2, home of the discerning Sudoku addict,The Guardian, publiĂ© le 13 mai 2005
  16. ↑ (en) « The World’s Largest Sudoku Puzzle: Win ÂŁ5000, Sky One, consultĂ© le 28 mai 2009 Â» (Archive ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?). ConsultĂ© le 2013-03-30
  17. ↑ (en) [PDF]
  18. ↑ a, b, c, d, e et f (en) Denis Berthier, « The Hidden Logic of Sudoku Â», Lulu Publishers, ISBN 978-1-84753-472-9,‎ 16 mai 2007 (lire en ligne)
  19. ↑ (ja) http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
  20. ↑ (en) http://www.csse.uwa.edu.au/~gordon/sudokumin.php
  21. ↑ Sudoku enumeration problems
  22. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/ et suite A107739 de l'OEIS
  23. ↑ (en) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et suite A109741 de l'OEIS
  24. ↑ (ja) ăƒ—ăƒ­ă‚°ăƒ©ăƒŸăƒłă‚°ăƒ‘ă‚șăƒ«é›‘è«‡ă‚łăƒŒăƒŠăƒŒ
  25. ↑ (en) Minimum Sudoku
  26. ↑ Gary McGuire : There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
  27. ↑ http://passeurdesciences.blog.lemonde.fr/2012/01/08/17-est-le-nombre-de-dieu-au-sudoku/
  28. ↑ 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
  29. ↑ D'aprùs SadMan Software: Sudoku Solving Techniques - Naked Single / Singleton / Sole Candidate
  30. ↑ D'aprùs SudoCue - Sudoku Solving Guide
  31. ↑ a et b (en) Denis Berthier, « Constraint Resolution Theories Â», Lulu Publishers, ISBN 978-1-4478-6888-0,‎ 5 octobre 2011 (lire en ligne)
  32. ↑ a et b (en) Denis Berthier, « Pattern-Based Constraint Satisfaction and Logic Puzzles Â», Lulu Publishers, ISBN 978-1-291-20339-4,‎ 20 november 2012 (lire en ligne)
  33. ↑ a et b Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), December 4-12, 2009
  34. ↑ 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
  35. ↑ Voir Solution to the Easter Monster Puzzle: Formal Logic and Number Pair Chains ou Easter Monster pour une Ă©tude de la solution du « easter monster Â».
  36. ↑ (en) Knuth: Preprints

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • 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).
  • Denis Berthier, Constraint Resolution Theories, Lulu Publishers, novembre 2011, 308 pages (ISBN 978-1-4478-6888-0).
  • Denis Berthier, Pattern-Based Constraint Satisfaction and Logic Puzzles, Lulu Publishers, novembre 2012, 484 pages (ISBN 978-1-291-20339-4).
  • « 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; re-publiĂ© comme chapitre du livre Advanced Techniques in Computing Sciences and Software Engineering, Springer, 2010 (ISBN 9789094136599).
  • 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; re-publiĂ© comme chapitre du livre Advanced Techniques in Computing Sciences and Software Engineering, Springer, 2010 (ISBN 9789094136599).
  • Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), December 4-12, 2009; re-publiĂ© comme chapitre du livre Innovations in Computing Sciences and Software Engineering, Springer, 2010 (ISBN 97890481911133).

Articles connexes[modifier | modifier le code]

  • 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

Liens externes[modifier | modifier le code]

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.


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