AccueilđŸ‡«đŸ‡·Chercher

Sudoku

Le sudoku (æ•°ç‹Ź, prononcĂ© /sɯː.do.kÉŻ/ en japonais, /su.do.ku/ ou /sy.do.ky/ en français), 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.

Sudoku proposé par la presse.

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 rĂ©gion (Ă©galement appelĂ©e « bloc », « groupe », « secteur » ou « sous-grille »). La plupart du temps, les symboles sont des chiffres allant de 1 Ă  9, les rĂ©gions Ă©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.

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

Étymologie

Le nom sudoku (æ•°ç‹Ź) est nĂ© de l’abrĂ©viation de la rĂšgle japonaise du jeu « SĆ«ji wa dokushin ni kagiru » (æ•°ć­—ăŻç‹Źèș«ă«é™ă‚‹), signifiant littĂ©ralement « chiffre (æ•°ć­—) limitĂ© (限る) Ă  un seul (独èș«) » (sous-entendu par case, par ligne et par colonne). 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ɯː.do.kÉŻ] ; 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 » : [sy.do.ky]. Au Japon, Nikoli est toujours propriĂ©taire du nom sudoku[1] ; ses concurrents utilisent donc un autre nom : ils peuvent renvoyer au jeu par le nom amĂ©ricain original « Number Place[2] » (anglais : place numĂ©rale), ou encore par le mot « Nanpure » (ナンプレ), plus court. Quelques Ă©diteurs non japonais orthographient le titre « Su Doku ».

Histoire

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

Probablement inspirĂ© par le carrĂ© magique, ce jeu est tout d'abord connu des mathĂ©maticiens chinois, Ă  partir de -650, sous le nom Luoshu (掛äčŠ, LuĂČ shĆ«, « Livre de la riviĂšre Luo »). D'ordre 3, il pouvait alors ĂȘtre reprĂ©sentĂ© par diffĂ©rents symboles et utilisĂ© dans le feng shui.

Ce sont visiblement les Indiens, inventeurs des signes dits chiffres arabes, qui les limitĂšrent Ă  des chiffres[3], puis les Arabes, probablement vers le VIIe siĂšcle, lorsque leurs armĂ©es 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 Ă  Bagdad vers 983, l’EncyclopĂ©die de la FraternitĂ© de la puretĂ© (Rasa'il Ikhwan al-Safa)[3].

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 de 3 × 3 cases, dans ses ProblĂšmes plaisants et dĂ©lectables qui se font par les nombres, publiĂ© en 1612[4].

Le mathématicien suisse Leonhard Euler (1707-1783) crée ou au moins cite le « carré latin »[5], 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.

Dans l'hebdomadaire pour la jeunesse Le Petit Français illustré (numéro 7 du , p. 92), sous le titre général « ProblÚmes amusants » est proposé le jeu suivant : « Disposer les 9 chiffres, 1, 2, 3, 4, 5, 6, 7, 8, 9, dans les 9 cases de la figure ci-dessous, de telle façon que le total des 3 chiffres de chaque ligne verticale, horizontale et diagonale soit égal à 15. »

En 1892, en France, dans le quotidien monarchiste Le SiĂšcle, apparaĂźt la plus ancienne grille connue de sudoku[6]. Le , 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.

La version moderne du sudoku est inventée anonymement par l'Américain Howard Garns et publié pour la premiÚre fois en 1979 dans Dell Magazines sous le nom Number Place[7].

En , Maki Kaji (鍜æČ» 真蔷, 1951-2021[8]), directeur de la sociĂ©tĂ© Nikoli, publie pour la premiĂšre fois, dans sa revue mensuelle « Getsukan Nikoli suto » (æœˆćˆŠăƒ‹ă‚łăƒȘă‚čト), le jeu Number Place sous le nom « SĆ«ji wa dokushin ni kagiru » (æ•°ć­—ăŻç‹Źèș«ă«é™ă‚‹), plus tard « SĆ«doku » (æ•°ç‹Ź)[2].

RĂšgles de base

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

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 6×6 irrĂ©gulier (Suguru (ou autre)).
Sudoku par comparaison et sa solution.
Killer Su Doku (détail).

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

  • 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[9] ;
  • 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 (aussi appelĂ©s Suguru ou Tectonic).

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 seule 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

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

En français, cette variante alphabĂ©tique porte divers noms comme Sudoku lettres, Mokitu (TĂ©lĂ© 7 jours) ou Mysmo (LibĂ©ration). Certaines grilles se limitent aux mots ne comportant que des lettres diffĂ©rentes. D’autres acceptent des mots comportant plusieurs fois la mĂȘme lettre auquel cas elle a Ă  chaque fois une graphie diffĂ©rente, par exemple : MAHaRADJa. Le Custom Sudoku[12] crĂ©Ă© par Miguel Palomo admet par contre un mot avec de vraies lettres rĂ©pĂ©tĂ©es.

Le Code Doku[13] conçu par Steve Schaefer contient une phrase complĂšte, alors que le Super Wordoku[14] de Top Notch contient deux mots de neuf lettres, chacun se trouvant sur l’une des diagonales principales. Ces jeux ne sont pas considĂ©rĂ©s comme de vrais 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.

Précurseurs du Sudoku

Un ancĂȘtre du sudoku : le carrĂ© latin magique

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

Les expĂ©riences agronomiques en champ, gĂ©nĂ©ralement constituĂ©es d’un certain nombre de parcelles carrĂ©es ou rectangulaires, sont souvent organisĂ©es sous la forme de blocs alĂ©atoires complets, c’est-Ă -dire de groupes de parcelles voisines au sein desquels les diffĂ©rents Ă©lĂ©ments Ă  comparer (diffĂ©rentes fumures par exemple) sont tous prĂ©sents et rĂ©partis au hasard.

Quand le nombre total de parcelles disponibles est égal à un carré (16, 25, 36, etc.), une autre possibilité correspond à la notion de carré latin, qui est tel que les différents éléments à comparer sont présents dans chacune des lignes et dans chacune des colonnes de parcelles.

La superposition de ces deux dispositifs peut donner naissance Ă  ce qui a Ă©tĂ© appelĂ© carrĂ© latin magique, notamment par W.T. Federer[15] 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[16].

Emplois historiques des carrés magiques

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[17] (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

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 finalement Ă  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

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

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[19] et, en 1996, il récidive pour Palm OS[20].

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

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[21]. 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 la mathĂ©maticienne 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[22] 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 AntFal, 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

Structure logique

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

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,
  • et (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[24], 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[25] - [26], alors que 18 est le nombre minimum de dĂ©voilĂ©s pour les grilles 9×9 symĂ©triques.

Symétries des grilles

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 2×9!×(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

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 Ă 

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 à 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é[27] que ce nombre de grilles était de[27] - [28] - [29] :

Ce nombre 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[30] - [29]. Un catalogue complet de ces grilles a Ă©tĂ© constituĂ©.

Nombre de grilles incomplĂštes

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 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 problÚmes minimaux (voir la section « classification des problÚmes »).

Nombre minimal de révélés

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

Un révélé étant une case dont le contenu est visible sur une grille de sudoku, se pose le problÚme de leur nombre minimal.

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[31] - [32]. 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).

Rien ne dit que ce ne soit pas possible avec moins de nombres. 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[33] - [34] - [29].

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

Méthodes de résolution utilisées par les joueurs

Remarques préliminaires

  1. Il existe de nombreuses approches de la résolution des Sudokus, dont certaines ne sont praticables que par ordinateur. Il ne sera question ici que des méthodes utilisées par les joueurs.
  2. Il ne s’agit pas de donner une liste exhaustive de ces mĂ©thodes (ce qui nĂ©cessiterait un livre volumineux), mais un simple aperçu. De nombreuses variantes et extensions existent, comme les poissons Ă  nageoires (finned fish), trop spĂ©cialisĂ©es pour ĂȘtre dĂ©taillĂ©es ici.
  3. Quelles 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 problĂšmes. 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.

Principe

À un niveau Ă©lĂ©mentaire, il faut balayer la grille pour chaque chiffre de un Ă  neuf, et pour chaque bloc :

  • Regarder si le chiffre y figure ou pas ;
  • Si le chiffre y figure, regarder quelles sont les cases qu'il interdit sur les autres blocs en ligne ou en colonne ;
  • Si le chiffre n'y figure pas, regarder quelles sont les cases oĂč il ne peut pas figurer, compte tenu de la position des autres instances du mĂȘme chiffre dans les autres blocs en ligne ou en colonne.

Lorsqu'il n'y a qu'une seule possibilitĂ© pour une ligne, une colonne, ou un bloc, c'est nĂ©cessairement lĂ  que le chiffre doit s'inscrire. Avec un peu d'expĂ©rience, il est possible de visualiser les cases « allumĂ©es » sur l'ensemble de la grille, oĂč ce chiffre peut figurer, ce qui permet de dĂ©tecter des configurations plus avancĂ©es.

Quand un problĂšme 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 problĂšmes correspondent Ă  des niveaux « facile » ou « Ă©lĂ©mentaire ».

Singleton

Le « singleton » correspond au cas trivial 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 Ă  la fois 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Ă©

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

Inversement, le « singleton cachĂ© » est souvent facilement rĂ©vĂ©lĂ© par un balayage systĂ©matique des chiffres et des blocs, parce que sa position ne dĂ©pend que de la position du chiffre considĂ©rĂ© dans les blocs voisins, et de ce que les cases sont libres ou occupĂ©es dans le bloc considĂ©rĂ©. Dans l'exemple ci-contre, quand on en est Ă  estimer les possibilitĂ©s du « 4 » pour le bloc supĂ©rieur droit, la seule information nĂ©cessaire pour les cases du « 7 » et du « 8 » est qu'elles sont occupĂ©es par des chiffres diffĂ©rents de 4 ; la conclusion est la mĂȘme quel que le soit le chiffre contenu dans ces cases.

Élimination indirecte

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.

L'Ă©limination indirecte est un prolongement de l'Ă©limination directe.

Lorsqu'on balaye la grille pour localiser les cases admissibles pour un certain candidat, on peut se trouver dans la situation oĂč dans un bloc, les cases admissibles sont toutes localisĂ©es sur une mĂȘme ligne (ou une mĂȘme colonne). Dans ce cas, quelle que soit la position finale du candidat dans le bloc, cet alignement interdit pour le candidat les autres cases libres de cette mĂȘme ligne (ou colonne) situĂ©es dans les autres blocs. Autrement dit : si dans un bloc, les candidats sont sur une mĂȘme ligne, le candidat est exclu des autres cases libres de la ligne.

De mĂȘme, quand dans deux blocs en ligne, les candidats sont limitĂ©s Ă  deux lignes, les candidats du troisiĂšme bloc ne peuvent se trouver que sur la troisiĂšme ligne (et rĂ©ciproquement pour les colonnes).

Cette interdiction peut conduire Ă  identifier un singleton cachĂ©, comme dans le premier exemple ci-contre. Elle peut Ă©galement, de maniĂšre plus subtile, conduire Ă  conclure que dans un autre bloc de cette ligne (ou colonne), les candidats ne peuvent se situer que sur un mĂȘme ligne ou colonne, conduisant de proche en proche Ă  une Ă©limination indirecte en chaĂźne. Cette premiĂšre application de l'Ă©limination indirecte peut par consĂ©quent se faire sans marquage, mais demande plus de rĂ©flexion.

Exemple d'Ă©liminations indirectes en cascade.

Dans l'exemple ci-contre, aprÚs que les paires identifiables ont été marquées, l'examen du candidat "1" permet par exemple d'identifier deux singletons, en enchaßnant quatre éliminations indirectes. Il n'y a qu'un seul "1" dans la cellule "Aa", ce qui interdit la présence d'un autre "1" en ligne "A" et en colonne "a" (en jaune).

  • On commence par raisonner sur les blocs de la verticale centrale pour faire deux Ă©liminations indirectes :
    • Dans le bloc supĂ©rieur central, il ne peut donc y avoir de "1" que sur la colonne "d" (en vert), excluant ce mĂȘme candidat sur le reste de la colonne.
    • Par consĂ©quent, dans le bloc infĂ©rieur central, le "1" ne peut se trouver que sur la colonne "e", excluant ce mĂȘme candidat sur le reste de la colonne.
    • Et donc, dans le bloc central, le candidat "1" ne peut se trouver que sur la colonne "f" (en bleu).
  • On raisonne Ă  prĂ©sent sur les blocs de l'horizontale centrale pour une Ă©limination indirecte sur deux lignes :
    • Dans le bloc central, "1" ne peut que se trouver sur les lignes "E&F" (en bleu).
    • Mais dans le bloc de centre gauche, le "1" est restreint Ă  ces mĂȘmes lignes "E&F" (en vert).
    • Par consĂ©quent, dans le bloc de centre droit, le "1" se trouve nĂ©cessairement sur la ligne "D" (en bleu).
  • De lĂ , on examine les blocs de droite pour une seconde Ă©limination sur deux lignes :
    • Dans le bloc de centre droit, le "1" est Ă  prĂ©sent restreint aux colonnes "h&j" (en bleu).
    • Mais dans le bloc supĂ©rieur droit, le "1" est Ă©galement restreint Ă  ces mĂȘmes colonnes (en vert).
    • Donc, dans le bloc infĂ©rieur droit, le "1" ne peut pas se trouver dans les colonnes "h&j" (en jaune).
  • On voit Ă  prĂ©sent que sur la ligne "J", les deux cellules qui avaient Ă©tĂ© marquĂ©es des paires "12" et "13" ne peuvent donc pas recevoir un "1" ; leur valeur est donc nĂ©cessairement "2" et "3".

Principe

La deuxiĂšme mĂ©thode de balayage consiste Ă  se demander, sur un groupe donnĂ© (ligne, colonne ou bloc) : (1) quels sont les manquants, et (2) oĂč peuvent-ils se trouver. L'objet est d'identifier des « singletons cachĂ©s », et Ă  dĂ©faut, des paires Ă  marquer.

Cette mĂ©thode est particuliĂšrement triviale dans le cas oĂč il ne manque qu'un seul chiffre dans l'entitĂ©, dans ce cas la case est un « singleton », Ă  la fois un « singleton nu » et un « singleton cachĂ© », et sa solution est immĂ©diate.

Elle est d'autant plus fructueuse qu'il y a plus de cases remplies sur l'entitĂ© considĂ©rĂ©e. Elle peut donc ĂȘtre faite d'office dĂšs qu'une entitĂ© n'a plus que deux cases vides (inscription directe des paires), puis, par ordre de prĂ©fĂ©rence, quand une entitĂ© n'a plus que trois, quatre, voire cinq cases vides. Un balayage Ă  « six cases vides » ne donnera des fruits qu'exceptionnellement (mais peut en donner).

Singleton nu

Exemple de grille avec un « singleton nu » : la colonne d doit ĂȘtre complĂ©tĂ©e par « 14589 », et sur la ligne C seule la valeur « 9 » est possible.

Si une cellule n'accepte qu'un unique candidat, alors c’est la valeur de cette cellule. C'est ce que l'on appelle un « singleton nu ». Le cas a d'autant plus de chance de se produire 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 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)[35]. 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[36]


Marquage des doublets

Dans ce type de balayage, il est utile de marquer directement les paires, c'est-Ă -dire les cases de la grille oĂč il ne reste plus que deux candidats. Ces cases peuvent ĂȘtre remplies par le couple de chiffres, inscrits en petit ou au crayon ; et la seule Ă©volution possible pour de telles cases est de basculer sur l'une ou l'autre de ces valeurs. L'avantage de ce marquage est double :

  • Dans le balayage « Ă©lĂ©mentaire » prĂ©cĂ©dent, il permet dans certains cas (quand une mĂȘme paire est sur la mĂȘme ligne, colonne, ou bloc) de faire comme si ces deux chiffres Ă©taient effectivement prĂ©sents sur la grille pour bloquer les possibilitĂ©s associĂ©es aux autres cases.
  • En fin de problĂšme, ces cases permettent de terminer trĂšs rapidement une grille, puisque dĂšs qu'une des valeurs de la paire est trouvĂ©e sur une autre case liĂ©e (en ligne, en colonne, ou dans le bloc), on peut immĂ©diatement inscrire l'autre valeur comme valeur effective, sans avoir Ă  refaire tout le raisonnement qui avait conduit initialement Ă  limiter les possibilitĂ©s Ă  deux valeurs.

Marquage des paires

Le marquage des paires constitue le second niveau de résolution des sudokus. « Marquer une paire » sur une case donnée consiste à noter que sur cette case, il n'y a que deux candidats possibles.

Le marquage peut se faire simplement en mettant dans la case les deux chiffres candidats, mais en Ă©criture suffisamment petite pour ĂȘtre oblitĂ©rĂ©e par la valeur dĂ©finitive. Il n'y a qu'une seule maniĂšre d'apporter de l’information Ă  une case portant une paire, c'est en donnant la valeur effective ; de ce fait, le marquage des paires ne conduit pas Ă  des surcharges graphiques trop importantes.

Il est important, Ă  ce stade, de remarquer que si le marquage direct des possibilitĂ©s limitĂ©es aux paires dans une case est effectivement utile, marquer ainsi les possibilitĂ©s plus Ă©tendues (trois, quatre candidats possibles,...) n'a au contraire aucun intĂ©rĂȘt (et constitue une pratique de dĂ©butant).

Paires couplées

La paire « 78 » apparaßt deux fois sur la colonne « e », interdisant ces deux valeurs dans les autres cases de la colonne.

Lorsque les paires sont marquĂ©es, on peut rencontrer une mĂȘme paire de candidats dans deux cases d'un mĂȘme groupe (ligne, colonne ou bloc). Dans ce cas, les deux cases occupĂ©es par la paire sont couplĂ©es et fonctionnent comme s'ils Ă©taient occupĂ©s par les candidats correspondants, interdisant ces deux candidats Ă  toutes les autres cases libres de ce mĂȘme groupe (ligne, colonne ou bloc).

Quelques cas particuliers sont facilement identifiables :

  • Lorsqu'il ne reste plus que deux cases libres sur une ligne ou une colonne, ces deux cases forment par construction une paire nue ; et si elles sont situĂ©es dans un mĂȘme bloc, elles interdisent ces valeurs au reste du bloc.
  • Lorsqu'une paire couplĂ©e apparaĂźt dans un groupe ayant trois cases libres, la troisiĂšme case n'a qu'une valeur possible : c'est un singleton nu.
  • Lorsqu'une paire couplĂ©e apparaĂźt dans un groupe ayant quatre cases libres, les deux cases restantes forment nĂ©cessairement une paire sur laquelle les deux autres valeurs restantes sont possibles : c'est une paire cachĂ©e.

La prise en compte de ces paires couplĂ©es peut conduire Ă  noter de nouvelles paires. Dans l'exemple ci-contre, la recherche des candidats possibles a conduit notamment Ă  identifier deux paires « 78 » sur la colonne « e ». Sur les six cases vides de la colonne, il n'y en a donc que quatre qui sont rĂ©ellement libres, puisque deux peuvent ĂȘtre considĂ©rĂ©es comme quasi remplies.

  • En recherchant oĂč les quatre autres valeurs « 1459 » peuvent ĂȘtre localisĂ©es sur cette mĂȘme colonne, on identifie une nouvelle paire « 14 » en ligne A, et deux paires « 59 » en lignes D et J.
  • La case restante en ligne F est donc Ă©galement une paire « 14 ».

Élimination indirecte

Lorsqu'on balaye la grille pour localiser les cases admissibles pour un certain candidat, on peut se trouver dans la situation oĂč le candidat en cours d'examen figure dans une paire couplĂ©e sur une mĂȘme ligne ou colonne. Dans ce cas, le candidat est exclu du reste de cette ligne (ou colonne), limitant les possibilitĂ©s dans les autres blocs touchĂ©s par cette ligne (ou colonne).

Paires cachées

Trois paires cachées marquées en jaune.

Les « paires cachĂ©es » demandent gĂ©nĂ©ralement une recherche systĂ©matique pour ĂȘtre dĂ©tectĂ©es. Pour les dĂ©tecter, il faut effectuer un balayage systĂ©matique par bloc (ligne, colonne, ou carrĂ©). Sur chaque bloc, il faut se poser la question « oĂč sont les 1 » [...] « oĂč sont les 9 ». Si un des chiffres ne peut ĂȘtre que dans deux emplacements possibles, il est possible qu'il fasse partie d'une paire cachĂ©e ; et si un autre chiffre ne peut ĂȘtre que dans ces deux mĂȘmes emplacements, ces deux chiffres forment ensemble une « paire cachĂ©e ». Dans ce cas, parce que ces deux chiffres ne peuvent qu'ĂȘtre Ă  ces deux emplacements, il n'est pas possible qu'un autre chiffre se trouve sur ces mĂȘmes emplacements, ce qui Ă©limine les possibilitĂ©s correspondantes pour les autres chiffres.

La recherche des paires cachĂ©es est beaucoup plus fastidieuse, parce qu'elle porte thĂ©oriquement sur les 3x9=27 blocs, pour lesquels il faut vĂ©rifier si l'une des 9x8/2=36 paires possibles ne peut occuper que deux parmi 9 cases possibles. Il est possible d'accĂ©lĂ©rer un peu cette recherche, en remarquant d'une part que si la recherche est systĂ©matique, une fois la paire "a-b" testĂ©e il est inutile de tester la paire "b-a", et surtout, d’autre part, que si une case est dĂ©jĂ  occupĂ©e par un doublet, une Ă©ventuelle paire cachĂ©e ne peut porter que sur ces deux mĂȘmes Ă©lĂ©ments.

Par exemple, sur la figure ci-jointe, trois paires cachées ont été identifiées, qui permettent de remplir une case chacune :

  • Les cases B-bc (jaune) sont les seules du carrĂ© supĂ©rieur gauche oĂč peuvent ĂȘtre prĂ©sentes les valeurs 6 et 7 ; de ce fait, le 5 n'est possible dans ce carrĂ© qu'en Ab (vert).
  • Sur la ligne C, les cases C-df (jaune) sont les seules de la ligne pouvant recevoir les valeurs 4 et 8 ; de ce fait, le 3 n'est possible dans cette ligne qu'en Ca (vert).
  • Sur la ligne I, les cases I-ef (jaune) sont les seules de la ligne Ă  pouvoir recevoir les valeurs 3 et 8 ; de ce fait, le 5 n'est possible qu'en Ih (vert).

Triplets nus

Lorsqu'on recherche les manquants sur un groupe oĂč les paires sont marquĂ©es, on peut se trouver dans la situation oĂč le groupe affiche deux paires « ab » et « bc » ayant un Ă©lĂ©ment « b » en commun. Il convient alors d'examiner si une autre case de ce groupe n'admet comme valeurs possibles que ces trois mĂȘmes valeurs « abc ». Si c'est le cas, ces trois valeurs se rĂ©partissent nĂ©cessairement sur ces trois cases, et sont par consĂ©quent exclues des autres cases libres du groupe :

  • Si le groupe n'a que quatre cases libres, la quatriĂšme est nĂ©cessairement un singleton.
  • Si le groupe a cinq cases libres, les deux autres forment nĂ©cessairement une paire couplĂ©e.
  • D'une maniĂšre gĂ©nĂ©rale, il devient possible de rechercher singletons et paires sur les autres cases libres du groupe, en excluant ces trois valeurs « abc ».

Gestion des nombres candidats

Un exemple de la notation pointée.
Un exemple de la notation pointée.

Ces recherches sont plus laborieuses que les prĂ©cĂ©dentes, et pour les conduire systĂ©matiquement, il est plus facile de marquer les cellules. 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[24]) ; ils font appel Ă  la logique Ă©pistĂ©mique. L’article From Constraints to Resolution Rules, Part I: Conceptual Framework[37], 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. La position relative du point indique le chiffre manquant. Par exemple, pour reprĂ©senter le chiffre 1, le joueur positionnera son point en haut Ă  gauche de la cellule (cf schĂ©ma ci-dessus). 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.

Élimination indirecte - interactions ligne-bloc et colonne-bloc

Lorsqu'on utilise un marquage des candidats possibles, la méthode d'élimination indirecte (mentionnée ci-dessus dans les méthodes « faciles ») se décline alors en deux cas permettant d'exclure certains candidats :

  • Comme prĂ©cĂ©demment, si dans un bloc, les candidats se concentrent sur une mĂȘme ligne (ou colonne), le candidat est exclu sur le reste de la ligne (ou colonne). Ce premier cas se rencontrait dĂ©jĂ  dans les mĂ©thodes simples, parce qu'il permet parfois d'identifier un singleton cachĂ©.
  • De plus Ă  prĂ©sent, si dans une ligne (ou colonne) les candidats se concentrent sur un mĂȘme bloc, le candidat est exclu du reste du bloc. Ce deuxiĂšme cas ne peut jamais conduire Ă  identifier un singleton cachĂ©.

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.

Groupes nus et cachés

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 n (couramment de deux Ă  quatre) nombres dont la prĂ©sence est possible dans un nombre Ă©gal de cases vides et prĂ©sentant une configuration remarquable, soit que la prĂ©sence de ces nombres soit impossible dans les autres cases de la mĂȘme rĂ©gion, soit qu'aucun autre nombre ne puisse apparaĂźtre dans les cases du groupe :

  • si seuls les nombres du groupe peuvent apparaĂźtre dans les cases (mais la prĂ©sence de ces nombres est Ă©ventuellement possible dans d'autres cases de la mĂȘme rĂ©gion) : il s'agit alors d'un « groupe nu » ;
  • si les nombres du groupe ne peuvent pas apparaĂźtre dans d'autres cases de la mĂȘme rĂ©gion (mais d'autres nombres peuvent Ă©ventuellement apparaĂźtre dans les cases du groupe) : il s'agit alors d'un « groupe cachĂ© ».

On voit que ces définitions sont symétriques : si un groupe de n cases vides dans une région forme un groupe nu avec n candidats, les autres cases vides formeront un groupe caché (avec un nombre éventuellement différent de membres) avec le reste des candidats ; et inversement.

La recherche des singletons cachĂ©s a dĂ©jĂ  Ă©tĂ© faite avec le balayage Ă©lĂ©mentaire, et les singletons nus ont dĂ©jĂ  Ă©tĂ© identifiĂ©s avec la recherche des manquants et le marquage des paires. De mĂȘme, les paires nues couplĂ©es peuvent ĂȘtre identifiĂ©es par un simple marquage des paires. Ces groupes nus et cachĂ©s non triviaux ne peuvent apporter du nouveau 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 au moins quatre cases libres ou plus. 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 telle rĂ©gion a Ă©tĂ© rĂ©duite, il n'est plus nĂ©cessaire de l'examiner par la suite.

La méthode ne trouve sa pleine application qu'à partir de cinq cases libres et la recherche de triplets nus : une région de cinq cases libres peut comporter un triplet nu (et une paire cachée), une région de six cases peut comporter un triplet ou un quadruplet nu (et, respectivement, un triplet ou une paire cachée), et ainsi de suite.

Quel que soit le groupe identifié, on peut alors éliminer les candidats:

  • si le groupe identifiĂ© est nu, on peut le « cacher », en supprimant ses candidats des autres cases de la rĂ©gion ;
  • s'il est cachĂ©, on peut le « dĂ©nuder », en supprimant du groupes les candidats qui n'en font pas partie.

AprÚs cette réduction, la situation est celle d'une exclusion mutuelle : les nombres du groupe n'apparaissent pas ailleurs, et il n'y a que les nombres du groupe dans les cases.

Groupes nus

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 traitement des « paires liĂ©es » a Ă©tĂ© dĂ©crit avec le marquage des paires, et la possibilitĂ© d'identifier parfois quelques « triplets nus » y avait Ă©tĂ© signalĂ©e. Les « groupes nus » sont le cas plus gĂ©nĂ©ral de ce traitement. 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) ; mais il demande en pratique de marquer les candidats.

La rĂšgle est la suivante. Si dans une mĂȘme rĂ©gion (ligne, colonne ou bloc), on observe un groupe de trois cases pour lesquelles :
i) il y a au plus trois candidats, et
ii) tous ces candidats sont pris parmi les trois mĂȘmes valeurs ;
alors nĂ©cessairement, ces trois valeurs devront ĂȘtre prises sur ces trois cases, et ne peuvent pas aller ailleurs dans cette rĂ©gion. La dĂ©monstration se fait par l'absurde : si l'une de ces trois valeurs candidates Ă©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 nus exploitables par cette méthode comprennent deux, trois ou quatre éléments. On peut remarquer en effet 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.

Recherche des « groupes nus »

La recherche des « groupes nus » se fait aprÚs marquage des candidats, par balayage systématique des cases contenant deux, trois ou quatre candidats. Les étapes en sont typiquement, par ordre de difficulté croissante :

  • Sur une case Ă  deux candidats, on recherche sur les trois rĂ©gions associĂ©es (ligne, colonne ou bloc) si une autre case contient les deux mĂȘmes candidats.
  • À dĂ©faut, sur une case Ă  deux candidats, on recherche s'il existe dans la rĂ©gion deux autres cases ayant deux candidats dont un commun, ouvrant la possibilitĂ© d'un triplet liĂ© incomplet (voire d'un quadruplet liĂ© incomplet).

Ces deux premiers balayages peuvent ĂȘtre effectuĂ©s mĂȘme lorsque seules les paires candidates sont marquĂ©es.

Si ce premier balayage a échoué, un « groupe nu » aura nécessairement au moins trois candidats, dont au moins une case complÚte (sinon le groupe aurait été détecté dans l'étape précédente). Il formera donc formera un triplet ou un quadruplet :

  • Sur une case Ă  trois candidats, on recherche de mĂȘme sur les trois rĂ©gions associĂ©es si deux autres cases (y compris, le cas Ă©chĂ©ant, celles n'ayant que deux candidats) prennent leurs candidats dans ces trois mĂȘmes valeurs.
  • À dĂ©faut, on recherche s'il existe des cases de trois candidats dont deux communs, ouvrant la possibilitĂ© d'un quadruplet liĂ© incomplet.

Si ce second balayage a Ă©chouĂ©, un Ă©ventuel « groupe nu » aura nĂ©cessairement quatre candidat, dont au moins une case complĂšte. En dernier ressort, on peut rechercher sur toutes les cases Ă  quatre candidats si ces quatre mĂȘmes candidats se retrouvent sur quatre cases diffĂ©rentes de la mĂȘme rĂ©gion.

Groupes cachés

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

Une premiÚre remarque est que le complémentaire d'un groupe caché est un groupe nu : si sur les n+c cases libres, un sous-ensemble de c cases forment un « groupe caché » de c candidats (c'est-à-dire que ces c candidats n'apparaissent pas dans les n autres cases), le reste des n cases forme de son cÎté un groupe nu de n candidats (c'est-à-dire que les candidats du groupe c n'y figurent pas).

Pour rechercher un groupe cachĂ©, il faut chercher un groupe de c valeurs dont les candidats n'apparaissent que sur c 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. Alternativement, on peut chercher ce mĂȘme groupe de c valeurs, qui soient exclues de n cases libres du groupe.

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.

L'identification des groupes cachés peut souvent se faire indirectement par l'identification de groupes nus de taille supérieure. Dans l'exemple ci-contre, la recherche d'un triplet nu en colonne "f" conduit à remarquer le groupe "367" en Df et Ff.

  • Il n'y a pas d'autre case en colonne "f" limitĂ©e aux candidats "367", mais le "3678" en Ef suggĂšre d'Ă©tendre la recherche Ă  des quadruplets nus.
  • Il n'y a pas d'autre case en colonne "f" limitĂ©e aux candidats "3678", mais deux nouvelles cases y sont presque, en y ajoutant le candidat "9" : les cases Cf et Hf.

On a ainsi trouvé de proche en proche un groupe nu de cinq candidats "36789". Le complémentaire, correspondant aux cases Af, Gf et Jf, correspond dont à un groupe caché de trois valeurs "124".

La recherche directe d'un groupe caché porte sur des petits groupes de deux à trois candidats (exceptionnellement quatre), donc ne peut pas porter sur des candidats apparaissant plus souvent dans la région considérée. La recherche consiste à déterminer d'abord les candidats susceptibles de former un groupe caché dans la région, puis de vérifier sur les candidats identifiés s'ils forment effectivement un tel groupe. Pour reprendre l'exemple ci-contre :

  • La recherche directe d'un triplet cachĂ© en colonne "f" conduit Ă  limiter les membres potentiels aux candidats "1" (deux apparitions), "2", "4" et "9" (trois apparitions). Un triplet cachĂ© ne peut donc porter que sur les candidats "1249", l'un d'entre eux Ă©tant de trop.
  • Un candidat apparaissant trois fois apparaĂźtra dans les trois cases du triplet cachĂ©. Le candidat "9" apparaissant deux fois sans le reste du groupe, il n'est pas possible qu'il fasse partie d'un triplet cachĂ© sur cette base, puisqu'il faudrait qu'un autre candidat du triplet fasse toutes ses apparitions sur une derniĂšre case unique.
  • Les candidats Ă  tester se limitent donc Ă  "124", et une vĂ©rification rapide montre qu'ils forment effectivement un triplet cachĂ©.

Fish ou Poissons (X-Wing, Swordfish, Jellyfish)

X-wing sur les lignes F et J pour 8 : Les deux lignes F et J ont toutes deux 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 (exemple : 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

Dans The Hidden Logic of Sudoku[24], 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 Jellyfish, 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

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

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 types de chaĂźnes.

Généralisations des chaßnes xy : chaßnes d'ALS et chaßnes nrczt

Parmi les généralisations logiques « naturelles » des chaßnes xy, on a :

  • les chaĂźnes d’ALS (Almost Locked Sets), les plus anciennes et de loin les plus utilisĂ©es par les joueurs sur les forums de Sudoku ; un maillon de ces chaĂźnes n’est plus un candidat mais un ALS (Almost Locked Sets), c’est-Ă -dire un ensemble de k cellules (sur une mĂȘme ligne, une mĂȘme colonne ou dans un mĂȘme bloc) dont les candidats appartiennent Ă  un ensemble de k+1 nombres ;
  • les chaĂźnes xyt, xyz et xyzt ainsi que leurs 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[24])) ;
  • 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é

On exige en gĂ©nĂ©ral d’un problĂšme, 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 problĂšmes.

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 problĂšme 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 problĂšme 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 problĂšmes vĂ©rifient dĂ©sormais plus sĂ©rieusement l’unicitĂ©.

Le principe du rectangle interdit

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

ab ab

ab ab

alors pour toute solution du problĂšme 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 problĂšme 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

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 problĂšmes

Il n’existe pas de classification universelle des diffĂ©rents problĂšmes : 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 problĂšmes 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 problĂšmes ayant la mĂȘme valeur dans une classification peuvent prĂ©senter des difficultĂ©s trĂšs diffĂ©rentes.

Préambule sur les problÚmes minimaux et les statistiques de classification des puzzles

Une notion gĂ©nĂ©rale trĂšs utile d’un point de vue thĂ©orique est celle de problĂšme minimal. Un problĂšme 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 problĂšmes, 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 problĂšmes 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 problĂšmes. 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 problĂšmes 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 problĂšmes 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 problĂšmes 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[38], Pattern-Based Constraint Satisfaction and Logic Puzzles[39] ou l'article disponible sur le site de son auteur Unbiased Statistics of a CSP - A Controlled-Bias Generator[40].

SER (Sudoku Explainer Rating)

Le SER (Sudoku Explainer Rating) est de loin la classification la plus utilisĂ©e. Sudoku Explainer est un logiciel libre (en java), dĂ©veloppĂ© par Nicolas Juillerat et tĂ©lĂ©chargeable sur le web. Il peut ĂȘtre utilisĂ© pour rĂ©soudre des problĂšmes 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 problĂšmes 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’est-Ă -dire 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

Cette classification, dĂ©finie dans The Hidden Logic of Sudoku[24], est basĂ©e sur la longueur maximale de la chaĂźne nrczt nĂ©cessaire pour rĂ©soudre un problĂšme. 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 problĂšmes 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 problĂšme.

Statistiques de la classification nrczt

Les statistiques de la classification nrczt sont accessibles :

  • dans trois livres : The Hidden Logic of Sudoku[24], Constraint Resolution Theories[38] et Pattern-Based Constraint Satisfaction and Logic Puzzles[39]
  • et dans deux articles du mĂȘme auteur : From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E[41] (sur la base de 10 000 problĂšmes minimaux alĂ©atoires) et Unbiased Statistics of a CSP - A Controlled-Bias Generator[40].

Les résultats suivants sont basés sur le nouveau générateur à biais contrÎlé (et sur Presque six millions de problÚmes minimaux aléatoires); ils sont non biaisés. Ce générateur et la vaste collection associée sont accessibles sur la plateforme GitHub : https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection

Le résolveur de Sudokus ayant servi à établir cette classification (SudoRules, partie du logiciel plus général de résolution de contraintes CSP-Rules) est accessible sur la plateforme GitHub : https://github.com/denis-berthier/CSP-Rules-V2.1

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,005 5
  • niveau 11 : 0,001 5

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

  1. une trÚs grande majorité des problÚmes peut se résoudre par des techniques relativement simples (ici, des chaßnes courtes) ;
  2. il reste malgré tout des problÚmes 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 problĂšmes exceptionnellement complexes (comme le fameux Easter Monster[42]) 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 problĂšmes minimaux (3,10 Ă— 1037) ainsi que le nombre de problĂšmes minimaux non Ă©quivalents (2,55 Ă— 1025).

Classifications des problÚmes « grand public »

La plupart des auteurs des manuels sur le sudoku sont d’accord sur le fait que plusieurs facteurs influent sur la difficultĂ© de ces problĂšmes dont l’équation de base tient compte modulo une certaine pondĂ©ration :

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

Cependant, cette question de difficultĂ© fait toujours l’objet de nombreux dĂ©bats dans les forums sur le sudoku, car elle est liĂ©e aux concepts et reprĂ©sentations visuelles que chacun est prĂȘt Ă  adopter. Mais elle peut ĂȘtre complĂštement Ă©lucidĂ©e si l'on hiĂ©rarchise, du simple au complexe, les techniques et procĂ©dĂ©s que l'on peut utiliser pour rĂ©ussir une grille, et si l'on considĂšre notre maniĂšre de jouer (observer certaines rĂšgles de 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

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

Utilisation des techniques permettant le traitement des cellules-Ă -candidats-multiples selon une seule dimension ; ligne, colonne ou rĂ©gion, dont « l’élimination Ă  cause des paires nues », « le dĂ©graissage des candidats cachĂ©s » et « le dĂ©graissage des paires camouflĂ©es ». Certaines grilles de type 2 peuvent ĂȘtre rĂ©ussies, comme pour le type 1, mentalement. D’autres, d’un niveau supĂ©rieur, nĂ©cessitent que l’on inscrive, au fur et Ă  mesure, les candidats dans les cellules d’une rĂ©gion, une ligne ou une colonne, sans toutefois le faire pour toutes les cellules vides, et voir si l’on peut simplifier les multiples par l’une des trois techniques prĂ©cĂ©dentes. Les plus difficiles des grilles de ce type 2 ne se prĂȘtent Ă  la rĂ©solution qu’une fois que 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 bloc 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

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

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

Certains journaux, magazines, sites et logiciels livrent des grilles dites «diaboliques» voire «infernales». Le plus souvent, ces grilles peuvent ĂȘtre rĂ©solues par les techniques mises au point jusqu’à ce jour, et sont beaucoup moins difficiles qu'il n'y parait. En effet, 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 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

Solutions logicielles

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

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

Bien que cet algorithme ne soit pas trĂšs Ă©lĂ©gant, il est certain de trouver une solution s’il en existe. Une grille 9×9 est habituellement rĂ©solue en moins de trois secondes avec un ordinateur personnel moderne qui a recours Ă  un interprĂ©teur, et en quelques millisecondes avec un langage compilĂ©. Cependant, il existe des grilles qui sont particuliĂšrement difficiles Ă  rĂ©soudre par backtracking (voir (en) Algorithmics of Sudoku#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[43]), 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, 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 9×9×9 variables boolĂ©ennes pour modĂ©liser une grille de sudoku 9×9. 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 → ! ( x_h_j_k), celles de ligne de la forme x_i_j_k → ! ( x_i_h_k) et celle de prĂ©sence d'un chiffre pour toute case i,j de la forme 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, 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). Des implĂ©mentations libres sont disponibles[44].

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, dĂ©sormais public, est basĂ© sur des techniques d’intelligence artificielle; il fait partie d'un logiciel plus gĂ©nĂ©ral de rĂ©solution de problĂšmes de satisfaction de contraintes (qui inclut aussi d'autres jeux logiques). Il est disponible sur la plateforme GitHub : https://github.com/denis-berthier/CSP-Rules-V2.1.

Construction de grilles

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 beaucoup d'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 problĂšmes minimaux (plusieurs dizaines Ă  la seconde) est disponible sur le Web.

La minimalitĂ© est une exigence annexe parfois attendue du crĂ©ateur de problĂšmes, 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 problĂšmes qui Ă  la fois soient minimaux et aient certaines symĂ©tries (en particulier, suexg ne le fait pas).

Notes et références

  1. « メンテナンă‚čæƒ…ć ± (Maintenance information) / J-PlatPat/AIPN », sur j-platpat.inpit.go.jp (consultĂ© le ).
  2. « Sudoku Variations », sur Mathpuzzle (consulté le ).
  3. (en) Mark Swaney, Magic Squares.
  4. ProblÚme VI « ProblÚmes plaisants et délectables qui se font par les nombres ».
  5. (de) Sudoku Anleitung.
  6. Jean Robin, « L'inventeur du sudoku est français », sur leparisien.fr, (consulté le ).
  7. http://www.time.com/time/magazine/article/0,9171,2137423,00.html
  8. « Japon : Le "pÚre du Sudoku" est mort à 69 ans », sur BFMTV, (consulté le ).
  9. (fr) http://www.kuboku.com/
  10. (en) « http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoko/sudoku_word.html »(Archive.org ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?) (consultĂ© le ).
  11. (en) http://sudoku.top-notch.co.uk/wordoku.asp
  12. « Custom Sudoku »
  13. (en) http://www.mathrec.org/sudoku
  14. (en) http://sudoku.top-notch.co.uk/superwordoku.asp
  15. (en)Walter T. Federer. Experimental design: theory and application. Macmillan, New York, 1955, 544 + 47 p.
  16. Pierre Dagnelie. Avant le sudoku : le carré latin magique. Revue Modulad 39, 172-175, 2008 (ou [PDF]).
  17. Carrés magiques en Chine.
  18. (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.
  19. (en) « http://www.mathsisfun.net/SingleNumber.sit »(Archive.org ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?) (consultĂ© le ).
  20. (en) « http://www.mathsisfun.net/SingleNumber.prc »(Archive.org ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?) (consultĂ© le ).
  21. (en) G2, home of the discerning Sudoku addict, The Guardian, publié le 13 mai 2005.
  22. (en) « The World’s Largest Sudoku Puzzle: Win ÂŁ5000, Sky One, consultĂ© le 28 mai 2009 »(Archive.org ‱ Wikiwix ‱ Archive.is ‱ Google ‱ Que faire ?) (consultĂ© le ).
  23. (en) [PDF].
  24. (en) Denis Berthier, « The Hidden Logic of Sudoku », Lulu Publishers,‎ (ISBN 978-1-84753-472-9, lire en ligne, consultĂ© le ).
  25. (ja) http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
  26. (en) http://www.csse.uwa.edu.au/~gordon/sudokumin.php
  27. (en) Sudoku enumeration problems.
  28. suite A107739 de l'OEIS.
  29. Jean-Paul Delahaye, Le problĂšme du Sudoku, Pour la science no 447, janvier 2015, p. 76-81
  30. (en) http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html et suite A109741 de l'OEIS
  31. (ja) ăƒ—ăƒ­ă‚°ăƒ©ăƒŸăƒłă‚°ăƒ‘ă‚șăƒ«é›‘è«‡ă‚łăƒŒăƒŠăƒŒ.
  32. (en) Minimum Sudoku.
  33. (en) Gary McGuire : There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem[PDF].
  34. Pierre Barthélémy, « 17 est le nombre de Dieu au sudoku », sur lemonde.fr, (consulté le ).
  35. D'aprĂšs (en)SadMan Software: Sudoku Solving Techniques - Naked Single / Singleton / Sole Candidate.
  36. D'aprĂšs (en)SudoCue - Sudoku Solving Guide.
  37. (en) 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.
  38. (en) Denis Berthier, « Constraint Resolution Theories », Lulu Publishers,‎ (ISBN 978-1-4478-6888-0, lire en ligne, consultĂ© le ).
  39. (en) Denis Berthier, « Pattern-Based Constraint Satisfaction and Logic Puzzles », Lulu Publishers,‎ (ISBN 978-1-291-20339-4, lire en ligne, consultĂ© le ).
  40. Denis Berthier, Unbiased Statistics of a CSP - A Controlled-Bias Generator, International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), 4-12 décembre 2009.
  41. 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), 5-13 décembre 2008.
  42. Voir (en)Solution to the Easter Monster Puzzle: Formal Logic and Number Pair Chains ou (en)Easter Monster pour une étude de la solution du « easter monster ».
  43. (en) Knuth: Preprints.
  44. « robdd based sudoku solver »

Voir aussi

Bibliographie

  • Narendra Jussien, PrĂ©cis de Sudoku, HermĂšs Lavoisier, 2006, 188 pages (ISBN 2-7462-1559-4).
  • (en) Denis Berthier, The Hidden Logic of Sudoku, Lulu Publishers ; 1re Ă©dition, , 384 pages (ISBN 978-1-84753-472-9) ; deuxiĂšme Ă©dition, , 416 pages (ISBN 978-1-84799-214-7).
  • (en) Denis Berthier, Constraint Resolution Theories, Lulu Publishers, , 308 pages (ISBN 978-1-4478-6888-0).
  • (en) Denis Berthier, Pattern-Based Constraint Satisfaction and Logic Puzzles, Lulu Publishers, , 484 pages (ISBN 978-1-291-20339-4).
  • « Le tsunami du sudoku », Pour la science, no 338, , p. 144.
  • (en) 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 (OCLC 5662041121).
  • (en) 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 (OCLC 5661887312).
  • (en) 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 DOI 10.1007/978-90-481-3660-5_28.

Articles connexes

Hors origine japonaise
Créateurs et éditeurs de jeux

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.