Utilisateur:Farid mita

Un article de Wikipédia, l'encyclopédie libre.

Mes contributions sur Wikipédia:

Sommaire 1 Sudoku 1.1 Méthode de résolution/Analyse 1.1.1 Grille-Conjointe; changer de situation pour résolution plus poussée 1.1.2 Stratégie des chemins; résoudre des cas plus complexes 1.1.3 Une technique «  à part » : principe de l’unicité de la solution 1.1.4 Stratégie de dernier recours : formulation claire et nette des hypothèses 1.2 Degrés de difficulté 1.3 Type 1 : 1.4 Type 2 : 1.5 Type 3 : 1.6 Type 4 : 1.7 Type 5 : 1.8 Construction: 2 Site-perso: 3 Discusion: 4 Remerciements

[modifier] Sudoku

[modifier] Méthode de résolution/Analyse

Résumé des paragraphes insérés: Introduction, pour la première fois, de la notion de "groupes indépendants de multiples numériquement liés" + inutilité de la formulation des hypothèses + introduction pour la première fois de la "grille-conjointe";

En principe, ces trois procédés ( candidat unique par croisement+candidat unique par comptage et élimination+groupes indépendants de multiples numériquement liés) suffisent pour réussir intégralement une grille. Mais il y a des situations où il semble qu’il n’est plus possible d’avancer. Voici un début d’exemple :

Vous avez trouvé à partir des chiffres déjà révélés selon les régions et les colonnes, les multiples 123-12-1456-479-23-56-2456-178-89 écrits sur toute une ligne pour une certaine grille. D’abord, on relève les 123, 12 et 23 numériquement liés ; trois multiples formés des trois chiffres 1,2 et 3, qui vont occuper chacun l’une des trois cases. Donc la ligne se simplifie en 123-12-456-479-23-56-456-78-89. Ensuite, on considère les multiples 456, 56 et 456 qui sont aussi numériquement liés, mais leur groupe est indépendant de celui des multiples formés à la base des chiffres 1, 2 et 3.Pour la même raison, la ligne se simplifie en 123-12-456-79-23-56-456-78-89. Il reste donc trois multiples 79, 78 et 89 qui sont numériquement liés, mais constituent un troisième groupe indépendant des deux premiers. À ce niveau, on dira que l’on a rempli la ligne de façon optimale. Les simplifications ainsi effectuées vont se répercuter sur les régions, les colonnes puis sur les autres lignes puis de nouveau sur les régions, les colonnes et les lignes si l’on arrive à dégager chaque fois, de nouveaux groupes indépendants. S’il reste toujours des cases sans candidat unique, alors, on pourra attaquer par traitement des multiples en considérant deux dimensions à la fois; colonnes+lignes (principe de l'unicité, X-Wing par exemple), colonnes+régions (doublons, jumeaux par exemple), lignes+régions (idem).Si la solution n'apparaît pas toujours, alors, désormais, vous êtes invité à utiliser les techniques de traitement à trois dimensions ( lignes X colonnes X régions ) dont par exemple, celles découlant de l'utilisation des chemins ( théorie basée sur la logique bivalente; il y est ou il n'y est pas).

Et si votre labeur n'aboutit pas toujours à la grille-solution, alors, c’est à cause de l’une des deux raisons suivantes :

• Vous vous êtes bien appliqué et vous avez rempli entièrement la grille de façon optimale par des chiffres uniques dans certaines cases et par des multiples dans les autres. Mais, tous les groupes des multiples que vous avez inscrits sont indépendants. Dans ce cas, Vous avez affaire à une grille présentant plusieurs solutions ! Ce n’est pas un « bon » Su-Doku et le problème ne devait pas être proposé, malheureusement !
• Toutes les cases de votre grille ont des candidats uniques ou multiples, mais, faute d’expérience, vous n’arrivez pas à discerner facilement des groupes indépendants de multiples numériquement liés. Dans ce cas, vous pouvez procéder par la disjonction de l’un des multiples. C’est-à-dire faire une hypothèse sur ses chiffres, et voir l’effet qui va se répercuter sur les autres multiples. Si vous avez vraiment un « bon » jeu de Su-Doku, alors un seul chiffre du multiple en question conduira à la solution du problème, tandis que pour tous les autres, on aboutira à des situations de blocage ! Dans le cas contraire, le problème ne mérite pas d’être posé ! Par principe !

Mais le fait de formuler une hypothèse sur le chiffre à choisir parmi ceux d'un multiple donné ne garantit pas toujours la simlification des autres multiples et risque d'aboutir sur de nouvelles hypothèses à faire, ce qui augmente rapidement le nombre de grilles à examiner successivement! Pire encore, les grilles obtenues peuvent être d'un niveau médiocre et donc sans intérêt intellectuel!

les paragtaphes suivants ont été supprimés par un wikipédiste qui a inséré dans l'article, un autre plus instructif. Je garde les miens pour mémoire!

Aussi, est-il préférable, pour éviter de formuler des hypothèses, d'être plus astucieux en considérant une nouvelle grille, dite la grille-conjointe qui consiste à repérer la bonne case pour un chiffre donné, dans une région donnée tout en continuant à travailler sur la grille normale en repérant pour le bon chiffre pour une case donnée.

Précisons que la grille-conjointe, introduite pour la première fois par F.MITA, est un deuxième tableau de 9 lignes (une ligne par chiffre) croisées avec 9 colonnes (une colonne par région) dont les cellules reçoivent les coordonnées de la case associée au chiffre et région donnés dans la grille normale du problème proposé. De par sa construction, la grille-conjointe englobe les techniques de résolution les plus efficaces dont X-wing, swordfish et bien d'autres inconnues par le commun des joueurs.

Un va-et-vient entre les deux grilles permettra aisément de réussir la grille-problème, même en cas de difficulté supérieur.

Cependant, la grille-conjointe comme tout d'ailleurs, la formulation des hypothèses sont inutiles si l'on est capable de raisonner en termes de "groupes indépendants de multiples numériquement liés", selon chaque région, chaque ligne et chaque colonne.

A la place, j'ai soumis ce qui suit:

[modifier] Grille-Conjointe; changer de situation pour résolution plus poussée

La stratégie des symétries généralisées entre lignes, colonnes et chiffres omet un quatrième angle d'attaque pour résoudre d'autres cas de figures plus complexes: considérer une région et un chiffre et repérer la bonne cellule. L'auteur du manuel "Stratégie de résolution d'une grille de Sudoku"^[1] propose l'utilisation de la Grille-Conjointe; c'est un tableau de 9 rangées horizontales(une rangée par chiffre) croisées avec 9 rangées verticales (une rangée par région) dont les cellules reçoivent les coordonnées de la case associée au chiffre et région donnés dans la grille normale du problème proposé. De par sa construction, la grille-conjointe englobe les techniques de résolution les plus efficaces dont X-wing, Swordfish et bien d'autres inconnues par le commun des joueurs. mais "ignore" la TPU ( technique découlant du principe de l'unicité de la solution), comme d'ailleurs la stratégie des Symétries généralisées. L'auteur suggère de classer la TPU dans une catégorie à part!

[modifier] Stratégie des chemins; résoudre des cas plus complexes

Si l'adoption du tableau étendu de résolution utilisant les symétries généralisées et/ou de la grille-conjointe permettent de résoudre les grilles fréquemment proposées dans les journaux, magazines et sites, il existe bien des cas de figure où ces deux stratégies butent sans pouvoir atteindre la solution finale. Avouons que ces deux stratégies ont le mérite de nous faire découvrir de nouveaux procédés de résolution mettant en jeu deux dimensions ( lignes X colonnes, lignes X régions et colonnes X régions)sur la grille-problème normale ou initiale, alors qu'il met en oeuvre qu'une seule dimension ( rangée horizontale ou verticale dans chacun des deux tableaux additionnels de la stratégie des symétries généralisées ou sur la grille-conjointe) dont le traitement est facile à mener ( élimination à cause des multiples nues ou dévoilement par dégraissage de multiples).

La stratégie adoptée pour ces cas de figures plus complexes consiste à prendre en considération les trois dimensions à la fois ( lignes X colonnes X régions). Il faut 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" et non(p): "N n'est pas la valeur").

Vu d'un certain angle, il s'agit de faire 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. C'est donc comme si l'on procède par formulation par hypothèse, mais d'une manière "caché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.

[modifier] Une technique «  à part » : principe de l’unicité de la solution

Il existe une classe de techniques, bien qu’en mettant en jeu deux dimensions seulement (lignes X colonnes, lignes X régions ou colonnes X régions) ne peuvent être retrouvées ni traduites d’une certaine manière dans le tableau étendu de résolution ou sur la grille-conjointe. On cite comme exemple, la technique découlant du principe de l’unicité de la solution. Le cas de figure est le suivant : dans quatre cases, sommets d’un rectangle, on trouve trois même paires ab, ab, ab et cette même paire mêlée avec d’autre chiffres x,…..,z sous forme abx….z. Alors, en vertu du principe de l’unicité de la solution, dans ce quatrième sommet, on peut chasser sans risque les deux chiffres a et b. Car au cas contraire, la grille aboutirait sur au moins deux solutions.

Dans certains cas, cette technique peut être utilisé sans le savoir, s’il est possible de suivre un chemin (ici une boucle) de l’un des sommets vers lui-même. Parfois, on est amené à utiliser cette même technique sur des polygones au lieu d’un rectangle ; une généralisation est donc possible, mais utilisant la stratégie des chemins.

[modifier] Stratégie de dernier recours : formulation claire et nette des hypothèses

Certains journaux, magazines, sites et logiciels nous livrent des grilles dites « diaboliques ». En général, il n’en est rien ! Ces grilles peuvent être résolues par les techniques mises au point jusqu’à ce jour. Une grande majorité peut être remplie « mentalement » même !

Bref, une définition s’impose : une grille diabolique est celle qui ne peut être résolue par aucun des procédés mis au point jusqu’à ce jour, sauf par la formulation d’une ou de plusieurs hypothèses sur les chiffres à mettre dans une ou plusieurs cases. Bien entendu, l’unicité de la solution pour la grille est requise.

Désormais, c’est le seul moyen pour aboutir sur la solution, en attendant l’élaboration de nouveaux procédés « manuels ».

[modifier] Degrés de difficulté

Objet de la contribution: Précision des critères de classification et reformulation:

Plusieurs facteurs influent sur la difficulté de ces problèmes . 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 X ligne, région X colonne ou colonne X ligne  ;
• du nombre de groupes indépendants de multiples numériquement liés, traitables suivant les trois dimensions à la fois; région X ligne X 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.

............

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 exemeple, 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é ( voir également la Typologie des grilles-problèmes élaborée par Farid MITA sur http://membres.lycos.fr/supergrille/sdk_types_grilles.html):

[modifier] 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 généré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".

[modifier] 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 pas à la résolution qu’une fois toutes les cellules contiennent leurs candidats probables. Dans ce cas, il faut essayer d’arriver à la situation optimale de la grille : dans chaque catégorie (ligne, colonne et région), les groupes des « multiples numériquement liés » doivent être « indépendants». D’autres techniques simples de traitement selon une seule dimension peuvent être utilisées, dont « l’élimination à cause des triplets nus » et « le dégraissage des triplets camouflés ». Cette dernière est plus pénible à faire ! On pourra également éliminer certains chiffres par une technique simple de traitement, cette fois-ci, à deux dimensions ligne X région ou colonne X région : «la répartition d'un blocs en quatre domaines complémentaires ou alternés». Donc, si vous optez pour un exercice mental, ce type de grilles vous propose de bien difficiles. Et si vous vous permettez d’inscrire les multiples dans les cellules, vous avez là de très beaux exercices d’entraînement sur la stratégie de traitement des « groupes indépendants de multiples numériquement liés ».

[modifier] 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 X colonnes, lignes X régions et/ou colonnes X 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.

[modifier] 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 X colonnes X 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.

[modifier] Type 5 :

Certains journaux, magazines, sites et logiciels nous livrent des grilles dites « diaboliques ». Le plus souvent, il n’en est rien de telles ! Ces grilles peuvent être résolues par les techniques mises au point jusqu’à ce jour. Une grande majorité peut être remplie « mentalement » même !

Bref, une définition s’impose : une grille diabolique est celle qui ne peut être résolue par aucun des procédés mis au point jusqu’à ce jour, sauf par la formulation d’une ou de plusieurs hypothèses sur les chiffres à mettre dans une ou plusieurs cases. Bien entendu, l’unicité de la solution pour la grille est requise.

Désormais, c’est le seul moyen pour aboutir à la solution, en attendant l’élaboration de nouveaux procédés « manuels ».

Signalons enfin, qu’au niveau de la construction des grilles-problèmes, il est fréquemment plus facile d’obtenir une grille de type1, et presque rare de tomber sur une grille de type 4 ou 5. Les logiciels élaborés jusqu’à ce jour partent bien sûr des différents procédés de résolution, pour fabriquer un problème, mais le niveau souhaité baisse, hélas, généralement d’un ou même de deux degrés ! Statistiquement, on relève que la distribution de la fréquence par type tourne autour de 46%, 32%, 11%, 8% et 3%, du premier type au cinquième.

[modifier] Construction:

Objet de la contribution: Notions de qualité d'une grille: Unicité de la solution + irréductibilité de la grille

Rappelons que le principe fondamental du Su-Doku réside dans le fait que seules sont permises comme problèmes à résoudre, les grilles qui aboutissent à une et une seule solution ! Cependant, certains sites et magazines spécialisés publient des grilles-problèmes proposant moins de données au départ et présentant même des symétries pouvant être plus attrayantes, parfois fantaisistes, mais admettant plus d’une solution. Mais, il n'y a pas que le problème de l'unicité de la solution, certains joueurs expérimentés ont remarqué que, pour certaines grilles, un ou plusieurs chiffres sont révélés de façon "gratuite", car ils peuvent être déduits logiquement en considérant le reste des chiffres de la grille. Ce qui veut dire qu'on pouvait proposer la grille avec moins de chiffres tout en garantissant l'aboutissement à la même et unique solution. C'est une question d'optimisation des grilles-problèmes: moins de chiffres dont aucun ne peut être déduit à partir des autres.

[modifier] Site-perso:

http://membres.lycos.fr/supergrille

Documents mathématiques, didactiques, pédagogiques, ludiques, élaborés et présentés sous format Excel, Word, PowerPoint, PDF, HTML, et autres...

En ce qui concerne le Su-Doku, des diaporamas pour illustrer des techniques, des générateurs sous excel de nouvelles belles grilles à résourdre, des grilles sous pdf, ... sont prêts à être enregistrés.

Email: farid.mita()gmail.com (remplacer () par @ )

[modifier] Discusion:

http://fr.wikipedia.org/wiki/Discussion_Utilisateur:Farid_mita

[modifier] Remerciements

Les plus sincères voeux à ceux qui ont pu rectifier certaines de mes erreurs d'orthographe