Règles du Sudoku

Une grille de sudoku se compose de 81 cases regroupées en 9 blocs de 9 cases.

Le joueur doit compléter la grille avec des chiffres allant de 1 à 9.


Chaque chiffre ne peut être utilisé qu'une seule fois dans chaque ligne, dans chaque colonne et dans chaque bloc.

Jeudi 26 janvier 4 26 /01 /Jan 18:01
Par Sudoku - Publié dans : sudoku-sudoku
Ecrire un commentaire - Voir les 7 commentaires
Jeudi 26 janvier 4 26 /01 /Jan 18:00
Le sudoku fait actuellement l’objet d’un engouement incroyable si bien qu’il est impossible de réaliser quelques pas dans la rue, le métro, le tramway, les bus ou les cours de récréation, sans voir un jeu de sudoku.
 
Le succès du sodoku s’explique probablement par son accessibilité auprès du grand public contrairement aux mots croisés, dans la mesure où seule la réflexion est nécessaire afin de parvenir à solutionner un sudoku.
 
Néanmoins, nous pouvons nous poser la question de savoir si le sudoku est un phénomène de mode ou un phénomène de société ? Afin de répondre à cette question, il est indispensable d’attendre quelques mois mais personnellement je crois que le sudoku va s’installer profondément dans l’univers du jeu.
 
Par FS - Publié dans : sudoku-sudoku
Ecrire un commentaire - Voir les 0 commentaires
Jeudi 26 janvier 4 26 /01 /Jan 17:32
La grille de jeu est un carré de neuf cases de côté, subdivisé en autant de carrés identiques, appelés régions (voir figure). La règle du jeu est simple : chaque ligne, colonne et région ne doit contenir qu'une seule fois tous les chiffres de un à neuf. Formulé autrement, chacun de ces ensembles doit contenir tous les chiffres de un à neuf.
 
Les chiffres ne sont utilisés que par convention, les relations arithmétiques entre eux ne servant pas. N'importe quel ensemble de signes distincts : lettre, forme, couleur,... peut être utilisé sans changer les règles du jeu. Dell Magazine, le premier à publier des grilles, a utilisé des chiffres dans ses publications. Par contre, Scramblets, de Penny Press, et Sudoku Word, de Knight Features Syndicate, utilisent tous les deux des lettres.
 
L'intérêt du jeu réside dans la simplicité de ses règles, et dans la complexité de ses solutions. Les grilles publiées ont souvent un niveau de difficulté indicatif. L'éditeur peut aussi indiquer un temps de résolution probable. Quoique en général, les grilles contenant le plus de chiffres préremplis fussent les plus simples, l'inverse n'est pas systématiquement vrai. La véritable difficulté du puzzle réside plutôt dans la difficulté à trouver la suite exacte de chiffres à ajouter.
 
Ce jeu a déjà inspiré plusieurs versions électroniques qui apportent un intérêt différent à la résolution des grilles de Sudoku. Sa forme en grille et son utilisation ludique le rapprochent d'autres casse-tête publiés dans les journaux, tels les mots croisés et les problèmes d'échecs.
 
Des professeurs recommandent la pratique du Sudoku comme un entraînement aux raisonnements logiques. Le niveau de difficulté peut dans ce cas être adapté au public.
 
Des grilles sont publiées dans des journaux, mais peuvent aussi être générées par ordinateur.

 

Source : Wikipedia

Par FS - Publié dans : sudoku-sudoku
Ecrire un commentaire - Voir les 0 commentaires
Jeudi 26 janvier 4 26 /01 /Jan 17:32

La méthode de résolution se ramène à trois procédés : recherche, candidature et analyse.

Recherche

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

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

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

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

Candidature

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

  • Pour la notation indicée, les candidats sont inscrits dans une cellule, chaque chiffre occupant ou non une place précise. L'inconvénient de cette méthode est que les journaux publient des grilles de petite taille, ce qui rend difficile l'inscription de plusieurs chiffres dans une même cellule. Plusieurs joueurs reproduisent à plus grande échelle de telles grilles ou ont recours à un crayon à pointe fine.

  • Pour la notation pointée, les joueurs inscrivent des points dans les cellules vides. La position relative du point indique le chiffre manquant. Par exemple, pour indiquer 1, un point apparaît en haut à gauche dans la cellule. Cette notation permet de jouer directement avec une grille imprimée dans un journal. Cependant, elle demande une certaine dextérité, il est possible de mal placer un point dans un moment d'inattention et une petite marque faite par erreur peut mener à de la confusion. Certains joueurs préfèrent utiliser un stylo pour limiter les fautes.

Analyse

Les deux thèmes de ce procédé sont l'élimination et l'hypothèse.

 

 

 

  • Élimination : la recherche de la solution se fait en éliminant successivement les candidats d'une cellule de façon à ne retenir qu'un seul candidat. Une fois ce candidat trouvé, une autre recherche devrait être effectuée de façon à déterminer les conséquences sur les autres cellules. Il y a plusieurs techniques d'élimination qui s'appuient sur les règles ci-dessous, lesquelles ont d'utiles corollaires :

1 Un ensemble donné de n cellules dans une rangée, une colonne ou une région, ne peut recevoir que n chiffres différents. Cette règle est à la base de la technique d' « élimination du candidat orphelin », discutée ci-dessous.

2 Chaque candidat doit ultimement appartenir à un modèle auto-consistant et   indépendant. Cette règle est à la base des techniques d'analyse avancées, lesquelles demandent d'inspecter l'ensemble de toutes les possibilités pour un candidat. Il n'y a qu'un nombre fini de « circuits fermés » ou possibilités de grilles « n×n » qui existent. Cette règle a donné naissance aux méthodes X-wing et Swordfish, entre autres. Si un tel modèle est identifié, alors l'élimination de candidats est souvent possible.

  • L'une des techniques les plus utilisées est l' « élimination du candidat orphelin ». Les cellules avec un même ensemble de candidats sont dites couplées si le nombre de candidats dans chacune d'elle est égal au nombre de cellules qui peuvent les accueillir. Par exemple, deux cellules sont couplées si elles contiennent une paire unique de candidats (p,q) dans une rangée, une colonne ou une région; trois cellules sont dites couplées si elles contiennent un triplet unique de candidats (p,q,r). Ces chiffres ne peuvent apparaître ailleurs, car il y aurait conflit selon la rangée, la colonne ou la région. Pour cette raison, les candidats (p,q,r) qui se trouvent dans les autres cellules sont à éliminer. Ce principe vaut avec des sous-ensembles de candidats : si trois cellules ont seulement { (p,q,r), (p,q), (q,r) }, ou { (p,r), (q,r), (p,q) }, tous les candidats de cet ensemble qui se trouvent dans les autres cellules sont à éliminer.
  • Un deuxième principe découle du principe précédent. Si le nombre de cellules dans une rangée, une colonne ou une région, est égal à la taille d'un ensemble de candidats, les cellules et les chiffres sont couplés et seulement ces chiffres apparaîtront dans les cellules. Tous les autres candidats sont à éliminer. Par exemple, si (p,q) peut seulement apparaître dans deux cellules (d'une rangée, d'une colonne ou d'une région), les autres candidats sont à éliminer.
    Le premier principe s'appuie sur le concept de « chiffres couplés uniquement », alors que le second s'appuie sur le concept de « cellules couplées uniquement ». Les techniques avancées s'appuient sur ces concepts et englobent de multiples rangées, de multiples colonnes et de multiples régions.
  • Avec l'approche par hypothèse, une cellule avec seulement deux candidats est choisie et l'un des deux chiffres est inscrit dans la cellule. Les étapes précédentes sont répétées et mènent soit à une contradiction (chiffre dupliqué ou cellule sans candidat), soit à une proposition valide. Évidemment, dans le cas d'une contradiction, le deuxième chiffre fait partie de la solution. L'algorithme de Nishio est une forme épurée de cette approche : Pour chaque candidat d'une cellule, est-ce qu'insérer un chiffre en particulier prévient l'inscription de ce candidat ailleurs dans la grille ? Si la réponse est oui, alors le candidat est éliminé.
    L'approche par hypothèse demande d'utiliser un crayon et une gomme à effacer. Les puristes la rejettent, car elle est une approche par essais et erreurs, alors que la plupart des grilles publiées font appel à la logique seulement pour être résolues. Cependant, cette approche a le mérite de souvent mener à la solution plus rapidement.

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

Source : Wikipedia

Par FS - Publié dans : sudoku-sudoku
Ecrire un commentaire - Voir les 0 commentaires
Jeudi 26 janvier 4 26 /01 /Jan 17:31
Le problème des officiers
En 1782, le mathématicien suisse Leonhard Euler imagine un problème similaire au Sudoku tel que nous le connaissons. Certains attribuent la paternité du Sudoku au Suisse bien que les travaux d'Euler concernaient les carrés latins et la théorie des graphes.
 
On considère six régiments différents, chaque régiment possède six officiers de grades distincts. On se demande maintenant comment placer les 36 officiers dans une grille de 6x6, à raison d'un officier par case, de telle manière que chaque ligne et chaque colonne contienne tous les grades et tous les régiments.
 
Il s'agit en d'autres termes d'un carré gréco-latin d'ordre 6 (la combinaison de deux carrés latins, un carré latin pour les régiments, un carré latin pour les grades), problème dont la résolution est impossible. Euler l'avait déjà pressenti à l'époque, sans toutefois donner une démonstration formelle à sa conjecture. Il dira :
 
Or, après toutes les peines qu’on s’est données pour résoudre ce problème, on a été obligé de reconnaître qu’un tel arrangement est absolument impossible, quoiqu’on ne puisse pas en donner de démonstration rigoureuse.
En 1901, le français Gaston Tarry démontre l'impossibilité du résultat grâce à une recherche exhaustive des cas et par croisement des résultats.
La version moderne du sudoku
En 1979, un pigiste spécialisé dans les puzzles, Howard Garns, crée le premier puzzle. Dell Magazines l'introduit cette même année dans une publication destinée au marché newyorkais, le Dell Pencil Puzzles and Word Games, sous le nom de Number Place. Nikoli l'introduit au Japon en avril 1984 dans le magazine Monthly Nikolist et le nomme Sūji wa dokushin ni kagiru (数字は独身に限る, que l'on peut traduire par « le chiffre doit être unique » ou « survient une seule fois »; 独身 qui signifie littéralement « seul » ou « célibataire»). C'est le président de Nikoli qui le nomme ainsi. Plus tard, le nom change et devient Sudoku (数独), respectant ainsi la tradition de former un mot plus court en prenant le premier kanji de la paraphrase.
 
En 1986, Nikoli introduit deux nouveautés, qui rendront le puzzle populaire : le nombre de dévoilés est au plus de 30 et les puzzles sont symétriques, c'est-à-dire que les dévoilés sont symétriquement distribués autour du centre de la grille. Aujourd'hui, la plupart des journaux importants au Japon, tel Asahi Shimbun, publient ce jeu. Au Japon, Nikoli est toujours propriétaire du nom Sudoku ; ses concurrents utilisent un autre nom.
 
En 1989, Loadstar et Softdisk publient DigitHunt pour le Commodore 64, probablement le premier logiciel pour ordinateur personnel à générer des Sudoku. Il existe une entreprise qui continue à 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 (pour plus de détails, voir (en) [1]) et, en 1996, il récidive pour le Palm (pour plus de détails, voir (en) [2]).
 
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 puzzle. Des grilles apparaissent dans certaines anthologies de puzzles, telles que The Giant 1001 Puzzle Book (sous le nom de Nine Numbers).
 
C'est en juillet 2005 que le sudoku arrive en France, publié par Sport Cérébral, éditeur spécialisé dans les jeux de réflexion. 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. Le Figaro publie les premières grilles quotidiennes dès le début juillet, suivi au cours de l'été 2005 par Libération, La Provence, Nice Matin, 20 Minutes, Métro et Le Monde. Le magazine 1, 2, 3... Sudoku sortit son premier numéro en novembre 2005.
 
Le phénomène a également gagné la Suisse, Wayne Gould fournit des grilles au quotidien francophone Le Matin qui a vendu cette année 150 000 livres de sudoku et envisage par ailleurs de produire une émission télévisée sur ce thème. Le Temps, autre quotidien helvétique publie quant à lui des grilles de sudoku depuis septembre.
 
Il semble que les Japonais aient développé le jeu du Sudoku parce que leur alphabet comportait trop de signes pour pouvoir produire à grande échelle des mots croisés (voir [3]).
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 complétée dans une librairie japonaise. Pendant six ans, il développe un programme qui génère automatiquement ces grilles. Sachant que les journaux britanniques publient des mots croisés et autres jeux semblables depuis longtemps, il promeut le Sudoku auprès du journal The Times, lequel publie pour la première fois une grille le 12 novembre 2004.
 
Trois jours plus tard, The Daily Mail publie aussi une grille sous le nom Codenumber. The Daily Telegraph introduit son premier puzzle le 19 janvier 2005, suivi par les autres publications du Telegraph Group. Le 20 mai 2005, le Daily Telegraph de Sydney publie pour la première fois une grille.
 
C'est lorsque le Daily Telegraph publie des grilles sur une base quotidienne, à partir du 23 février 2005, tout en promouvant celui-ci sur sa page une, que les autres journaux britanniques portent 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à planifié de tirer avantage de son avance en publiant un premier livre sur le Sudoku.
 
En avril et mai 2005, le puzzle é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 est devenu populaire en Grande-Bretagne, le Daily Mail l'adopte en place de Codenumber. Dès lors, les journaux ont rivalisé d'imagination pour mousser 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 puzzles construits à la main, obtenus de Nikoli, offrent une meilleure expérience que les grilles générées à l'aide d'un logiciel.
 
La subite popularité de Sudoku en Grande-Bretagne a attiré son lot de commentaires dans les médias (voir Sources ci-dessous) et des parodies ont suivi (par exemple, la section G2 du journal The Guardian' s'annonce comme le premier supplément avec une grille par page : (en) [4]). Le Sudoku est devenu particulièrement visible tout de suite après les élections de 2005 en Grande-Bretagne, 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 un puzzle facile et difficile. En conséquence, il les publie côte à côte depuis le 20 juin 2005.
 
La télévision britannique s'est empressée de surfer sur la vague de popularité et Sky One diffuse la première émission sur le Sudoku, Sudoku Live, le 1er juillet 2005, que le mathématicien Carol Vorderman présente. Neuf équipes de neuf joueurs, dont une vedette, chacune représentant une région géographique, tentent de compléter une grille de Sudoku. Chaque joueur a en main un appareil qui lui permet de saisir un chiffre dans l'une des quatre cellules dont il est responsable. Échanger avec les autres membres de l'équipe est permis mais, la familiarité manquant, les compétiteurs ne le font pas. Également, l'auditoire à la maison participe à une autre compétition interactive en même temps. Sky One a tenté de créer un (en) engouement pour son émission par le biais d'un énorme puzzle 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 »). A titre d'exemple Wayne Gould fournit fin 2005 des grilles pour environ 70 quotidiens dans 27 pays.
 
Le 28 novembre 2005, la Télévision suisse romande lance une émission télévisée quotidienne, Su/do/ku, où deux candidats s'affrontent sur 5 jours, à raison de 3 manches de 8 minutes chaque jour.
 
Des championnats nationaux sont également organisés comme le 1er Championnat de France de Sudoku (Paris, 18 décembre 2005) remporté par Juliette Thery, 19 ans. Cette compétition organisée par Sport Cérébral récompense le meilleur joueur de l'année. C'est l'agence de communication Décollage vertical qui a mis en place cet évènement unique en France.
 
Source : Wikipedia
Par FS - Publié dans : sudoku-sudoku
Ecrire un commentaire - Voir les 1 commentaires
Créer un blog gratuit sur over-blog.com - Contact - C.G.U. - Rémunération en droits d'auteur - Signaler un abus