Grille sudoku Sudoku Sudoku gratuit sudoku gratuit jeu gratuit
jouer jeu
Sudoku Devenez membre du meilleur site de sudoku Jouer au Sudoku Tournois de sudoku Forum Sudoku
menu jeu

Jouer au sudoku
  Sudoku Sudoku enfant :
Sudoku Sudoku enfant facile
Sudoku Sudoku enfant difficile



Sudoku Sudoku en solo :
Sudoku Sudoku facile
Sudoku Sudoku moyen
Sudoku Sudoku difficile
Sudoku Sudoku diabolique
Sudoku Sudoku Samourai
Sudoku Sudoku 3D/Flash

Sudoku Imprimer des grilles
Sudoku Télécharger des grilles
Sudoku Recommander à un ami
 
jouer gratuit kakuro sodoku

Tournoi de sudoku
 

Présentation des tournois

Sudoku Tournoi 1 contre 1 - new !
Sudoku Tournoi de sudoku
Sudoku Jouer au rapidoku
Sudoku Rapidoku sur 3 grilles
Sudoku Duel contre un(e) ami(e)

 
imprimer telecharger gagner

Classement des tournois de sudoku
 

Classements tout compris

Sudoku Classement du mois
Sudoku Classement hebdo'
Sudoku Classement du jour
Stats Mes Statistiques
Sudoku Liste des membres

Classements des tournois

Sudoku Tout tournois
Sudoku Tournois fixe
Sudoku Rapidoku
Sudoku Rapidoku sur 3

Classement des solos

Sudoku Classement solos

 
jouer gratuit jouer en ligne gratuitement

Acheter du sudoku
  Sudoku Sudoku électronique
Sudoku Jeux de sudoku PC
Sudoku Sudoku sur consoles
Sudoku Livres de sudoku

Sudoku Télécharger 6 400 grilles
Sudoku Sudoku sur ton mobile

Sudoku Meilleurs prix du sudoku
 
imprimer des grilles de kakuro sudoku samourai imprimer des grilles samourai
Le sudoku
 

Le sudoku (prononcé /sudoku/ en français, /sɯːdokɯ/ en japonais), du japonais 数, sû, chiffre, et de 独, doku, unique, est un jeu en forme de grille défini en 1979 et inspiré du carré latin ainsi que du problème des 36 officiers de Leonhard Euler. Le but du jeu est de remplir cette grille avec des chiffres allant de 1 à 9 en respectant certaines contraintes, quelques chiffres étant déjà disposés dans la grille.

Voici le sommaire :
1 - Présentation du Sudoku
2 - Son Historique
2.1 - Le fameu problème des officiers
2.2 - La version moderne du sudoku
2.3 - Popularité dans les médias
3 - Les variantes
4 - Nombre de grilles complètes possibles
5 - Mathématiques
6 - Les r ègles et terminologie
7 - Les m éthode de résolution
7.1 - La recherche
7.2 - La candidature
7.3 - L'analyse
8 - Les solutions logicielles
9 - Degrés de difficulté
10 - Construction

Présentation

La grille de jeu du Sudoku est un carré de neuf cases de chaque côté, subdivisé en autant de carrés identiques, appelés régions. La règle du jeu est la suivante : 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 jeu réside plutôt dans la difficulté à trouver la suite exacte de chiffres à ajouter.

Ce jeu a déjà inspiré de nombreuses 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, et, ils semblent être écoutés. 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.

Historique

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 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 6 officiers de grades différents. On se demande ensuite 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 un exemple à sa conjecture. Il dira :

« Or, après toutes les peines qu’on s’est données pour résoudre ce problème, on a été obligé de reconnaître qu’un tel arrangement est absolument impossible, quoiqu’on ne puisse pas en donner de démonstration rigoureuse. »
En 1901, le Français Gaston Tarry démontre l'impossibilité du résultat grâce à une recherche exhaustive des cas et par croisement des résultats.

Le lien entre le sudoku et le problème des 36 officiers est la contrainte qui empêche la répétition du même élément dans la grille, tout en arrivant au final à un jeu qui emploie le principe du carré latin (combinaison de deux carrés latins dans le cas du carré gréco-latin, carré latin subdivisé en plusieurs régions dans le cas du sudoku).

La version moderne du sudoku

Le sudoku a des ancêtres en France 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 à remplir des grilles 9x9 divisées en 9 régions, très proches de ce jeu (mais les grilles initiales comprenaient des contraintes supplémentaires sur la solution), qui étaient publiées dans les grands quotidiens de l'époque, révèle Pour la Science dans son édition de juin 2006.

Selon le magazine, la grille la plus proche d'un sudoku, qui a été retrouvée par le Français Christian Boyer, est celle de B. Meyniel, diffusé dans le quotidien La France du 6 juillet 1895, et une variante proche a été publiée juste avant, en novembre 1892, dans Le Siècle, variante qui utilisait des nombres à deux chiffres.

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 "Number Place". Nikoli l'introduit au Japon en avril 1984 dans le magazine Monthly Nikolist. La règle du jeu en japonais se résume en une seule phrase : Sūji wa dokushin ni kagiru (数字は独身に限る), ce qui signifie exactement il ne peut y avoir qu'un seul et unique chiffre (par case). D'oû le nom de Sudoku (数独), qui associe les caractères Sû 数 chiffre et Doku 独 tout seul, unique. En 1986, Nikoli introduit deux nouveautés, qui rendront le jeu plus populaire qu'auparavant : le nombre de dévoilés est au plus de 30 et les grilles sont symétriques, c'est-à-dire que les dévoilés sont symétriquement distribués autour du centre de la grille. Maintenant, 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 programme pour ordinateur personnel à générer des Sudoku. Il existe une société 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 Mac, en japonais et en anglais et, en 1996, il récidive pour le Palm.

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 plusieurs anthologies de jeux, 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 à plus de 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, PDG 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é d'autres pays tel que la Suisse, Wayne Gould fournit des grilles au quotidien Francais Le Matin qui a vendu cette année 150 000 livres de sudoku. Le Temps, autre quotidien helvétique publie quant à lui des grilles de sudoku depuis septembre.

Popularité dans les médias

Dès 1997, Wayne Gould, un Néo-Zélandais et juge à la retraite de Hong Kong, est intrigué par une grille partiellement remplie dans une librairie japonaise. Pendant six ans, il développe un programme qui génère automatiquement ces grilles. Sachant que les journaux britanniques publient des mots croisés et autres jeux semblables depuis longtemps, il promeut le sudoku auprès du journal The Times, lequel publie pour la première fois une grille le 12 novembre 2004.

trois jours plus tard, The Daily Mail publie aussi une grille sous le nom Codenumber. The Daily Telegraph diffuse sa première grille le 19 janvier 2005, suivi par les autres publications du Telegraph Group. Le 20 mai 2005, le Daily Telegraph de Sydney publie pour la 1ère fois une grille.

C'est lorsque le Daily Telegraph publie des grilles sur une base quotidienne, à partir du 23 février 2005, tout en promouvant celui-ci sur sa page une, que les autres journaux britanniques commencent à y prêter attention. Le Daily Telegraph a continué sa campagne de promotion lorsqu'il a réalisé que ses ventes augmentaient simplement par la présence d'une grille de sudoku. The Times était plutôt discret sur l'immense popularité qui entourait son concours de sudoku. Il avait déjà prévu de tirer avantage de son avance en publiant un premier livre sur le sudoku.

En avril/mai 2005, le jeu était suffisamment populaire pour que plusieurs journaux nationaux le publient sur une base régulière. Entre autre, on retrouve The Independent, The Guardian, The Sun (intitulé Sun Doku) et The Daily Mirror. Lorsque le mot Sudoku devient populaire au Royaume-Uni, le Daily Mail l'adopte à la place de Codenumber. Dès lors, les journaux ont rivalisé d'imagination pour pousser leurs grilles. The Times et Daily Mail affirment qu'ils sont les premiers à avoir publié une grille de sudoku, alors que The Guardian affirme, ironiquement, que ses grilles construites à la main, obtenues de Nikoli, apportent une meilleure expérience que les grilles générées à l'aide d'un logiciel.

La subite popularité du sudoku au Royaume-Uni a attiré un grand nombre de commentaires dans les médias 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. Le sudoku est devenu particulièrement visible tout de suite après les élections de 2005 au Royaume-Uni, incitant quelques commentateurs à affirmer qu'il remplissait un besoin chez le lectorat politique. Une autre explication suggère qu'il attire et retient l'attention des lecteurs, plusieurs se sentant de plus en plus satisfaits lorsque la solution se dessine. The Times estime que les lecteurs apprécient à la fois les grilles faciles et difficiles. En conséquence, il les publie côte à côte depuis le 20 juin 2005.

La 1ère émission à la télévision qui met en jeu le Sudoku, 1er juillet 2005, sur Sky One, La célèbre 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'une énorme grille de 84 m de côté. Cependant, il avait 1 905 solutions.

Cette brusque augmentation de popularité dans les médias 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 28 novembre 2005, la Télévision suisse romande lance une émission télévisée quotidienne, Su/do/ku, où deux candidats s'affrontent sur 5 jours, à raison de 3 manches de 8 minutes chaque jour. Toutefois, la difficulté pour faire passer ce genre de jeu à la télévision entraînera l'arrêt de l'émission après quelques semaines.

Des championnats nationaux sont également organisés comme le 1er championnat de France de sudoku (Paris, 18 décembre 2005) remporté par Juliette Thery, 19 ans. Cette compétition organisée par Sport cérébral récompense le meilleur joueur de l'année. C'est l'agence de communication Décollage vertical qui a mis en place cet évènement unique en France.

Variantes

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

- 2×2 ou "Sudoku binaire", contenant des régions 1×1 (version pleine d'ironie) ;
- 4×4 contenant des régions 2×2 (généralement pour les enfants) ;
- 5×5 contenant des régions en forme de pentamino ont été publiés sous le nom Logi-5;
- 6×6 contenant des régions 2×3 (proposée lors du World Puzzle Championship) ;
- 7×7 avec six régions en forme d'hexamino et une région disjointe (proposée lors du World Puzzle Championship) ;
- 9×9 avec des régions en forme de ennéamino ;
- 16×16 avec des régions 4×4 (appelées Number Place Challenger et publiées par Dell, ou appelées parfois Super Sudoku) ;
- 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 mai 2005. Le logiciel ksudoku appelle de telle grilles roxdoku et les génère automatiquement.

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. Le (en) Wordoku 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.

Le (en) Code Doku conçu par Steve Schaefer contient une phrase complète, alors que le (en) Super Wordoku de Top Notch contient 2 mots de neuf lettres, chacun se trouvant sur l'une des diagonales principales. Ces jeux ne sont pas considérés comme de vrais sudoku par les puristes, car la logique n'est pas suffisante pour les résoudre, même s'ils ont une solution unique. Top Notch affirme que ces jeux sont conçus de façon à bloquer les solutions composées par des logiciels de résolution automatique.

Au Japon, plusieurs variantes sont publiées. En voici une liste :

- Grilles connectées séquentiellement : plusieurs grilles 9×9 sont résolues consécutivement, mais seul la première a suffisamment de dévoilés pour permettre de résoudre logiquement. Une fois résolue, certains chiffres sont copiés vers le suivant. Cette formule impose au joueur de faire des allers et des retours entre des grilles partiellement résolues.
- Grilles très grandes qui consistent en de multiples grilles qui se chevauchent (habituellement 9×9). Des grilles constituées de 20 à 50, ou plus, sont courantes. La taille des régions qui se chevauchent varie (deux grilles 9×9 peuvent partager 9, 18 ou 36 cellules). Souvent, il n'y a aucun dévoilé dans ces régions.
- Grilles habituelles où un chiffre est membre de quatre groupes, au lieu des trois habituels (rangées, colonnes et régions) : les chiffres situés aux mêmes positions relatives dans une région ne doivent pas correspondre. Ces grilles sont habituellement imprimées en couleur, chaque groupe disjoint partageant une couleur pour faciliter la lecture.

La trousse de jeux pour participer au World Puzzle Championship de 2005 contient une variante intitulée Digital Number Place : plutôt que de contenir des dévoilés, la plupart des cellules contiennent un chiffre partiellement dessiné qui emprunte à la graphie de l'affichage à sept segments.

Le 31 août 2005, The Times a entamé la publication du Killer Su Doku, aussi nommé Samunamupure (qui signifie « lieu de sommation »), lequel indique la somme de cellules regroupées, ce qui ajoute un supplément de difficulté dans la recherche de la solution, bien que cela puisse aider à résoudre. Les autres règles s'appliquent.

La plupart des journaux proposent aujourd'hui une grille de Sudoku dans leur page de jeux.

Nombre de grilles complètes possibles

Il est évident que le nombre de grilles complètes est inférieur au nombre de façons de placer neuf chiffres 1, neuf chiffres 2..., neuf chiffres 9 dans une grille de 81 cases.

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 nombres de carrés latins de côté 9.

Enfin, le nombre de grilles complètes possibles est inférieur à 9!9 qui correspond au nombre de façons de construire les régions sans tenir compte des contraintes sur les lignes et les colonnes.

En 2005, Bertram Felgenhauer et Frazer Jarvis ont prouvé que ce nombre de grilles était de :

6 670 903 752 021 072 936 960≈6,67.1021.

Ce nombre est égal à :

9!×722×27×27 704 267 971

Le dernier facteur est un nombre 1er. Ce résultat a été prouvé grâce à une recherche approfondie. 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.

En revanche, à cette date, aucun résultat n'existe sur le nombre de grilles complètes dans un super sudoku (grille 16 × 16). Si maintenant, on s'intéresse aux nombres de problèmes proposables, ce nombre est nettement plus important car il existe plusieurs façons de révéler les chiffres d'une même grille.

Le problème de savoir combien de cases remplies sont nécessaires au préalable pour rendre la résolution unique est, à ce jour, sans réponse. Le meilleur résultat, obtenu par des Japonais, est de 17 cases sans contrainte de symétrie. [10] [11]. Rien ne dit que ce ne soit pas possible avec moins de nombres. Gordon Royle précise que deux résolutions sont considérées comme différentes si elles ne peuvent pas être transformées l'une vers l'autre (ou l'inverse) grâce à une combinaison des opérations suivantes :

1. permutations des 9 nombres
2. échange des lignes avec les colonnes (transposition)
3. permutation des lignes dans un seul bloc
4. permutation des colonnes dans un seul bloc
5. permutation des blocs sur une ligne de blocs
6. permutation des blocs sur une colonne de blocs

On remarque l'analogie avec les opérations matricielles en algèbre linéaire.

Mathématiques

Le problème de placer des chiffres sur une grille de n2×n2 comprenant n×n régions est prouvé NP-complet[2].

La résolution d'un sudoku peut être formalisée par le problème de la 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) ,

Une grille solution est aussi un carré latin. Il y a notablement moins de grilles solutions que de carrés latins, car le Sudoku impose des contraintes supplémentaires (Voir ci dessus point 4 : nombre de grilles complètes possibles).

Le nombre maximum de dévoilés sans qu'une solution unique n'apparaisse immédiatement, peu importe la variante, est la taille de la grille moins 4 : si deux paires de candidats ne sont pas inscrits et que les cellules vides occupent les coins d'un rectangle, et que exactement deux cellules sont dans une région, alors il existe deux façons d'inscrire les candidats. L'opposé de ce problème, à savoir le nombre minimum de dévoilés pour garantir une solution unique, est un problème non résolu, bien que des enthousiastes japonais aient découvert une grille 9×9 sans symétrie qui contient seulement 17 dévoilés, alors que 18 est le nombre minimum de dévoilés pour les grilles 9×9 symétriques.

Règles et terminologie

La plupart du temps, le jeu est proposé sous la forme d'une grille de 9×9, et composé de sous-grilles de 3×3, appelées « régions ». Quelques cellules contiennent des chiffres, dits « dévoilés ». Le but est de remplir les cellules vides, un chiffre dans chacune, de façon à ce que chaque rangée, chaque colonne et chaque région soient composées d'un seul chiffre allant de 1 à 9. En conséquence, chaque chiffre dans la solution apparaît une seule fois selon les trois « directions », d'où le nom « chiffre unique ». Lorsque qu'un chiffre peut s'inscrire dans une cellule, on dit qu'il est candidat

Méthode de résolution

La région en haut à droite doit contenir un 5. En éliminant les rangées et les colonnes en regard qui contiennent un 5, le joueur élimine toutes les cellules vides qui ne peuvent contenir ce 5. Il ne reste donc qu'une seule cellule d'accueil, en vert.La méthode de résolution se ramène à trois procédés : recherche, candidature et analyse

1. 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 joueur 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 joueur 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 grilles 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 grilles 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.

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

2. Candidature

La recherche cesse lorsque 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.
3. 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.

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 efficace, il trouvera une solution s'il dispose de suffisamment de temps. 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, un programme plus efficace s'appuiera sur les candidats potentiels pour chaque cellule, éliminant les candidats impossibles jusqu'à ce qu'un seul chiffre demeure. Connaissant ce chiffre, il peut trouver un autre chiffre pour une autre cellule, et ainsi de suite.

Une alternative au backtracking est de recourir aux méthodes préconisées par la programmation logique, telle qu'implantée par 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. Sachant que la plupart des grilles ont 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 [3]), et qui se révèle très efficace pour résoudre ce type de problème. Il est démontré que cet algorithme est tout indiqué pour la résolution d'un Sudoku, ne prenant que quelques millisecondes. Grâce à sa vitesse, il est maintenant préféré par la plupart des concepteurs logiciels.

Degrés de difficulté

Les grilles publiées mentionnent souvent un degré de difficulté. Celui-ci est calculé selon la facilité de résolution par une méthode logique. Étonnamment, le nombre de dévoilés n'a presque aucune incidence sur la difficulté d'une grille. Des grilles avec un petit nombre de chiffres peuvent être facilement résolues, alors que d'autres qui contiennent un nombre plus élevé de dévoilés que la moyenne peuvent être très difficiles à résoudre.

Connaissant la complexité des règles, les logiciels de résolution automatique peuvent estimer la difficulté pour un humain à trouver une solution. Cette estimation est en général suffisamment précise pour permettre aux éditeurs de la fournir. Quelques éditeurs en ligne fournissent également cette estimation.

Plusieurs facteurs influent sur la difficulté de ces problèmes. L'équation de base tient compte :

- du nombre de cellules à remplir ;
- du nombre de cellules remplies par élimination ;
- du nombre d'hypothèses à faire pour compléter la grille ;
- du nombre de recherches à faire pour compléter la grille.

Construction

Il semblerait que les grilles de Dell Magazines, le pionnier dans le domaine de la publication, soient générées par ordinateur. Elles sont habituellement composées de 30 chiffres dévoilés répartis au hasard. L'auteur des grilles est inconnu. Durant l'hiver 2000, Wei-Hwa Huang a affirmé qu'il était l'auteur du programme qui génère ces grilles; selon lui, les grilles antérieures étaient construites à la main. Le générateur serait écrit en C++ et, bien qu'il offre certaines options pour satisfaire le marché japonais (symétrie et moins de chiffres), Dell préfère ne pas les utiliser. Certains spéculent que Dell continue à utiliser ce programme, mais aucune preuve ne soutient leur affirmation.

Les sudoku de Nikoli, important créateur de sudoku au Japon, sont construits à la main, le nom de l'auteur apparaissant avec chaque grille publiée ; les dévoilés sont toujours présentés de façon symétrique. Cet exploit est possible en connaissant à l'avance l'endroit où seront les dévoilés et en affectant par la suite un chiffre aux cellules ainsi choisies. Le Number Place Challenger de Dell affiche aussi le nom de l'auteur. Les grilles publiées dans la plupart des journaux britanniques seraient générées automatiquement, mais font appel à la symétrie, ce qui laisserait sous-entendre qu'un humain les crée. The Guardian affirme que ses grilles sont créées à la main par des Japonais, mais aucune mention de l'auteur n'est faite. Elles seraient construites par des gens de Nikoli. The Guardian a affirmé que puisqu'ils sont construits à la main, ils contiennent de « subtiles allusions » hautement improbables dans les grilles construites par ordinateur.

Il est possible de construire des grilles avec de multiples solutions et sans solution, mais celles-ci ne sont pas considérées comme d'authentiques sudoku. Comme pour les autres jeux logiques, une solution unique est requise. Une grande attention est donc nécessaire lors de la construction d'une grille, puisqu'un seul chiffre mal placé risque de rendre la résolution de celle-ci impossible.

Par WIKIPEDIA

HAUT DE PAGE

 
Accès à votre compte membre pour jouer au sudoku
 

Il y a 26 connecté(s)

 
Devenez membre de grille sudoku
 

Pseudo :

 
Mot de passe :

 


Les outils du sudoku
   

Sudoku
 
 

Plus de sudoku
   

Sites sur le sudoku
 

Sudoku Actu Jeux Video
Sudoku Recherche Colocation Portail Colocation
Sudoku Plan, itinéraire
Sudoku Covoiturage, Covoiturage
SudokuPrix carburant
Sudoku Kit graphique, template
Sudokukit graphique
Sudoku Jeux gratuit
Sudoku Gagner des cadeaux
Sudoku Jeux
Sudoku Kakuro
Sudoku Wyx
Sudoku Jeux en ligne de réflexion
Sudoku World of Warcraft
SudokuJeux Gratuits
Sudoku Les autres partenaires

Votre site de sudoku ici ?

 
samourai imprimer
grille a imprimer
© 2006/2008. Grilles-Sudoku - Tous droits réservés - Plan du site -