SUDOKU 数独 :en japonais u se prononce eu [ɯ symbole API) ] et non ou à fortiori u.
Approche commerciale des éditeurs
La gratuité d'accéder en ligne au jeu du sudoku est fortement mis en avant par les moteurs de recherche dans leur publication sur le WEB pour en favoriser l'addiction.
L'éditeur ne fournit aucune indication sur les méthodes de la résolution de sa grille qu'il a éditée d'où la multitude d'études sur le sujet renforçant l'attractivité de ce jeu en exagérant sa facilité.
A cette fin, la taille de case est ample avec l'emploi préconisé d'une gomme et d'un crayon pour inscrire le candidat et compléter la grille. Il arrive souvent que 8 sections soient valides et non la dernière. La correction par retour en arrière nécessite un marquage préalable fastidieux suivant l'importance de la longueur de la chaîne dont l'extrémité est en défaut, à fortiori si d'autres choix aléatoires se présentent.
En effet, l'éditeur a le libre choix des révélés. Toutes les grilles publiées imposent la réduction de couples, sauf en cours/fin de partie où il ne reste plus qu'un chiffre à remplir dans une section. Elle se concrétise par la présence de chiffres révélés positionnés sur les médianes de chaque section de la grille comprenant 9 cases .
rappel: Les médianes d'un quadrilatère sont les segments reliant les milieux des côtés opposés.
Réduire un couple de cases consiste à rompre l'indétermination en retenant qu'un seul candidat valide sur toutes les combinaisons binaires possibles dans l'une et à l'exclure dans l'autre, le choix aléatoire étant écarté.
Exemple: Soient 9,1,3 les révélés situés sur la médiane d'une section adjacente à une autre section générant dans celle-ci les couples (9,1),(9,3),(1,3) dans deux cases en bordure de section. Si le candidat 9 est sélectionné dans une case, seuls les couples (1,3) sont à retenir dans l'autre. Si le candidat 1 est retenu dans une case, l'autre vaut 3, la réduction étant opérée. Le processus est donc itératif.
La formule des combinaisons et non des arrangements prévaut. Dans une section vide, on peut former au maximum dans une bande (H ou V ) 2*3*6!/[(2!)(4!)] = 90 couples dual répartis dans les 9 cases.
La stratégie de réduction de couples est non indispensable pour clore une partie et nécessite un marquage fastidieux. Voir toutefois dans la grille BETA où le contenu de deux couples binaires exclut les candidats potentiels situés sur la même ligne/colonne dans une autre section sans pouvoir se réduire.
La pratique développe une adaptation neuronale dans la recherche des chiffres candidats selon la stratégie retenue.
Le sudoku réclame beaucoup de concentration. Une erreur de marquage dans la séquence 1 à 9 est toujours possible quand l'attention visuelle se relâche.
. Il est alors conseillé de reprendre plus tard la partie ou l'abandonner pour éviter le sentiment de frustration du à l'incapacité mentale de poursuivre le jeu si facilement commencé vis à vis du niveau de difficultés affiché.
A contrario, la rapidité de remplissage final de la grille apporte une moindre satisfaction due à sa facilité.
Les méthodes de résolution élémentaires ci-dessous faisant appel à la logique doivent être combinées car l'axiome mathématique du choix ne s'applique pas dans le sudoku par défaut d'unicité de méthode de résolution.
Selon celui-ci, pour n'importe quelle collection d'ensembles non vides, il existe un moyen de choisir exactement un élément de chaque ensemble, or toute section peut être adressée de 9 façons différentes dans la grille.
Énoncé des trois techniques de base pour application conjointe:
- Exclusion d'un candidat d'une case dans une ligne/colonne par croisement avec une colonne/ligne contenant déjà sa valeur et test de son report dans la même séquence de chiffres 1 à 9. Les sections n'admettant pas de doublons, le même chiffre dans une section ne peut être inséré dans une autre case de la même section, son report s'effectuant dans les autres sections adjacentes sur une autre ligne/colonne.
- Fermeture d'une séquence de candidats répartis dans une ou plusieurs sections et dans laquelle il ne manque plus qu'un chiffre.
Comment commencer la partie de façon la plus rationnelle face à des (nombres) révélés de 1 à 9 dans une grille?
La méthode d'encadrement s'effectue à partir des boucles non fermées en reprenant à chaque itération les candidats déjà validés avec cette méthode et les révélés initiaux. Elle est toutefois vite limitée en présence de couples.
La grille AlPHA en fournit un exemple avec la probabilité de réussite de 1/81 pour 4 encadrements différents d'un même chiffre.
La méthode d'exclusion (grille GAMMA) prend le relais en ciblant directement les cases disponibles dans une section à partir des chiffres révélés dans les deux autres sections puisqu'elles complémentent lignes/colonnes comportant ces chiffres.
En début de partie, en l'absence de chiffres révélés, la probabilité de réussite d'un candidat adressé en coordonnées orthogonales (n,m) avec n ∈ (1,9) , m ∈ (A,I) est donnée par la formule:
prob (n,m) =prob (n) ∈ Ln * prob (m) ∈ Cm= (1/9)*(1/9)=1/81 car (n,m)=Ln ∩ Cm
Il n'est pas impossible que 2 chiffres seulement ouvrent la partie comme dans la grille BETA avec les révélés en rouge, candidats en noir.
On obtient le candidat (5,A)= 6 à l'aide de deux lignes contenant 6 explicitement.
Les couples dual notés (3G,3I)=(6,9) sont résilients, car, sans pouvoir être réduits,ils positionnent le candidat 1 par exclusion sur les couples binaires (2G),(2,I) donc (3B)=1, sachant (4,C)=1. De plus, ils permettent l'élimination des candidats 6 et 9 sur la ligne 3 dans la première section, donc (1B)=6, le tout par encadrement.
La présence d'un couple dual x/y - deux cases ne comportant que les chiffres x et y - dans une même section, sans possibilité de réduction, limite donc le choix des autres candidats par exclusion dans d'autres sections.
En effet, dans un couple généré par un révélè, les valeurs sont (ce révélè, x?) ou (x?, ce révélè). Seul un révélè positionné sur une médiane ne générant qu'un seul couple au lieu de trois dans une autre section permet toutefois de constituer une ligne/colonne contenant cette valeur et la poursuite de la méthode d'encadrement.
Dans la grille GAMMA, la recherche dans la section H1,V1 de révélés dans les autres sections adjacentes est inutile car 1,3,4,5 y figurent déjà
Dans la grille EPSILON, (4,E) = 7 par application de la fermeture d'une séquence répartie dans une ou plusieurs sections et dans laquelle il ne manque plus qu'un chiffre.
Certains chercheurs évoquent des stratégies basées sur l'association de couples, uniques par section en les chaînant à travers la théorie mathématique des graphes.
Leur temps de résolution serait optimal dés qu'un couple dual est réduit mais ils ne sont résilients que par la position des autres chiffres déjà validés. A titre d'exemple ci-dessous, la chaîne (9,7),(7,3),(3,9). Le couple dual résilient (9,7) doit être réduit pour briser la chaîne avec les méthodes exposées en début de cet exposé!
Le bon positionnement des candidats en fin de partie - et sa réussite - peuvent s'effectuer visuellement en reprenant la méthode d'élaboration d'une grille de sudoku ci-dessous, la fermeture de toutes les boucles ayant été constatée.
Élaboration d'une grille de SUDOKU
Une grille de sudoku a toujours au moins une solution. Elle peut être obtenue par programme informatique.
En effet, la probabilité de non alignement pour tout chiffre sur 3 cases horizontales/verticales doit être égale à 1, à savoir: nombre de cas possibles pour le chiffre dernière case=3 sachant la probabilité de non alignement pour la deuxième case du à la première case vaut 2/3.
Il s'ensuit que trois cases permettent à coup sûr un seul encadrement d'un candidat. Il faut donc, pour valider localement ce dernier 3 autres encadrements et donc pour la totalité de la grille, faire appel à 9 cases,d'où la notion de boucle fermée précisée ci-dessous. A défaut, il y aura deux candidats identiques dans une section.
L'élaboration d'une grille de sudoku s'effectue de manière itérative suivant la méthode ci-dessous. Elle est à portée de tout pratiquant avec les conventions de numérotation des sections de 9 chiffres de la gauche vers la droite, de haut en bas de I à IX.
Huit boucles itératives circulaires fermées avec les chiffres de 1 à 9 sont pré-marquées en commençant par la section I en respectant la règle du non alignement. Cette étape achevée, l'inscription des chiffres dans la section V (chiffres 1 et 2 en rouge) ne peut s'effectuer que par encadrement.
Le concepteur de la grille propose un extrait du marquage en ne laissant subsister en début de partie que les révélés à charge pour le challenger de la compléter par des candidats.
La rupture des boucles (chiffres 2 en jaune) lui permet une grande liberté pour complexifier leur reconstitution. L'absence de quatre chiffres dans la boucle correspondante ne donne aucune indication sur sa position dans la section V (chiffre 2 case bleue). De ce fait, l'essai de toutes les combinaisons possibles en remplissant les cases vides pour reconstituer le chaînon manquant ne peut se faire à la main. La technique ci-dessous évite ce désagrément:
Les boucles doivent être fermées l'une après l'autre. Si une boucle est formée de plusieurs mailles optionnelles, chacune d'elles sera testée en cas de duplication de candidats sur une ligne/colonne par complémentarité sans qu'il soit utile de modifier le reste de la grille.
Le marquage actualisé au fur à à mesure de toutes les combinaisons possibles des cases dans la totalité de la grille lève en principe l'indétermination mais n'est pas le plus pertinent car il contient un sous-ensemble de couples inutiles pour valider rapidement un candidat par la logique.
Notons toutefois que la validité du candidat unique dans une section - le terme singleton est évoqué- en écartant les autres cases à choix multiples obtenus par marquage.
Compléments
Nombre minimal de nombres révélés pour aboutir à deux grilles distinctes: >17
Cette grille de 17 chiffres a les deux solutions ci-dessus
Le nombre de chiffres révélés diminue avec le niveau croissant de difficultés (de 40 à 20).
