Combien de carrés y a-t-il dans une grille « Sudoku » standard ?
81
Une version sur table du Sudoku peut être jouée avec un jeu de cartes standard de 81 cartes (voir Jeu de cartes). Un puzzle Sudoku tridimensionnel a été publié dans le Daily Telegraph en mai 2005. Le Times publie également une version tridimensionnelle sous le nom de Tredoku. De plus, une version Sudoku du Rubik's Cube est nommée Sudoku Cube.
(,,, initialement appelé Number Place), est un puzzle combinatoire de placement de nombres basé sur la logique. L'objectif est de remplir une grille 9×9 avec des chiffres afin que chaque colonne, chaque ligne et chacune des neuf sous-grilles 3×3 qui composent la grille (également appelées « cases », « blocs », « régions » ou « sous-carrés") contient tous les chiffres de 1 à 9. Le créateur de puzzle fournit une grille partiellement complétée qui, pour un puzzle bien posé, a une solution unique.
Les puzzles terminés sont toujours une sorte de carré latin avec une contrainte supplémentaire sur le contenu des régions individuelles. Par exemple, le même entier ne peut pas apparaître deux fois dans la même ligne, colonne ou dans l’une des neuf sous-régions 3×3 du plateau de jeu 9x9.
Les journaux français ont présenté des variantes de ces puzzles au XIXe siècle, et le puzzle est apparu depuis 1979 dans des livres de puzzles sous le nom de Number Place. Cependant, le Sudoku moderne n'a commencé à se généraliser qu'en 1986 grâce à la société japonaise de puzzles Nikoli, sous le nom de Sudoku, qui signifie « numéro unique ». Il est apparu pour la première fois dans un journal américain, puis dans le Times (Royaume-Uni) en 2004, grâce aux efforts de Wayne Gould, qui a conçu un programme informatique permettant de produire rapidement des puzzles distincts.
Histoire
Les énigmes numériques sont apparues dans les journaux à la fin du XIXe siècle, lorsque les créateurs de puzzles français ont commencé à expérimenter la suppression des nombres des carrés magiques. Le Siècle, un quotidien parisien, a publié le 19 novembre 1892 un carré magique 9×9 partiellement complété avec des sous-carrés 3×3. Ce n'était pas un Sudoku car il contenait des nombres à deux chiffres et nécessitait de l'arithmétique plutôt que de la logique pour le résoudre, mais il caractéristiques clés partagées : chaque ligne, colonne et sous-carré totalisent le même nombre.
Le 6 juillet 1895, La France, rivale du Siècles, affine le puzzle pour en faire presque un Sudoku moderne. Il a simplifié le puzzle du carré magique 9 × 9 de sorte que chaque ligne, colonne et diagonale brisée ne contenait que les nombres 1 à 9, mais ne marquait pas les sous-carrés. Bien qu’ils ne soient pas marqués, chaque sous-carré 3×3 comprend bien les nombres 1 à 9 et la contrainte supplémentaire sur les diagonales brisées ne conduit qu’à une seule solution.
Ces énigmes hebdomadaires ont été publiées dans les journaux français tels que L'Echo de Paris pendant environ une décennie, mais ont disparu à l'époque de la Première Guerre mondiale.
Le Sudoku moderne a très probablement été conçu de manière anonyme par Howard Garns, un architecte à la retraite de 74 ans et constructeur de puzzles indépendant de Connersville, Indiana, et publié pour la première fois en 1979 par Dell Magazines sous le titre Number Place (les premiers exemples connus de Sudoku moderne). Le nom de Garns était toujours présent sur la liste des contributeurs dans les numéros de Dell Pencil Puzzles et Word Games qui incluaient Number Place, et était toujours absent dans les numéros qui n'y figuraient pas. Il est décédé en 1989 avant d'avoir eu la chance de voir sa création comme un phénomène mondial. Il n’est pas clair si Garns connaissait l’un des journaux français répertoriés ci-dessus.
Le puzzle a été introduit au Japon par Nikoli dans le journal Monthly Nikolist en avril 1984 sous le nom de « les chiffres doivent être uniques » ou « les chiffres sont limités à une seule occurrence ». (En japonais, dokushin signifie « personne célibataire ».) Plus tard, le nom a été abrégé en Sudoku (数独) par , en prenant uniquement le premier kanji des mots composés pour former une version plus courte. "Sudoku" est une marque déposée au Japon et le puzzle est généralement appelé ou, de manière plus informelle, un portemanteau des deux mots . En 1986, Nikoli a introduit deux innovations : le nombre de données était limité à 32 au maximum et les puzzles sont devenus « symétriques » (ce qui signifie que les données étaient distribuées dans des cellules à rotation symétrique). Il est désormais publié dans des périodiques japonais grand public, tels que l'Asahi Shimbun.
Le Times de Londres a commencé à présenter le Sudoku fin 2004 après une apparition réussie dans un journal local américain, grâce aux efforts de Wayne Gould, et s'est rapidement répandu dans d'autres journaux en tant qu'article régulier. Gould a conçu un programme informatique pour produire rapidement des puzzles uniques.
Variantes
Variations de tailles de grille
Bien que la grille 9×9 avec des régions 3×3 soit de loin la plus courante, de nombreuses autres variantes existent. Les exemples de puzzles peuvent être des grilles 4×4 avec des régions 2×2 ; Des grilles 5×5 avec des régions pentomino ont été publiées sous le nom Logi-5 ; le Championnat du monde de puzzle comprenait une grille 6 × 6 avec des régions 2 × 3 et une grille 7 × 7 avec six régions heptomino et une région disjointe. Des grilles plus grandes sont également possibles. Le Times propose une grille "Dodeka Sudoku" de 12 × 12 avec 12 régions de carrés 4 × 3. Dell Magazines publie régulièrement des puzzles 16 × 16 "Number Place Challenger" (utilisant les chiffres 1 à 16 ou les lettres A-P). Nikoli propose des mastodontes « Sudoku le Géant » 25×25. Un puzzle de 100 × 100 grilles baptisé Sudoku-zilla a été publié en 2010.
Imposer des contraintes supplémentaires
Une autre variante courante consiste à ajouter des limites sur le placement des nombres au-delà des exigences habituelles en matière de lignes, de colonnes et de cases. Souvent, la limite prend la forme d’une « dimension » supplémentaire ; la plus courante consiste à exiger que les nombres dans les diagonales principales de la grille soient également uniques. Les puzzles "Number Place Challenger" susmentionnés sont tous de cette variante, tout comme les puzzles Sudoku X du Daily Mail, qui utilisent des grilles 6 × 6.
Mini-Sudoku
Une variante nommée "Mini Sudoku" apparaît dans le journal américain USA Today et ailleurs, qui se joue sur une grille 6×6 avec 3×2 régions. L'objet est le même que celui du Sudoku standard, mais le puzzle utilise uniquement les chiffres de 1 à 6. Une forme similaire, destinée aux jeunes résolveurs de puzzles, appelée "Le Sudoku Junior", est apparue dans certains journaux, comme certaines éditions de Le courrier quotidien.
Sudoku tueur
La variante Killer Sudoku combine des éléments du Sudoku et du Kakuro.
Sudoku alphabétique
Des variantes alphabétiques sont apparues, parfois appelées Wordoku ; aucune différence fonctionnelle n'existe dans le puzzle à moins que les lettres n'épelent quelque chose. Certaines variantes, comme dans le Guide TV, incluent un mot lu le long d'une diagonale principale, d'une ligne ou d'une colonne une fois résolu ; déterminer le mot à l’avance peut être considéré comme une aide à la résolution. Un Wordoku peut contenir des mots autres que le mot principal.
"Quadratum latinum" est une variante de Sudoku avec chiffres romains (I, II, III, IV, ..., IX) proposée par Hebdomada aenigmatum, un magazine mensuel de puzzles latins et de mots croisés. Comme le Wordoku, il ne présente aucune différence fonctionnelle par rapport à un Sudoku normal, mais ajoute la difficulté visuelle liée à l'utilisation des chiffres romains.
Hypersudoku
L’Hypersudoku est l’une des variantes les plus populaires. Il est publié par des journaux et des magazines du monde entier et est également connu sous les noms de « NRC Sudoku », « Windoku », « Hyper-Sudoku » et « 4 Square Sudoku ». La disposition est identique à un Sudoku normal, mais avec des carrés intérieurs supplémentaires définis dans lesquels doivent apparaître les chiffres de 1 à 9. L'algorithme de résolution est légèrement différent des puzzles Sudoku normaux en raison de l'accent mis sur les carrés qui se chevauchent. Ce chevauchement donne au joueur plus d'informations pour réduire logiquement les possibilités dans les cases restantes. L'approche du jeu est similaire à celle du Sudoku, mais en mettant peut-être davantage l'accent sur l'analyse des carrés et des chevauchements plutôt que sur les colonnes et les lignes.
Autres variantes
Les puzzles construits à partir de plusieurs grilles de Sudoku sont courants. Cinq grilles 9×9 qui se chevauchent au niveau des coins en forme de quinconce sont connues au Japon sous le nom de Sudoku Gattai 5 (cinq fusionnés). Dans The Times, The Age et The Sydney Morning Herald, cette forme de puzzle est connue sous le nom de Samurai SuDoku. Le Baltimore Sun et le Toronto Star publient un puzzle de cette variante (intitulé High Five) dans leur édition du dimanche. Souvent, aucune donnée n'est placée dans les régions qui se chevauchent. Des grilles séquentielles, par opposition aux chevauchements, sont également publiées, les valeurs situées à des emplacements spécifiques des grilles devant être transférées à d'autres.
Une version sur table du Sudoku peut être jouée avec un jeu de cartes standard de 81 cartes (voir Jeu de cartes). Un puzzle Sudoku tridimensionnel a été publié dans le Daily Telegraph en mai 2005. Le Times publie également une version tridimensionnelle sous le nom de Tredoku. De plus, une version Sudoku du Rubik's Cube est nommée Sudoku Cube.
De nombreuses autres variantes ont été développées. Certains ont des formes différentes dans la disposition des grilles 9×9 qui se chevauchent, comme un papillon, un moulin à vent ou une fleur. D'autres varient la logique de résolution de la grille. L'un d'eux est "Plus grand que le Sudoku". En cela, une grille 3×3 du Sudoku est donnée avec 12 symboles Supérieur à (>) ou Inférieur à (Une autre variante de la logique de solution est le "Clueless Sudoku", dans lequel neuf grilles Sudoku 9×9 sont chacune placées. dans un tableau 3 × 3. La cellule centrale de chaque grille 3 × 3 des neuf puzzles est laissée vide et forme un dixième puzzle Sudoku sans qu'aucune cellule ne soit complétée ;
Mathématiques du Sudoku
Les résultats dans le texte suivant font référence au Sudoku classique, sans tenir compte des puzzles, des hyper et autres.
Une grille de Sudoku complétée est un type spécial de carré latin avec la propriété supplémentaire de ne pas répéter de valeurs dans aucun des neuf blocs de cellules 3×3 contiguës. La relation entre les deux théories est désormais parfaitement connue, après qu'il a été prouvé qu'une formule du premier ordre ne mentionnant pas de blocs (appelés aussi cases ou régions) est valable pour le Sudoku si et seulement si elle est valable pour les carrés latins (cette propriété est trivialement vrai pour les axiomes et peut être étendu à n'importe quelle formule).
Le nombre de grilles de solutions classiques de Sudoku 9×9 est de 6 670 903 752 021 072 936 960, soit environ . C'est à peu près le nombre de carrés latins 9 × 9. Calcul détaillé de ce chiffre. Diverses autres tailles de grille ont également été énumérées. Voir l'article principal pour plus de détails. Le nombre de solutions essentiellement différentes, lorsque des symétries telles que la rotation, la réflexion, la permutation et le réétiquetage sont prises en compte, s'est avéré être de seulement 5 472 730 538.
Contrairement au nombre de grilles de Sudoku complètes, le nombre de grilles minimales de Sudoku 9×9 n'est pas connu avec précision. (Un puzzle minimal est un puzzle dans lequel aucun indice ne peut être supprimé sans perdre l'unicité de la solution.) Cependant, des techniques statistiques combinées à la définition d'un nouveau type de générateur permettent de montrer qu'environ (avec une erreur relative de 0,065 %) 3,10 × 1037 minimal Il existe des puzzles et des puzzles minimaux de 2,55 × 1 025 non essentiellement équivalents.
Le nombre maximum de données fournies sans fournir de solution unique est de quatre de moins qu'une grille complète (77) ; si deux instances de deux nombres chacune manquent dans les cellules qui occupent les coins d'un rectangle orthogonal et que exactement deux de ces cellules se trouvent dans une région, les nombres peuvent être attribués de deux manières. Puisque cela s'applique aux carrés latins en général, la plupart des variantes du Sudoku ont le même maximum. Le problème inverse – le moins de données qui rendent une solution unique – s'est avéré être 17 en janvier 2012 (confirmé en septembre 2013). Un certain nombre de puzzles valides avec 17 données ont été trouvés pour la variation standard sans contrainte de symétrie, par des passionnés de puzzles japonais, et 18 avec les données dans des cellules à rotation symétrique. Plus de 49 000 exemples de grilles de Sudoku avec 17 données donnant lieu à une solution unique sont connus.
La disposition des nombres dans les puzzles Sudoku a une entropie de Shannon plus grande que la disposition des nombres dans les matrices 9×9 générées aléatoirement, car les règles du Sudoku excluent certains arrangements aléatoires qui ont une symétrie innée.
Le problème général de la résolution de puzzles Sudoku sur des tableaux n2 × n2 de n × n blocs est connu pour être NP-complet.
Une approche populaire pour résoudre rapidement n'importe quel puzzle de Sudoku consiste à programmer une application de liens dansants, avec des résultats typiques en millisecondes pour un Sudoku 9x9. Bien que cela n’indique pas à quel point le puzzle serait difficile pour les humains, on sait au moins si la solution est unique, impossible ou combien de solutions possibles existent.
Popularité depuis 1997 en dehors du Japon
En 1997, Wayne Gould a vu un puzzle en partie terminé dans une librairie japonaise. Pendant six ans, il a développé un programme informatique permettant de produire rapidement des puzzles. Sachant que les journaux britanniques publient depuis longtemps des mots croisés et d'autres puzzles, il a promu le Sudoku auprès du Times en Grande-Bretagne, qui l'a lancé le 12 novembre 2004 (sous le nom de Su Doku). La première lettre au Times concernant Su Doku a été publiée le lendemain, le 13 novembre, par Ian Payn de Brentford, se plaignant que l'énigme lui avait fait rater son arrêt de métro.
L'essor rapide du Sudoku en Grande-Bretagne, passant d'une relative obscurité à une première page des journaux nationaux, a suscité des commentaires dans les médias et des parodies (comme lorsque la section The Guardians G2 s'est présentée comme le premier supplément de journal avec une grille de Sudoku sur chaque page). Reconnaissant les différents attraits psychologiques des énigmes faciles et difficiles, le Times a présenté les deux côte à côte le 20 juin 2005. À partir de juillet 2005, Channel 4 a inclus un jeu de Sudoku quotidien dans son service télétexte. Le 2 août, le guide des programmes de la BBC, Radio Times, présentait un Super Sudoku hebdomadaire avec une grille 16×16.
Aux États-Unis, le premier journal à publier un puzzle Sudoku de Wayne Gould fut The Conway Daily Sun (New Hampshire), en 2004.
La première émission télévisée de Sudoku en direct au monde, Sudoku Live, était un concours de puzzle diffusé pour la première fois le 1er juillet 2005 sur Sky One. Il a été présenté par Carol Vorderman. Neuf équipes de neuf joueurs (avec une célébrité dans chaque équipe) représentant des régions géographiques se sont affrontées pour résoudre une énigme. Chaque joueur disposait d'un appareil portatif pour saisir les nombres correspondant aux réponses de quatre cellules. Phil Kollin de Winchelsea, en Angleterre, a remporté le grand prix de la série, remportant plus de 23 000 £ sur une série de jeux. Le public à la maison participait à un concours interactif distinct, remporté par Hannah Withey de Cheshire.
Plus tard en 2005, la BBC a lancé SUDO-Q, un jeu télévisé combinant Sudoku et culture générale. Cependant, il n’utilise que des puzzles 4×4 et 6×6. Quatre saisons ont été produites, avant la fin de la série en 2007.
En 2006, un site Web de Sudoku a publié la chanson hommage au Sudoku de l'auteur-compositeur Peter Levy, mais a rapidement dû supprimer le fichier MP3 en raison d'un trafic important. Les radios britanniques et australiennes ont repris la chanson, qui doit figurer dans un documentaire britannique sur le Sudoku. L'ambassade du Japon a également nominé la chanson pour un prix, Levy étant en pourparlers avec Sony au Japon pour sortir la chanson en single.
Le logiciel Sudoku est très populaire sur les PC, les sites Web et les téléphones mobiles. Il est livré avec de nombreuses distributions Linux. Des logiciels ont également été publiés sur les consoles de jeux vidéo, telles que la Nintendo DS, la PlayStation Portable, la Game Boy Advance, la Xbox Live Arcade, la liseuse de livres électroniques Nook, la tablette Kindle Fire, plusieurs modèles d'iPod et l'iPhone. De nombreux téléphones Nokia disposaient également de Sudoku. En fait, à peine deux semaines après qu'Apple Inc. a lancé l'App Store en ligne sur son iTunes Store le 11 juillet 2008, près de 30 jeux de Sudoku différents s'y trouvaient déjà, créés par divers développeurs de logiciels, spécifiquement pour l'iPhone et l'iPod Touch. L'un des jeux vidéo les plus populaires mettant en vedette le Sudoku est Brain Age : Entraînez votre cerveau en quelques minutes par jour !. Bien accueilli par la critique et le commerce, il a suscité des éloges particuliers pour sa mise en œuvre du Sudoku et s'est vendu à plus de 8 millions d'exemplaires dans le monde. En raison de sa popularité, Nintendo a créé un deuxième jeu Brain Age intitulé Brain Age2, qui propose plus de 100 nouveaux puzzles Sudoku et d'autres activités.
En juin 2008, un procès devant jury australien lié à la drogue, coûtant plus d'un million de dollars australiens, a été avorté lorsqu'il a été découvert que cinq des 12 jurés jouaient au Sudoku au lieu d'écouter les preuves.
Compétitions
*Le premier Championnat du Monde de Sudoku a eu lieu à Lucca, en Italie, du 10 au 12 mars 2006. La gagnante était Jana Tylová de la République tchèque. Le concours comprenait de nombreuses variantes.
*Le deuxième Championnat du Monde de Sudoku s'est tenu à Prague du 28 mars au 1er avril 2007. Le champion individuel était l'Américain Thomas Snyder. Le champion par équipe était le Japon.
*Le troisième Championnat du Monde de Sudoku s'est tenu à Goa, en Inde, du 14 au 16 avril 2008. Thomas Snyder a répété son titre de champion individuel au classement général et a également remporté le tout premier Trophée Classique (un sous-ensemble de la compétition ne comptant que le Sudoku classique). La République tchèque a remporté la compétition par équipe.
*Le quatrième Championnat du Monde de Sudoku s'est tenu à Žilina, en Slovaquie, du 24 au 27 avril 2009. Après que l'ancien champion des États-Unis Thomas Snyder ait remporté la qualification générale, le Polonais Jan Mrozowski est sorti des séries éliminatoires à 36 concurrents pour devenir le nouveau Championnat du Monde. Champion du Sudoku. La Slovaquie, pays hôte, s'est imposée comme la meilleure équipe dans une compétition distincte réunissant des équipes de trois.
*Le cinquième Championnat du Monde de Sudoku s'est tenu à Philadelphie du 29 avril au 2 mai 2010. Le Polonais Jan Mrozowski a défendu avec succès son titre mondial dans la compétition individuelle, tandis que l'Allemagne a remporté une épreuve par équipe distincte. Les énigmes ont été écrites par Thomas Snyder et Wei-Hwa Huang, tous deux anciens champions américains de Sudoku.
* Aux États-Unis, le championnat national de Sudoku Philadelphia Inquirer a eu lieu trois fois, offrant à chaque fois un prix de 10 000 $ au vainqueur de la division avancée et une place dans l'équipe nationale américaine de Sudoku voyageant pour les championnats du monde. Les gagnants de l'événement étaient Thomas Snyder (2007), Wei-Hwa Huang (2008) et Tammy McLeod (2009). Lors de l'événement le plus récent, le finaliste de la troisième place dans la division avancée, Eugene Varshavsky, s'est montré assez médiocre sur scène après avoir établi un temps de qualification très rapide sur papier, ce qui a attiré l'attention des organisateurs et des concurrents, dont l'ancien champion Thomas Snyder, qui a demandé aux organisateurs reconsidérer ses résultats en raison de soupçons de tricherie. Après une enquête et un nouveau test de Varshavsky, les organisateurs l'ont disqualifié et ont attribué à Chris Narrikkattu la troisième place.