Résumé :
- 5 procédures de base pour une résolution manuelle de grille avec cette application de sudoku
- Préambule
- Introduction
- Règle du jeu de sudoku
- Description de la partie haute de l'écran d'accueil, au-dessus de la grille (espace dit manuel)
- Liste des opérations manuelles pour résoudre une grille de sudoku (sélection et désélection, effacement, méthodes de résolution)
- Procédures diverses (sélection de grille, réinitialisatin des archives, enregistrement de grille avec archive personnelle par défaut, test pour modification du programme)
- 9 méthodes basiques de résolution manuelle de grilles de sudoku
- 10 méthodes difficiles de résolution manuelle de grilles de sudoku
- Description de l'interface de l'écran pour la résolution de grilles de sudoku par ordinateur et la génération de grilles (espace dit automatique)
- Signification des icônes de l'espace automatique
- La zone des messages
- Les 7 listes (Méthodes, Méthodes unicité, Etapes, Variantes, Hypothèses, Archives, Grilles)
- L'écran des filtres et options
- Le calcul de grilles de sudoku par ordinateur
- L'application ponctuelle des méthodes de résolution
- La création de grilles de sudoku
- La génération de grilles de sudoku
- Les crashs pour impossibilité
- Les crashs pour défaut d'unicité et les méthodes pour les éviter
- Le clavier virtuel
- Utilisation des différents navigateurs
- Limitations de l'utilisation de l'imprimante en couleur
- Messages d'erreurs
- Bugs occasionnels identifiés et non résolus avec recherche de palliatifs
- Liste des méthodes implantées dans ce programme de sudoku avec exemples
- 5 procédures de base pour une résolution manuelle de grille avec cette application de sudoku
|
Au chargement du programme, une grille très facile, implantée en dur dans le programme, apparaît à l'écran. Avec l'affichage de son nom et du nom de l'archive qui la contient.
Pour une résolution manuelle de cette grille, les 5 procédures de base sont les suivantes :
- Déplacer la souris sur une des cases vierges où on pense connaître le chiffre à positionner. Un tableau interne apparaît dans cette case avec les chiffres-candidats de cette case; cliquer sur un de ces chiffres pour le sélectionner. Avec une écran tactile, appuyer sur une case de la grille, pour faire apparaître le tableau interne de ses chiffres-candidats et appuyer sur un de ces chiffres pour le sélectionner.
- Cliquer sur l'icône en haut de l'écran, pour faire apparaître la grille avec les cases vierges qui se sont remplies de leurs chiffres-candidats. Puis positionner le souris sur une de ces cases avec ses chiffres-candidats, ce qui fait apparaître le tableau interne de cette case, puis cliquer sur un des chiffres de ce tableau, ce qui désélectionne ce chiffre dans cette case. Pour revenir à la grille sans les chiffres-candidats, cliquer à nouveau sur l'icône . Avec un écran tactile, il faut appuer sur l'icone , puis appuyer sur une case avec ses chiffres-candidats, et enfin appuyer sur un des chiffres du tableau interne qui apparaît, pour le désélectionner. Réappuyer sur l'icône pour revenir à la grille sans les chiffres-candidats.
- Pour changer de grille, cliquer sur l'icône en haut de l'écran. Cette grille nouvelle aléatoire est encore très facile. Pour obtenir une grille plus difficile, voire diabolique, sélectionner, dans le menu déroulant sous la liste d'icônes, appelé Niveau de difficulté, le niveau de la grille que vous allez sélectionner aléatoirement.
- Quand on sélectionne ou désélectionne un chiffre dans une case, un message sous la grille indique l'opération qui vient d'être effectuée. Une assistance à la résolution manuelle existe si on coche la rubrique Assistance à la résolution manuelle, sous la liste d'icônes en haut de l'écran. Cette assistance se manifeste alors par l'apparition du symbole ! à la fin du message sous la grille, pour indiquer que l'opération est correcte.
- Pour annuler la dernière opération manuelle, il faut cliquer (ou appuyer, avec un écran tactile comme un téléphone portable) sur l'icône d'annulation , en haut de l'écran. Pour valider cette opération d'annulation, il faut cliquer (ou appuyer, avec un écran tactile comme un téléphone portable) 2 fois sur l'icône de basculement d'affichage en haut de l'écran.
|
- Préambule
|
Au chargement du programme, une grille très facile, implantée en dur dans le programme, apparaît à l'écran. Avec l'affichage de son nom et du nom de l'archive qui la contient.
Le nom de cette grille apparaît aussi en fin de la liste des grilles de cette archive, sous la grille et après la zone de commentaires. En cliquant sur ce nom de grille, dans cette liste, le programme calcule cette grille et affiche la solution. Ce n'est pas le but recherché, puisque le but du programme est d'abord de permettre une résolution manuelle de grille.
En cas de clic (ou appui pour un écran tactile) sur la grille de départ, ayant ainsi fait apparaître la solution,
il faut, pour récupérer la grille originelle, naviguer avec les flèches haut et bas.
Ceci est valable aussi pour une création manuelle de grille ou pour une génération de grille (voir ci-après)
Il existe 3 types de grilles de sudoku :
- Celles existant dans le programme, au nombre de 151, de tout niveau de difficulté, chargées aléatoirement, soit au démarrage du programme, soit en cliquant sur l'icône dans la barre d'icônes en haut de l'écran. Le niveau de difficulté de cette grille est déterminé par le choix qui a été fait dans la liste déroulante du niveau de difficulté.
- Celles créées par l'utilisateur, en cliquant sur l'icône dans la barre d'icônes en haut de l'écran. Cela fait apparaître une grille vierge, que l'utilisateur peut remplir, à l'aide d'une procédure expliquée ci-après. L'utilisateur doit aussi renseigner le nom de cette grille qui, au moment de l'enregistrement va être chargée dans l'archive dénommée "Nouvelle archive". L'utilisateur peut aussi changer le nom de cette archive, auquel cas la grille va être chargée dans cette archive personnelle.
- Celles générées par l'ordinateur quand l'utilisateur clique sur l'icône dans la première ligne de barres d'icônes en haut de l'écran, dans l'espace de création automatique (et non plus l'espace de résolution manuelle).
Il vaut mieux cocher l'assistance à la résolution manuelle, pour être bien sûr que l'opération manuelle venant d'être effectuée, est bien correcte. Ceci se manifeste par l'apparition du symbole ! à la fin du message sous la grille.
Cette assistance fonctionne bien sûr pour les grilles existant en dur dans le programme (dont le programme connaît le résultat) Elle fonctionne également pour les grilles personnelles, créées ou générées, car lors du chargement d'une de ces grilles, le programme commence par la calculer, afin d'identifier le résultat, ce qui permet de valider l'assistance manuelle. Ce calcul préparatoire peut prendre du temps, entre quelques secondes pour des grilles faciles, et jusqu'à quelques minutes pour des grilles très difficiles avec hypothèses (sur ordinateur), mais jusqu'à 30 minutes sur écran tactile (téléphone portable); il faut alors patienter le temps que ce calcul s'achève, avant de commencer la résolution manuelle.
La grille peut être affichée sous 2 formes : avec ou sans les chiffres candidats dans les cases non encore affectées (en cliquant alternativement sur l'icône de bascule affichage en haut de l'écran ). Lorsque l'utilisateur survole des cases de la grille, un tableau interne apparaît dans la case en cours de survol, contenant les chiffres candidats de cette case. Si l'utilisateur clique sur un de ces chiffres, ce chiffre est affecté à la case, si la grille ne fait pas apparaître les chiffres-candidats dans les cases non affectées, sinon, ce chiffre est désélectionné comme chiffre candidat de cette case.
L'utilisateur résoud la grille, soit en affectant des chiffres aux cases non encore affectées, soit en éliminant des chiffres-candidats dans les cases non encore affectées.
Si l'utilisateur cale, il peut demander à l'ordinateur de lui indiquer une méthode de résolution efficace, et de lui en montrer le résultat de l'application de cette méthode. Cela peut s'obtenir en cliquant sur l'icône en haut de l'écran, et en choisissant une méthode dans la liste des méthodes qui apparaît sous le message sous la grille. Il peut aussi choisir la rubrique "Toutes les méthodes applicables" en haut de cette liste, auquel cas, l'ordinateur calcule toutes les méthodes efficaces, affiche en rouge tous les chiffres candidats éliminés par ces méthodes efficaces et, sur fond vert ou orange, les chiffres ayant contribué à trouver une solution efficace. Il indique aussi la liste de toutes les variantes de toutes ces méthodes efficaces.
Cela permet à l'utilisateur d'essayer de comprendre comment fonctionnent ces méthodes, dont le résultat est expliqué sous la grille : explication particulière de l'exemple en cours, et explication générale de la manière dont fonctionne la méthode présentée.
Bien attendre la fin du calcul des méthodes par l'ordinateur, applicables ou pas, car cela prend du temps.
Une liste exhaustive d'exemples d'utilisation de ces méthodes (32 pour impossibilté, 19 pour défaut d'unicité) est présentée à la fin de cette aide. Avec explication particulière de chaque exemple présenté, et une explication générale de la méthode utilisée.
En résumé, la résolution manuelle d'une grille affichée, soit extraite des grilles existantes dans le programme, soit créée manuellement à partir de grilles existantes dans des revues ou sur internet, soit générées aléatoirement par le programme, se fait de manière simple :
- Sur ordinateur, survoler une case non affectée avec la souris, ce qui fait apparaître un tableau interne de cette case contenant les chiffres candidats de cette case, puis cliquer sur un de ces chiffres, ce qui affecte ce chiffre à cette case.
- Sur téléphone mobile, appuyer sur une case non affectée de cette grille, ce qui fait apparaître son tableau interne contenant ses chiffres candidats, puis appuyer sur un des chiffres de ce tableau interne, ce qui affecte ce chiffre à cette case.
Répéter cette opération jusqu'à la résolution de la grille, où toutes les cases sont affectées.
Si on clique sur l'icône de bascule affichage , en haut de l'écran, les chiffres candidats apparaissent dans les cases vierges. Dans ces conditions, l'opération ci-dessus, soit sur ordinateur, soit sur téléphone portable, permet, non plus d'affecter un chiffre à une case, mais de désélectionner un chiffre de cette case. C'est cette opération, plus que l'affectation d'un chiffre à une case, qui permet d'approcher plus rationnellement de la solution.
L'utilisateur peut corriger la dernière opération manuelle effectuée en cliquant (ou appuyant dessus) sur l'icône d'annulation , en haut de l'écran, ce qui annule la dernière opération manuelle, puis en cliquant 2 fois sur l'icône de bascule affichage .
En fait, toutes les méthodes de résolution, de la plus simple à la plus sophistiquée, visent à désélectionner des chiffres candidats dans les cases. C'est ce qui est expliqué tout au long de cette aide.
- Introduction
|
Ce programme est composé de 2 parties distinctes :
- une première partie, appelée espace de résolution manuelle de grilles de sudoku (ou espace manuel), permet à un utilisateur de résoudre manuellement des grilles choisies parmi 151 grilles implantées dans la programme, de tout niveau de difficulté. Au chargement du programme, c'est l'écran d'accueil de cet espace qui apparaît.
- Une deuxième partie, appelée espace de calcul de grilles par ordinateur (ou espace automatique).
C'est cette 2ème partie qui constitue l'originalité de ce programme, le distinguant de tout ce qui existe sur internet. Car c'est cela qui permet de résoudre toutes les grilles existantes et d'expliquer le mécanisme de résolution. Cette partie va au delà des méthodes de base qu'utilisent la majorité des utilisateurs, méthodes au nombre limité (environ 5); elle propose 32 méthodes sophistiquées, couvrant la quasi-totalité des méthodes employées par les joueurs de compétition, auxquelles il faut ajouter 19 méthodes couvrant la majorité des méthodes concernées par les défauts d'unicité.
Ces 2 espaces partagent les mêmes données et communiquent entre eux.
Ce programme ne se contente donc pas de suivre pas à pas une résolution manuelle, en fournissant des indices à l'occasion, comme le font la quasi-totalité des solveurs de sudoku sur internet.
L'application sur internet www.sudokunew.com est un exemple d'application réussie sur internet. Ecrite en open source, utilisant les outils de base internet (HTML, CSS et javascript), elle peut servir de modèle pour le développement d'applications sur internet. La méthode utilisée pour aboutir à ce résultat sera expliquée ultérieurement par le développeur, Raoul SALZBERG. 3 principes doivent être respectés dans un tel développement : avoir un code propre dit DRY (Don't Repat Yourself, voulant dire de ne pas se répéter), actualiser les images d'exemples au fur et à mesure du développement, et nettoyer régulièrement les portions de code devenues obsolètes (code dit mort).
Pour résoudre la grille d'accueil, comme le font tous les sites de sudoku, il faut survoler une case avec la souris, ce qui fait apparaître un tableau interne, puis sélectionner un chiffre de cette case en cliquant dessus.
Pour une utilisation avec écran tactile comme par exemple avec un téléphone portable, il faut appuyer sur une case, ce qui fait apparaître un tableau interne, puis appuyer sur un chiffre de ce tableau pour le sélectionner.
Recommencer cette procédure jusqu'à la solution. Une liste des étapes de résolution, sous le diagramme, retrace, au fur et à mesure, l'historique de cette résolution, que l'on peut consulter à tout moment.
Pour changer de grille, il suffit de cliquer sur l'icône de sélection de grille en haut de l'écran.
La première grille qui apparaît au chargement du programme est une grille très facile. Pour obtenir une grille plus difficile, il suffit de sélectionner un niveau de difficulté dans la liste déroulante sous les icônes du haut de l'écran, avant de cliquer sur l'icône de sélection de grille .
Pour obtenir de l'aide en cours de résolution, il faut cocher l'assistance à droite de la sélection du niveau de difficulté. Cette aide se manifeste par l'apparition du symbole ! à la fin du message sous la grille. Celui-ci indique que la sélection est correcte.
Il est possible d'annuler la dernière sélection, en cliquant sur l'icône d'annulation .
Dans le cas d'une utilisation, soit avec une souris, soit avec un écran tactile, il faut d'abord faire apparaître le tableau interne des chiffres candidats d'une case, soit en survolant cette case avec la souris, soit en appuyant sur cette case (dans le cas d'un écran tactile, comme pour un téléphone portable).
Il existe alors 5 facilités dans le cas d'utilisation d'une souris, et 3 facilités dans le cas d'utilisation d'un écran tactile :
- Sélection d'un chiffre du tableau interne, soit par clic gauche de la souris sur ce chiffre, soit par appui sur ce chiffre (écran tactile)
- Dans le cas d'utilisation d'une souris, désélection d'un chiffre du tableau interne par clic droit de la souris sur ce chiffre
- Cette désélection peut se faire aussi en cliquant sur l'icône de bascule affichage des chiffres candidats dans les cases , en haut de l'écran, ce qui fait donc apparaître ces chiffres-candidats, puis de survoler une case avec la souris, ce qui fait apparaître son tableau interne. La sélection d'un des chiffres de ce tableau, le désélectionne. Cette opération est également valable avec écran tactile (téléphone portable), où la sélection se fait en appuyant sur un des chiffres du tableau interne.
- Dans le cas d'utilisation d'une souris, dévalidation d'un chiffre affecté à une case par double clic gauche de la souris sur ce chiffre
- Cette dévalidation peut se faire également en cliquant sur l'icône d'annulation , ce qui dévalide la dernière sélection ou désélection manuelle.
Dans un programme comme celui-ci, il est obligatoire qu'il reste des erreurs appelées bugs. Au fur et à mesure de son utilisation, un ou plusieurs bugs peuvent apparaître, et il faut ensuite les éliminer. Certaines techniques pointues sont les plus concernées par ces bugs. C'est le cas des méthodes d'élimination des défauts d'unicité.
Un utilisateur persévérant peut arriver à planter le programme en multipliant les procédures qui peuvent parfois être contradictoires, laquelle contradiction n'a pas été correctement identifiée par un message d'erreur ! En renseignant celui qui a réalisé ce programme, celui-ci pourra y apporter une correction.
En cas de plantage, il faut revenir aux 4 archives de base, éliminant les archives personnelles. Pour cela, sélectionner la liste des archives, et cliquer sur l'icône de retour aux 4 archives de base , se trouvant dans la liste des 4 icônes pilotant les archives. Cette procédure doit être autorisée dans l'écran des filtres et options.
|
- Règle du jeu de sudoku
:
|
Une grille de sudoku est constituée d'un tableau carré 9x9 partiellement rempli de chiffres de 1 à 9, avec comme contrainte d'utiliser tous les chiffres de 1 à 9 dans chaque zone de 9 cases (ligne ou colonne ou bloc). Les lignes sont numérotées de 1 à 9 (de haut en bas), les colonnes de A à I (de gauche à droite), les blocs de 9 cases de 1 à 9 (à partir du coin en haut et à gauche, pour le bloc de numéro 1; pour une numérotation de gauche à droite et de haut en bas).
A partir d'une grille initiale partiellement remplie de chiffres, avec un nombre minimum de 17 cases renseignées, satisfaisant la contrainte ci-dessus, il s'agit de trouver, étape par étape, une grille finale complètement remplie de chiffres (toutes les cases sont renseignées avec un chiffre) et respectant cette même contrainte.
Dans la grille initiale, les cases vides contiennent en fait des chiffres potentiels respectant la contrainte. Ils sont dénommés chiffres candidats.
A chaque opération, manuelle ou automatique, les chiffres candidats apparaissant en rouge sont éliminés.
|
- Description de la partie haute de l'écran d'accueil, au-dessus de la grille (espace dit manuel)
:
|
La partie haute de l'écran d'accueil du programme, au-dessus de la grille, est la suivante :
Cette image est composée, dans l'ordre, des éléments suivants :
- Une rangée de 11 icônes, dont la signification est décrite ci-dessous
- Sous cette rangée d'icônes, une liste déroulante des niveaux de difficulté de la grille, que l'utilisateur peut sélectionner avant de choisir aléatoirement une grille du programme en cliquant sur l'icône
- A droite de cette liste de niveaux de difficulté, se trouve une case à cocher qui, si elle est cochée, fournit une assistance à la résolution manuelle de la grille, en indiquant si l'opération que vient d'effectuer l'utilisateur est correcte, par la présence, à la fin du message sous la grille, du symbole !.
- Le nom de l'archive dans laquelle se trouve la grille
- Le nom de la grille
Signification des 11 icônes dans l'écran d'accueil
Impression de la grille
Transfert dans l'espace de résolution par ordinateur et de génération de grilles (espace dit automatique)
Bascule affichage des chiffres-candidats dans les cases de la grille
Appel aléatoire de grille en archive
Annulation dernière action manuelle
Aide (cet écran)
Calcul automatique d'une grille utilisant toutes les méthodes de résolution disponibles, calcul à partir de l'étape en cours (souvent depuis le début, pour un calcul complet), avec affichage final de la liste des étapes et de la grille remplie (si solution sans hypothèse), avec indication si la grille est correcte. Quand une grille est chargée (soit par création, soit par génération, soit par sélection), il est possible de lancer son calcul par ordinateur en cliquant sur cette icône.
Accès à la liste des méthodes de résolution disponibles dans ce programme, affichée sous le diagramme de la grille
Création d'une nouvelle grille personnelle, partant d'une grille vierge, et effectuant une saisie manuelle des chiffres dans les cases. La grille est mise à zéro et le titre affiche la lettre N. On peut alors remplir cette grille à la main, et renseigner son titre (éventuellement avec le clavier virtuel qui s'affiche à l'écran quand on clique dans la zone de titre). La grille peut être remplie grâce au tableau interne apparaissant dans une case lors de son survol par la souris (voir ci-dessus) puis sauvegardée, en cliquant sur l'icône d'enregistrement (icône suivante), ce qui fait apparaître son nom en fin de la liste affichée des grilles. Cette opération de sauvegarde n'est pas possible dans les 4 archives de base, la grille étant alors incorporée automatiquement dans une archive auxiliaire appelée "Nouvelle archive".
Enregistrement de la grille en cours dans le webstorage de l'utilisateur, avec enregistrement éventuel de sa nouvelle archive, celle dont le nom est affiché. Cela fait apparaître la grille en fin de la liste des grilles de l'archive en cours (avec éventuellement le numéro de l'étape de calcul en cours, pour un enregistrement pendant le calcul). Il n'est pas possible d'enregistrer dans les 4 archives de base, une archive auxiliaire étant créée pour cela, appelée "Nouvelle archive". Il faut avoir renseigné au moins 17 cases avant de sauvegarder cette grille nouvellement créée. Il faut renseigner au préalable les noms de l'archive et de la grille. Attention : 2 grilles différentes peuvent avoir le même nom; mais ce n'est pas recommandé.
Suppression d'une grille personnelle. Après suppression, c'est la dernière grille de la liste des grilles enregistrées dans l'archive qui apparaît à l'écran. Si la grille supprimée est la dernière de l'archive, cette archive est supprimée. Il n'est pas possible de supprimer des grilles des 4 archives de base.
Lorsque la souris survole l'une de ces icônes, un message en jaune apparaît en haut et à gauche de l'écran, indiquant la signification de cette icône; de plus, l'icône se dilate. L'utilisateur peut alors cliquer sur cette icône pour l'exécuter.
Pour une résolution manuelle de la grille, les éléments suivants (décrits ci-après) apparaissent sous la grille :
- Un message indiquant l'opération que vient d'effectuer l'utilisateur
- La liste des étapes de cacul, retranscrivant l'historique des actions manuelles de l'utilisateur, surmontée de 3 icônes à cliquer, 2 pour la navigation haut et bas dans la liste des étapes de calcul, la troisième pour éventuellement imprimer la liste des étapes. Ces icônes sont activées par le survol de la souris, qui fait apparaître un message en jaune au bas de cette icône, en indiquant la signification, de même que l'icône se dilate
|
- Liste des opérations manuelles pour résoudre une grille de sudoku (sélection et désélection, effacement, méthodes de résolution)
|
La grille à résoudre est, en général, celle apparaissant au moment du chargement du programme, grille très facile, faisant partie des grilles existantes dans le programme.
La sélection d'un chiffre dans une case
La procédure consiste à survoler une case avec la souris, ce qui fait apparaître le tableau interne des chiffres-candidats de cette cas, puis à cliquer sur un de ces chiffres pour le sélectionner.
Cette même grille, lorsque la souris survole la case G3, faisant apparaître son tableau interne de chiffres candidats :
Cette même grille, après avoir cliqué sur le chiffre 8 de ce tableau interne avec le bouton gauche de la souris, ce qui sélectionne ce chiffre 8 pour la case G3 :
La désélection d'un chiffre dans une case
La procédure consiste d'abord à cliquer sur l'icône de bascule affichage en haut de l'écran, ce qui fait apparaître les chiffres-candidats dans les cases de la grille.
Puis la procédure est la même que pour la sélection d'un chiffre pour une case, c'est-à-dire survoler une case avec la souris, ce qui fait apparaître le tableau interne des chiffres-candidats de cette cas, puis à cliquer sur un de ces chiffres pour le désélectionner. Ce chiffre disparaît de la liste des chiffres-candidats de cette case.
La grille de départ avec ses chiffres candidats, lorsque l'on clique sur l'icône de bascule affichage en haut de l'écran :
Cette même grille, lorsque la souris survole la case G3, faisant apparaître son tableau interne de chiffres candidats :
Cette même grille, après avoir cliqué sur le chiffre 9 de ce tableau interne avec le bouton gauche de la souris, ce qui désélectionne ce chiffre 9 pour la case G3 :
L'effacement de la dernière opération manuelle
La procédure consiste à cliquer sur l'icône d'effacement en haut de l'écran , puis à cliquer 2 fois sur l'icône de bascule affichage en haut de l'écran.
L'utilisation des méthodes de résolution
La procédure consiste à cliquer sur l'icône de sélection de liste de méthodes en haut de l'écran, ce qui fait apparaître la liste des méthodes dans la zone des listes.
Puis à sélectionner une méthode dans cette liste, en cliquant dessus. Cela fait apparaître une nouvelle liste, celle des variantes de cette méthode, si celle-ci est applicable. Si la méthode est non effective, aucune variante n'apparaît.
Sur la grille, l'ensemble des chiffres éliminés par toutes les variantes de cette méthode apparaît en rouge.
La première ligne de la liste des méthodes s'appelle l'ensemble des méthodes applicables. En cliquant dessus, le programme parcourt toutes les méthodes de résolution, et fait apparaître toutes celles qui sont applicables, c'est-à-dire qui sont effectives.
Dans ce cas, la liste de toutes les variantes de toutes les méthodes applicables apparaît dans la zone de liste. Sous la grille, dans la zone des messages, la liste des méthodes applicables apparaît avec le nombre de variantes de chaque méthode et, sur la grille, apparaissent en rouge, l'ensemble des chiffres affectés par l'application de toutes ces méthodes.
Parmi les icônes en haut de la liste des variantes de toutes ces méthodes, l'icône permet de faire disparaître tous les chiffres rouges de la grille.
En appliquant plusieurs fois cette procédure en 3 étapes (clic sur l'icône de sélection des méthodes, puis sélection de la première ligne de cette liste de méthodes, puis clic sur l'icône éliminant les chiffres rouges de la grille), on arrive très rapidement à la solution. Il faut appliquer en moyenne 3 fois cette procédure pour trouver la solution.
La grille de départ, après avoir cliqué sur l'icône de sélection de liste de méthodes en haut de l'écran, puis avoir cliqué sur la première rubrique de cette liste de méthodes appelé "Toutes les méthodes applicables", ce qui a eu pour effet d'appliquer toutes les méthodes du programme applicables, montrant la liste des chiffres candidats éliminés, en rouge sur la grille :
Cette même grille, après avoir cliqué sur l'icône d'élimination des chiffres rouges en haut de la liste des variantes :
La liste des méthodes applicables à la grille Amandier comporte 66 variantes (début de la liste) :
Les opérations de sélection et de désélection de chiffres candidats dans les cases de la grille, sont celles de la résolution manuelle de cette grille.
La sélection de la liste des méthodes s'effectue en cliquant sur l'icône . Dans cette liste, il est possible de sélectionner une méthode particulière, pour vérifier si elle est applicable, avec le nombre de variantes qu'elle génère. Il est aussi possible de sélectionner la première ligne de cette liste, à savoir la liste de toutes les méthodes applicables. Dans ce cas, il faut être patient, car l'exécution de toutes les méthodes peut prendre du temps.
Cela permet de connaître l'ensemble des méthodes applicables, avec leur nombre de variantes, ainsi que l'effet sur la grille, avec l'apparition de chiffres en rouge, qui sont ceux qui sont éliminés.
Car l'opération de sélection de l'ensemble des méthodes applicables est réalisée par l'ordinateur, montrant à l'utilisateur ce qu'il est possible de faire en appliquant des méthodes sophistiquées, que les experts en sudoku savent faire.
Si aucune méthode n'est applicable, il est nécessaire de faire une hypothèse aléatoire, qui, si elle n'aboutit pas, nécessite de la corriger, ce qui prend beaucoup de temps, car il est parfois nécessaire de faire des hypothèses en cascade.
L'ordinateur sait calculer automatiquement une grille, même avec hypothèses, ce qui est expliqué ci-après.
Il est donc possible de sélectionner, dans la liste des méthodes, une méthode particulière, pour savoir si elle est applicable, et le nombre de variantes qu'elle peut générer.
Attention : Pour sélectionner ensuite une autre méthode, il faut d'abord resélectionner la liste des méthodes , avant de choisir cette nouvelle méthode.
| - Procédures diverses (sélection de grille, réinitialisatin des archives, enregistrement de grille avec archive personnelle par défaut, test pour modification du programme)
|
Sélection d'une grille
Pour sélectionner une grille, il est nécessaire d'être dans l'espace automatique, pour y sélectionner la liste des archives, puis, dans cette liste, sélectionner l'archive où se trouve cette grille, sélectionner cette archive, ce qui fait apparaître la liste des grilles dans cette archive, et enfin y sélectionner la grille en question :
Depuis l'espace d'accueil, cela donne la liste des opérations suivantes :
- Cliquer sur l'icone de transfert vers l'espace automatique , en haut de l'écran
- Cliquer sur l'icône de sélection de la liste des archives dans la 2ème ligne en haut de l'écran
- Descendre dans la liste des archives et y sélectionner l'archive dans la quelle se trouve la grille recherchée, ce qui sélectionne la liste des grilles de cette archive
- Sélectionner la grille recherchée dans cette liste de grilles
Attention, si l'option de calcul lors de la sélection est activée, dans l'écran des filtres et options, la sélection entraîne un calcul de cette grille, ce qui permet de rendre effective l'assistance à la résolution manuelle. Pour des grilles difficiles, ce calcul peut être long; il vaut mieux alors de désactiver cette option, pour ne pas avoir à patienter à chaque sélection de grille.
Pour activer l'aide à la résolution manuelle, il faut cocher cette option dans l'espace de calcul manuel.
Réinitialisation des archives
Pour différentes raisons, il est parfois nécessaire d'effacer toutes les archives personnelles, ne gardant que les 4 archives de base. Le cas le plus fréquent est celui d'un plantage, ayant déterioré la liste des archives, rendant impossible la sélection de grilles.
Depuis l'espace d'accueil, cela donne la liste des opérations suivantes :
- Cliquer sur l'icone de transfert vers l'espace automatique , en haut de l'écran
- Cliquer sur l'icône de sélection de la liste des archives dans la 2ème ligne en haut de l'écran
- Descendre dans la liste des archives et cliquer sur l'icône de réinitialisation des archives en haut de cette liste. Il faut pour que cette opération dangereuse puisse se faire, avoir sélectionné au préalable l'autorisation de la réinitialisation des archives, dans l'écran des filtres et options. Sinon, cette opération est refusée.
Enregistrement de grille avec archive personnelle par défaut
L'enregistrement de grille se fait en cliquant sur l'icône en haut de l'écran de l'espace d'accueil.
Si le nom affiché de l'archive fait partie des 4 archives de base, l'enregistrement de la grille s'effectue dans une archive personnelle automatique, appelée "Nouvelle archive". C'est souvent le cas lors de création de grille ou de génération de grille.
Sinon, si le nom de l'archive affiché est différent d'une des 4 archives de base, l'enregistrement de la grille se fait dans cette archive, ajoutée à la fin de la liste des grilles de cette archive. Si le nom de la grille existe déjà, la nouvelle grille va quand même s'installer à la fin de la liste des grilles, qui comprendra 2 grilles différentes avec le même nom. Ce n'est pas recommandé.
Test pour modification du programme
Cette facilité est disponible pour les utilisateurs désirant corriger ou agrandir cette application de sudoku, qui est en open source. Pour y avoir accès, il faut au préalable avoir coché cette option dans l'écran des filtres et options. Ceci fait apparaître l'icône en haut de l'écran, dans l'espace automatique.
Il suffit alors de cliquer sur cette icône, pour activer l'exécution de la fonction test() dans le programme en javascript iniautre.js.
| - 9 méthodes basiques de résolution manuelle de grilles de sudoku
:
|
Ces 9 méthodes, décrites ci-dessous, sont celles utilisées par la grande majorité des joueurs, celles que l'on retrouve sur tous les sites internet de sudoku, avec une numérotation des blocs comme suit :
- Singleton nu (case à un chiffre)
- Solo
- Jumeaux
- Triples
- Quadruples
- Jumeaux isolés
- Triples isolés
- Duo
- Trio
|
- 10 méthodes difficiles de résolution manuelle de grilles de sudoku
:
|
Ces 10 méthodes, décrites ci-dessous, sont une partie de celles utilisées par les joueurs experts en sudoku :
- W-Wing (l'aile de l'aigle)
- Le gratte-ciel
- L'attaque du cobra
- Sue-de-coq
- Le rectangle vide
- Le cerf-volant
- L'espadon (swordfish)
- XYZ-Wing (l'aigle et sa proie)
- XY-Wing (l'aigle et sa proie)
- XY-Wing (l'aigle et sa proie)
Une seule variété est décrite pour chacune de ces méthodes sophistiquées (exception de l'aigle et sa proie, 3 fois). L'ensemble des variétés de ces méthodes, ainsi que toutes les autres méthodes sophistiquées (contre les impossibilités et les défauts d'unicité), sont décrites à la fin de cette aide.
|
- Description de l'interface pour la résolution de grilles de sudoku par ordinateur et la génération de grilles (espace automatique)
:
|
Cet écran est chargé quand l'utilisateur clique sur l'icône de connexion à cet écran , dans l'écran d'accueil.
L'écran de cet espace de création de grilles et de calcul par ordinateur est le suivant :
Cet espace est composé, du haut en bas de l'écran par :
- Une 1ére ligne de 9 icônes pour les principales fonctions de base (impression, transfert vers l'espace de calcul manuel, bascule affichage des chiffres-candidats de la grille), pour la génération de grille, pour la gestion de grilles (enregistrement, suppression), pour le calcul par ordinateur (calcul complet ou calcul réduit) et enfin (icône optionnelle) pour le développement
- Une 2ème ligne de 9 icônes, dont 6 pour la gestion de 6 des 7 listes, 1 pour l'affichage de l'écran des filtres et options, 1 pour l'enregistrement des choix de cet écran des filtres et options, 1 pour l'indication du développeur de cette application de sudoku sur internet
- Le nom de l'archive dans laquelle se trouve la grille
- Le nom de la grille
- La grille proprement dite
- La zone des différents messages, dont, entre autres, la présentation du résultat de l'étape de calcul en cours, le suivi de la création de grille, l'affichage du résultat de la génération de grilles, les indications d'erreurs, le support au débogage, etc...
- La zone des listes surmontée de 3 icônes, pour la navigation dans la liste en haut et en bas, et pour l'impression de cette liste.
|
- Signification des icônes de l'espace automatique
|
1ère ligne des 9 icônes du haut de l'écran, dont une icône optionnelle pour les développeurs (5 des icônes sont communes avec des icônes de l'espace manuel) :
Impression de la grille sans les listes
Retour dans l'espace de résolution manuelle, y compris avec certaines données, dont le résultat de calcul par ordinateur, ou la proposition de résoudre des grilles qui ont été créés manuellement (grilles issues de revues ou sur internet) ou de grilles ayant été générées par ordinateur. Le niveau de difficulté est alors celui de la dernière grille sélectionnée dans l'espace de résolution par ordinateur.
Bascule affichage des chiffres-candidats dans les cases de la grille : affiche ou pas les chiffres-candidats dans les cases de la grille. Une option dans l'écran des filtres et options (voir ci-après) permet de ne faire apparaître que les cases ayant un nombre de chiffres-candidats inférieurs à un nombre donné
Enregistrement de la grille en cours dans le webstorage de l'utilisateur, avec enregistrement éventuel de sa nouvelle archive, celle dont le nom est affiché. Cela fait apparaître la grille en fin de la liste des grilles de l'archive en cours (avec éventuellement le numéro de l'étape en cours). Il n'est pas possible d'enregistrer dans les 4 archives de base, une archive auxiliaire étant créée pour cela, appelée "Nouvelle archive". Attention : 2 grilles différentes peuvent avoir le même nom; mais ce n'est pas recommandé.
Suppression d'une grille personnelle. Après suppression, c'est la dernière grille de la liste des grilles enregistrées dans l'archive qui apparaît à l'écran. Si la grille supprimée est la dernière de l'archive, cette archive est supprimée. Il n'est pas possible de supprimer des grilles des 4 archives de base.
Calcul automatique d'une grille utilisant toutes les méthodes de résolution disponibles, calcul à partir de l'étape en cours (souvent depuis le début, pour un calcul complet), avec affichage final de la liste des étapes et de la grille remplie (si solution sans hypothèse), avec indication si la grille est correcte.
Calcul automatique réduit d'une grille n'utilisant qu'une partie des méthodes de résolution disponibles, parmi les plus simples (nombre sélectionné dans l'écran des Filtres et Options)
Génération aléatoire d'une grille personnelle à l'utilisateur. Génération de grille, ex nihilo, de manière aléatoire, selon des caractéristiques définies dans l'écran des Filtres et Options.
Icône optionnelle visible en mode développement (à valider dans l'écran des filtres et options), pour pouvoir effectuer un test externe. Cette icône est visible si l'option correspondante est cochée dans l'écran des filtres et options. Attention de redémarrer l'application pour valider cette option si elle est cochée. Cette procédure est nécessaire pour toute modification du programme, pour un développeur souhaitant corriger le programme.
2ème ligne des 9 icônes du haut de l'écran :
Accès à la liste des méthodes de résolution disponibles dans ce programme, affichée sous le diagramme de la grille
Accès à la liste des méthodes de résolution disponibles dans ce programme permettant d'éviter des défauts d'unicité, affichée sous le diagramme de la grille
Accès à la liste des étapes de calcul (résolution manuelle ou résolution par le programme), affichée sous le diagramme de la grille
Accès à la liste des variantes de la méthode de résolution sélectionnée, affichée sous le diagramme de la grille
Accès à la liste des hypothèses nécessitées par des blocages, quand aucune méthode disponible n'est applicable, message affiché sous le diagramme de la grille
Accès à la liste des archives, affichée sous le diagramme de la grille
Accès à l'écran des filtres et options, affiché sous le diagramme de la grille
Sauvegarde des filtres de calcul et de génération, et des options, pour une utilisation ultérieure. Cette icône en forme de chapeau permet d'enregistrer la configuration en cours : archive, grille, tableau des Filtres et Options.
La liste des grilles n'est pas accessible par une icône, mais par la sélection d'une archive, dans la liste des archives, ce qui fait apparaître la liste des grilles de cette archive, puis par la sélection d'une grille dans cette archive.
Un calcul, complet ou réduit (en cliquant sur l'une des 2 icônes de calcul), n'est pas possible pendant la saisie d'une nouvelle grille. Il faut pour cela sélectionner auparavant la grille dans la liste des grilles.
Certaines méthodes, lorsqu'elles sont sélectionnées avec peu de cases restantes, en particulier les chaînes du Tigre (AIC-Chain, XY-Chain et ALS Chain), peuvent déterminer de très nombreuses variantes, parfois plusieurs centaines.
Attention : Lors du survol d'une icône, celle-ci se dilate et un message en jaune apparaît en haut et à gauche de l'écran, indiquant la signification de cette icône. Cliquer pour activer cette icône, quand ce message en jaune apparaît.
|
- La zone des messages
|
La zone des messages contient les messages afférents à l'opération en cours, parmi les opérations suivantes :
- Nom de la grille en cours (si sélection ou génération de grille)
- Etape en cours avec explications spécifique et générale de la méthode utilisée à cette étape
- Résultat d'un calcul, avec indication si la grille est correcte et affichage de la signature des hypothèses s'il y en a eu : H=hypothèse, E=hypothèse avortée (cas des hypothèses en cascade), U=Défaut d'unicité rectangle évité, V=Défaut d'unicité bug+1 évité
- Résultat d'une variante
- Affichage de la liste des méthodes applicables avec leurs nombres de variantes.
- Résultat d'une hypothèse
- Explication d'un archivage
- Les crashs pour impossibilité
- Les crashs pour défaut d'unicité et les méthodes pour les éviter
- Utilisation pour le débogage
|
- Les 7 listes (Méthodes, Méthodes unicité, Etapes, Variantes, Hypothèses, Archives, Grilles)
|
Ligne des icônes au-dessus de chacune des listes :
Navigation bas dans une liste
Navigation haut dans une liste
Affichage plein écran de la liste pour impression de cette liste
Icône supplémentaire de la liste des archives : produisant une réinitialisation générale des archives, revenant aux 4 archives de base et supprimant toutes les archives personnelles. Il faut, pour activer cette fonction avoir obtenu une autorisation préalable sélectionnée dans l'écran des filtres et options, qui a été validée en cliquant sur l'icône en forme de chapeau . Attention, danger : toutes les archives créées par l'utilisateur sont supprimées avec réinitialisation des seules 4 archives de base.
Icône supplémentaire de la liste des variantes : permettant de montrer la grille sans les chiffres éliminés en rouge, et après validation des solos isolés.
Sous la grille sudoku sont empilées, de manière superposée, les 7 listes et l'écran des "Filtres et Options". Un clic gauche sur une des 6 icônes de liste entraîne l'affichage correspondant. La liste Grilles, elle, ne peut être sélectionnée qu'en cliquant sur son nom dans l'archive qui la contient. Chaque élément d'une liste peut être ensuite sélectionné en cliquant directement dessus, ou en utilisant les 2 icônes de navigation.
Un clic gauche sur l'icône d'impression d'une liste entraîne l'affichage plein écran de cette liste avec, en haut de cet écran annexe 2 liens, l'un pour le retour à l'écran principal, l'autre pour imprimer cet écran annexe.
Sélection dans les 7 listes par clic gauche sur l'icône correspondante (6 listes :
) ou par clic sur son nom dans le contenu d'une archive (liste des grilles) :
- La sélection d'une grille, par clic sur son nom dans la liste des grilles d'une archive, entraîne l'affichage de son contenu dans le diagramme, son identification par l'affichage de son titre dans la zone de titre et dans la zone de messages et l'éclairage en blanc de son nom dans la liste affichée des grilles. Et la liste des étapes apparaît avec une seule étape dite 0 avec le mention "Grille initiale". L'enregistrement d'une grille ajoute une ligne de la liste dans l'archive contenant cette grille. Si la grille est sélectionnée à une étape de calcul par ordinateur, elle est sauvegardée en la copiant avec son nom auquel a été ajouté le numéro de l'étape correspondant.
- La sélection d'une méthode dans la liste suivante entraîne le calcul et l'affichage de toutes ses variantes applicables pour la grille en cours, à l'étape en cours. Si la méthode est non applicable, la liste des variantes n'apparaît pas, un message en indiquant la raison.
Il faut distinguer variante, qui est une des solutions obtenues avec la méthode sélectionnée, et variété, qui est en fait une sous-méthode de la méthode. Par exemple, la méthode "AIC-Chain" (ou approche du tigre) possède 4 variétés : AIC-Type I, AIC-Type II, AIC-loop discontinu et AIC-loop continu. Pour certaines méthodes, il existe même des combinaisons de variétés.
La sélection de la première ligne de liste des méthodes appelée "Toutes les méthodes applicables" entraîne le calcul de toutes les méthodes et l'affichage de celles qui sont applicables, avec leurs nombres de variantes, dans le message sous la grille, ainsi que la visualisation en rouge sur le diagramme, de tous les chiffres-candidats susceptibles d'être éliminés avec l'ensemble de ces méthodes applicables, avec toutes leurs variantes. La liste des variantes fait donc apparaître l'ensemble des variantes de toutes les méthodes applicables
Voici un exemple de la méthode dite "Toutes les méthodes applicables" :
Et le début de cette liste de variantes de toutes les méthodes applicables (18 sur 58) :
La sélection de la première ligne de liste des méthodes appelée "Toutes les méthodes unicité applicables" entraîne le calcul de toutes les méthodes unicité et l'affichage de celles qui sont applicables, avec leurs nombres de variantes, dans le message sous la grille, ainsi que la visualisation en rouge sur le diagramme, de tous les chiffres-candidats susceptibles d'être éliminés avec l'ensemble de ces méthodes unicité applicables, avec toutes leurs variantes. La liste des variantes fait donc apparaître l'ensemble des variantes de toutes les méthodes unicité applicables
Ceci entraîne l'affichage de la grille avec les chiffres éliminés en rouge, du fait de l'application de toutes ces méthodes applicables, dont la liste des méthodes avec leur nombre de variantes apparaît dans le message sous la grille, suivie de la liste détaillée complète des variantes.
Il est possible de faire disparaître ces chiffres rouges, en cliquant sur l'icône parmi les 4 icones en haut de la liste des variantes. Le programme élimine aussi tous les chiffres des cases vues par des solos isolés, apparus après élimination des chiffres rouges.
Voici un exemple de la méthode dite "Toutes les méthodes unicité applicables" :
Et la liste de variantes de toutes les méthodes unicité applicables :
La sélection d'une de ces méthodes ou de ces méthodes unicité entraîne l'affichage de la liste des variantes applicables de cette méthode, et l'affichage en rouge des chiffres éliminés par l'ensemble des méthodes applicables.
Il est possible ensuite de visualiser la grille sans ces chiffres rouges éliminés en cliquant sur l'icône en haut de la liste détaillée des variantes de cette méthode, ce qui élimine aussi les chiffres dans les cases voyant les solos isolés apparus.
En cliquant sur une des variantes dans cette liste, on obtient le résultat pour cette variante.
La sélection d'une étape affichée après un calcul, donne les indications suivantes : résultat sur la grille de la méthode utilisée lors de cette étape, avec affichage en rouge des chiffres candidats éliminés et les chiffres concernés par la ou les éliminations de chiffres candidats apparaissent sur fond vert. Dans la zone des messages se trouve l'explication de la méthode utilisée : explication spécifique du cas traité, et explication générale de la méthode.
Voici un exemple de la méthode "l'attaque du cobra" choisi à l'étape 13 de la solution de la grille dénommée "Al Escargot", dans l'archive "19 grilles de la littérature de sudoku".
Cette étape fait partie du début de la liste des étapes suivantes :
ATTENTION : il est donc possible de visualiser une des variantes de la liste obtenue en cliquant sur une méthode (ou même en cliquant sur la liste des variantes de toutes les méthodes). Mais ceci n'est pas possible s'il s'agit d'une sélection à une étape de calcul donnée, où seul l'ensemble des variantes peut être visualisé. Pour obtenir la visualisation d'une variante particulière de la liste des variantes d'une méthode, il faut au préalable enregistrer la grille à une étape de calcul particulière, puis cliquer sur la liste des méthodes de cette grille enregistrée.
En fait, il s'agit là d'un bug identifié et non résolu, dont il existe un palliatif qui consiste donc à enregistrer la grille à une étape de calcul donnée, avant de sélectionner une méthode efficace pour en visualiser toutes les variantes.
Dans la liste des hypothèses, un clic sur une hypothèse entraîne l'affichage de la liste des étapes de cette hypothèse et, dans la zone des messages, le résultat final de cette hypothèse, c'est-à-dire une solution, ou un crash pour impossibilté, ou un crash pour défaut d'unicité. Avec également, la correction appliquée à l'hypothèse précédente.
Dans la liste des archives, La sélection d'une archive entraîne l'affichage de la liste des grilles de cette archive et, dans la zone des messages, l'indication du chargement de cette archive. Le changement d'archive (par navigation ou clic gauche sur l'archive) enregistre automatiquement l'archive en cours avec ses modifications.
|
- L'écran des filtres et options
|
L'écran des "Filtres et options", auquel l'utilisateur accède en cliquant sur l'icône , en haut de l'écran, contient les éléments suivants :
- 3 filtres pour la génération de grilles : nombre de cases affectées, nombre maximum de cases par chiffre dans une même zone sudoku (ligne ou colonne ou bloc), nombre maximum d'échecs autorisés (il faut alors relancer la génération).
- 3 filtres pour le calcul d'une grille : nombre de méthodes du calcul réduit, longueur maximum des chaines de la méthode "Chaîne ALS-Chain" (obsolète),
nombre maximum d'itérations de la méthode "Chaîne ALS-Chain", case initiale de la méthode "Chaîne ALS-Chain" (aucune case initiale veut dire toutes les cases) (obsolète).
- 5 options de fonctionnement du programme
- Option d'activation du clavier virtuel : la saisie du titre de la grille ou de celui d'une nouvelle archive, peut se faire avec un clavier virtuel qui apparaît à l'écran quand on clique dans une des 2 zones de saisie (pour une utilisation sans clavier).
- Option d'autorisation de réinitialiser les archives, ce qui revient à revenir aux 4 archives de base. Cette option permet donc de remettre à zéro toutes les archives; elle doit être confirmée en cliquant sur l'icône de validation des Filtres et Options (icône en forme de chapeau). L'exécution de cette réinitialisation des archives est ensuite effectuée dans l'écran des archives, en cliquant sur l'icône de réinitialisation des archives .
- Option de travail en Mode développement. Si cette option est validée, il est possible de modifier le code source, grâce à une icône supplémentaire, pour démarrer un calcul sur une portion de code externe à tester. Cette icône est inhibées en mode production. Attention, La validation du mode développement, qui est effectuée en la validant puis en cliquant sur l'icône en forme de chapeau , n'est effective qu'en quittant le programme de sudoku puis en le rappelant.
- Option permettant le calcul de la grille sélectionnée, au moment de la sélection. Ceci permet d'activer l'assistance à la résolution manuelle, puisque la solution est connue. L'inconvénient est que le temps de calcul de cette grille lors de la sélection peut être très long, si elle est compliquée, ce qui ralentit le traitement de cette grille. Cela ne concerne que les grilles personnelles, et pas celles des archives de base, dont le résultat est déjà implanté.
- Option donnant le nombre maximum de chiffres-candidats pouvant être visualisés dans une case, avec clic gauche sur l'icône Bascule .
La configuration des 3 filtres de génération, des 3 filtres de calcul (dont 2 obsolètes), des 5 options (activation du clavier virtuel, autorisation de réinitialiser les archives, travail en mode de développement, calcul de grille lors de leur sélection, nombre de chiffres-candidats affichés),
est validée par un clic gauche sur l'icône de validation en haut de l'écran (icône en forme de chapeau), ce qui valide aussi la grille dans son archive. Une fois la configuration sélectionnée, il faut, pour l'activer, sortir du programme pour ensuite le recharger.
Selon les valeurs des filtres, le temps de génération ou de calcul est plus ou moins long, avec, en contrepartie, une plus ou moins bonne précision. Certaines méthodes utilisent des fonctions récursives (fonctions s'appelant elles-même), et une récursivité trop profonde peut générer une saturation de pile et un dépassement de temps.
Une fois la configuration effectuée, la valider en cliquant sur l'icône pour l'enregistrer, puis sortir du programme avant de le rappeler pour que cette configuration soit active.
|
- Le calcul de grilles de sudoku par ordinateur
|
Attention : toujours sélectionner la grille dans la liste des grilles avant de lancer un calcul de cette grille.
Un calcul par ordinateur est obtenu en cliquant sur l'une des 2 icônes de calcul (calcul complet et calcul réduit ). Le programme affiche alors le résultat, et permet de visualiser les étapes de calcul ayant permis d'aboutir à ce résultat, dans une liste des étapes sous le diagramme. Le programme indique aussi si la grille est correcte, à savoir qu'elle fournit une solution valide et une seule.
Au cours ou en fin de calcul, qu'il soit manuel ou par ordinateur, l'utilisateur peut revenir sur les différentes étapes de calcul précédentes, en cliquant d'abord sur l'icône sélectionnant la liste des étapes , puis en cliquant sur une de ces étapes, visualisant l'effet de l'opération à cette étape :
- Méthode utilisée à cette étape expliquée sous le diagramme, en 2 parties : explication spécifique de la manière dont la méthode est appliquée sur le diagramme, et explication générale indiquant le principe de la méthode utilisée. Ceci n'est pas intéressant pour un calcul en manuel puisqu'il s'agit alors uniquement de l'effet du choix d'un chiffre dans une case.
- Effet sur le diagramme de la méthode utilisée, à savoir l'indication en rouge des chiffres-candidats éliminés à cette étape, et l'affichage sur fond vert des chiffres concernés par l'élimination.
- Certaines cases restent vides et ne font pas apparaître leurs chiffres-candidats. Pour ce faire, il faut appuyer une première fois sur l'icône en haut de l'écran, ce qui ne fait apparaître sur le diagramme que les cases ayant un seul chiffre, puis, en appuyant une une seconde fois sur cette icône, ce qui fait réapparaitre tous les chiffres-candidats, y compris ceux en rouge qui sont éliminés. Mais les chiffres en vert concernés par la méthode de l'étape en cours, ne sont plus en vert.
Ceci permet à un utilisateur de comprendre, étape par étape, comment la grille a été résolue.
A partir de la grille initiale à l'étape 0, l'ordinateur calcule, en scrutant, à chaque étape, les méthodes, depuis la plus simple jusque la plus compliquée. Si une méthode donne un résultat, parce que efficace, elle est exécutée, avant de passer à l'étape suivante. Si aucune méthode n'est efficace, l'ordinateur fait alors une hypothèse aléatoire en imposant un des chiffres candidats à une case choisie aléatoirement. Il peut être nécessaire de faire des hypothèses en cascade, à chaque blocage dû à l'impossibilité de trouver une méthode efficace.
Le calcul se poursuit jusqu'à, soit une impossibilité, comme une case n'ayant plus de chiffre candidat (5 cas d'impossibilité ont été répertoriés dans le programme), soit une solution.
Si ce résultat (impossibilité ou solution) a nécessité de faire des hypothèses, il faut corriger la dernière hypothèse effectuée avant cela. Si une solution est trouvée, alors qu'une solution avait déjà été trouvée précédemment, le programme s'arrête car la grille est fausse par défaut d'unicité.
Le calcul continue jusque épuisement de toutes les hypothèses, après correction de toutes les hypothèses effectuées.
Dans ce cas, si une solution avait été trouvée précédemment, la grille est correcte avec une seule solution, sinon la grille est fausse car elle n'a pas de solution.
Le temps de calcul moyen des grilles les plus compliquées, nécessitant de faire des hypothèses, est de 5 minutes sur un simple ordinateur de bureau, et de 30 minutes sur un téléphone portable.
- L'application ponctuelle des méthodes de résolution
|
Une méthode de résolution efficace consiste, quand elle est appliquée à une grille de sudoku, à une étape de calcul donnée, à éliminer des chiffres candidats, qui apparaissent en rouge dans la grille. Mais il est possible qu'une autre méthode soit aussi applicable, ou même que la méthode en question puisse être appliquée d'une autre manière (variantes d'une méthode). Ceci montre qu'il existe plusieurs manières différentes de résoudre une grille.
L'ensemble des méthodes fonctionnent sur le principe suivant : à partir d'une hypothèse implicite, on utilise la méthode pour aboutir à une impossibilité, ce qui invalide l'hypothèse. Ceci permet d'éliminer les chiffres concernés par l'hypothèse.
Une autre notion importante est celle de lien fort : 2 cases sont reliées en lien fort sur un chiffre-candidat, si ce chiffre-candidat n'apparaît dans aucune autre case d'une zone sudoku commune à ces 2 cases. Il ne peut apparaître non plus dans aucune autre cases des autres zones sudoku communes à ces 2 cases. Cette notion peut être étendu au cas de plus de 2 cases : 3, 4, 5. Si un lien n'est pas fort, il est faible.
Pour tester si une méthode est efficace pour éliminer des chiffres-candidats, il faut cliquer sur l'icône sélectionnant la liste des méthodes , puis, dans la liste des méthodes qui apparaît, cliquer sur la méthode à tester. Si cette méthode est efficace, et même de différentes manières, une liste de ces différentes variantes apparaît. On peut alors sélectionner ces variantes, en navigant dans la liste de ces variantes, soit avec les icônes haut et bas, soit en cliquant directement sur la variante à visualiser.
Il existe donc, comme indiqué ci-dessus, une ligne particulièrement intéressante dans la liste des méthodes, la première ligne intitulée "Toutes les méthodes applicables". Quand on clique dessus, une liste de toutes les variantes de toutes les méthodes applicables apparaît : un message sous la grille répertorie toutes ces méthodes avec leurs nombres de variantes, précédant la liste de toutes ces variantes de toutes ces méthodes. Que l'on peut ensuite explorer. Et la grille contient tous les chiffres rouges (donc à éliminer) de toutes les variantes de toutes ces méthodes.
En voici un autre exemple :
Si aucune méthode n'est efficace, il faut se résoudre à faire une hypothèse, qui consiste à sélectionner aléatoirement un chiffre dans une case, en général une case à 2 chiffres candidats.
Si une hypothèse n'aboutit pas le calcul se terminant par une impossibilité, elle est corrigée. Une hypothèse fausse induit la suppression de toutes les hypothèses ultérieures dans le calcul.
Le niveau de difficulté des grilles avec hypothèses est donc très difficile voire diabolique et variable selon la quantité des hypothèses effectuées aléatoirement. Ainsi, la grille finlandaise "Al Escargot" nécessite en moyenne 12 modifications pour explorer toutes les possibilités et garantir qu'elle est correcte. Mais, en prenant des hypothèses judicieuses, elle peut être résolue en 2 hypothèses seulement. C'est ce qui arrive quand on choisit d'effectuer le calcul en 2 passes : la première en effectuant des hypothèses aléatoires, la deuxième en choisissant les hypothèses les plus judicieuses issues de ce premier calcul, à savoir le résultat d'une case ayant beaucoup de chiffres candidats.
La résolution d'une grille de sudoku consiste donc à éliminer, par étapes successives, dans les cases de la grille, les chiffres candidats démontrés comme faux par une des méthodes d'élimination existantes dans ce programme (il en existe d'autres, n'ayant pas été implantées). S'il n'y a pas de chiffre éliminé en rouge lors de l'application d'une méthode, c'est que cette méthode est inefficace, comme indiqué dans un message sous la grille.
Si une solution est trouvée sans hypothèse, elle est validée. Si au contraire, une solution est trouvée mais avec hypothèses, le calcul continue cependant, en modifiant la dernière hypothèse effectuée. Le calcul continue jusqu'à ce qu'il n'y ait plus d'hypothèse possible. Mais si entre temps, une deuxième solution est trouvée, prouvant que la solution n'est pas unique, c'est que la grille est fausse.
En fin de calcul une liste d'hypothèses est générée, et un message est affiché indiquant si la grille est correcte avec une solution unique (ni impossible, ni en défaut d'unicité). Dans la littérature du sudoku, une grille à solution unique est aussi appelée "puzzle bien formé".
|
- La création de grilles de sudoku (dans l'espace manuel)
|
Il existe 3 types de grilles dans ce programme :
- Des grilles disponibles dans le programme, chargées lors de la première utilisation, ou lors d'une réinitialisation générale. Ces grilles sont disponibles dans 4 archives, dites de base, avec les dénominations suivantes : 19 grilles de la littérature de sudoku, 73 grilles difficiles générées (73 grilles originales, créées avec la génération aléatoire de ce programme), 50 grilles faciles générées (50 grilles créées avec la génération aléatoire de ce programme), 9 grilles AIC extraites du numéro 11 de la revue Sudoku Grand Maître (étude approfondie de la méthode AIC-Chain, ou approche du tigre). Ces archives ne sont ni modifiables ni effaçables.
- Des grilles extérieures à saisir manuellement (processus de création de grille), en cliquant sur l'icône de création dans l'espace manuel. utilisant un puissant outil de saisie, permettant d'établir une grille en moins de 30 secondes.
- Des grilles générées aléatoirement par ce programme (processus de génération de grille vu au chapitre suivant), en cliquant sur l'icône de génération dans l'espace automatique .
L'utilisateur peut disposer de ces 2 derniers types de grilles dans des archives qui lui sont propres, dans lesquelles il peut aussi recopier des grilles des 4 archives de base.
Une grille est chargée si l'utilisateur clique sur son nom dans une liste de grilles d'une archive. Cette grille, une fois chargée, est disponible dans le diagramme, avec son nom en titre, et le nom de l'archive qui la contient.
Le mode création est généré quand on clique avec le bouton gauche de la souris sur l'icône de création de grille (dans l'espace manuel). Dans ce cas, une grille vierge apparaît avec le titre N. On renseigne ce titre du nom que l'on veut donner à cette nouvelle grille. Il faut aussi renseigner le nom de l'archive dans laquelle cette grille sera chargée. Par défaut, si l'archive est une des 4 archives de base, l'archive utilisée s'appellera "Nouvelle archive", en lieu et place de l'archive de base contenant la grille. Si cette archive existe déjà, la grille sera ajoutée à cette archive; sinon, l'archive est créée.
Pour créer cette nouvelle grille, vierge au départ, on la remplit en sélectionnant un chiffre du tableau interne qui apparaît dans une case quand la souris la survole. Ce tableau contient la liste des chiffres-candidats de cette case; au début, il s'agit de tous les chiffres de 1 à 9 puis, au fur et à mesure que la grille se remplit, le nombre de chiffres-candidats des cases sélectionnées diminue.
Si on s'est trompé lors d'une sélection, il faut sortir de la case en déplaçant la souris, pour ensuite y revenir, et double-cliquer avec le bouton gauche, pour dévalider ce chiffre et revenir ainsi à la situation précédente.
On peut aussi cliquer avec le bouton droit de la souris sur un chiffre du tableau interne d'une case, ce qui désélectionne ce seul chiffre : le tableau interne ne contiendra plus ce chiffre. Mais cette opération est peu intéressante pour créer une grille.
En fin de création de la grille, et à condition d'avoir renseigné au moins 17 cases, on sauvegarde cette grille en cliquant avec le bouton gauche de la souris sur l'icône de sauvegarde (qui existe dans les 2 espaces manuel et automatique), parmi les icônes principales en haut de l'écran à gauche. La grille apparaît alors à la fin de la liste des grilles de l'archive. Cela désactive le mode création.
|
- La génération de grilles de sudoku (dans l'espace automatique)
|
La procédure de génération de grille est la suivante :
- Cliquer sur l'icône de génération de grille en haut de l'écran . Ceci met en place de manière aléatoire des chiffres dans un nombre limité de cases de la grille. Ce nombre est initialisé dans l'écran des "Filtres et Options", ainsi que le nombre maximum de cases dans une même zone sudoku (afin de bien répartir les cases). A chaque case initialisée, le programme vérifie que cela n'engendre pas d'impossibilité immédiate, ce qui invalide cette affectation de case. A l'issue, de cette implantation de cases sans impossibilité immédiate, un calcul de cette première grille, dite brute de fonderie, est effectué afin de vérifier qu'elle ne génère pas d'impossibilité ni de défaut d'unicité. Après une attente normalement peu importante, une grille générée apparaît, avec, dans la zone des messages, une indication sur le nombre d'échecs dus à une impossibilité et le nombre d'échecs dus à un défaut d'unicité. La grille est en général correcte et l'indication "Grille générée" apparaît en titre. Si l'attente est prolongée (plus de 2 minutes), c'est que le programme a un grand nombre d'échecs (pour impossibilité ou défaut d'unicité). Si ce nombre d'échecs dépasse la limite autorisée (par défaut, 60), la grille générée qui apparaît est très probablement fausse et il faut relancer la génération de grille en cliquant sur l'icône correspondante. Cette opération est donc longue et peut provoquer un dépassement de temps système (dit "Time Out"); dans ce cas, laisser continuer le calcul jusqu'à son terme sans rien faire.
- Si la grille générée est correcte, renseigner le titre de la grille remplaçant le titre "Grille générée", dans la zone de titre, puis cliquer sur l'icône d'enregistrement en haut de l'écran (matérialisée par une forme de disquette)
- Cliquer sur l'archive de cette grille, dans la liste des archives
- Sélectionner cette nouvelle grille en cliquant sur son nom dans la liste des grilles
- Lancer un calcul pour vérifier cette grille, puis inspecter les étapes de calcul
En fin de génération de grille, un message sous le diagramme de la grille indique si la grille est correcte et combien d'échecs ont été subis lors de cette génération.
Il n'est pas possible de déterminer à priori si la grille qui va être générée sera facile, difficile, ou très difficile.
En moyenne, le programme génère 3 fois plus de grilles faciles que de grilles difficiles.
Et il faut en moyenne 20 échecs pour trouver une grille générée valide. Il faut être patient pendant la génération.
La grande majorité des échecs est due à une impossibilité, quelques cas étant dus à un défaut d'unicité.
Si le nombre d'échecs est trop important, il faut recommencer une génération de grille
Même si la grille finale est fausse, elle est enregistrée et peut être analysée. C'est une source très intéressante de cas d'études.
Par défaut, le nombre d'échecs est limité à 60 (même si ce chiffre peut être modifié dans l'écran des Filtres et Options).
Cette limite du nombre d'échecs est atteinte, en moyenne, une fois sur deux tentatives.
Voici 2 exemples de grille générées, l'une après 60 échecs, l'autre après 1 échec :
En résumé, la génération de grille se déroule en 5 étapes : générer, renommer, enregistrer, sélectionner et calculer.
|
- Les crashs pour impossibilité
|
Les situations d'impossibilité, générant un crash sont les suivantes :
- Aucun chiffre candidat dans une case (case vide)
- Doublon, le même chiffre affecté apparaîssant dans 2 cases différentes d'une même zone sudoku (ligne ou colonne ou bloc)
- Nombre de chiffres candidats dans des cases d'une même zone sudoku, inférieur au nombre de cases où ils se trouvent, comme par exemple 2 seuls chiffres dans 3 cases d'une même zone sudoku
- Chiffre manquant dans une zone sudoku
- 2 chiffres candidats dans une seule case d'une zone sudoku et pas dans les autres cases de cette zone
Voici 5 exemples de crash pour impossibilité, un pour doublon, un pour un chiffre absent dans une colonne, un pour 2 chiffres seuls dans une case, un pour 2 chiffres dans 3 cases, un pour 3 chiffres dans 4 cases:
|
- Les crashs pour défaut d'unicité et les méthodes pour les éviter
|
Deux situations de défaut d'unicité dans ce programme (il en existe d'autres) :
- Unicité appelée Bug+1, toutes les cases de la grille ne possèdant plus que un ou 2 chiffres candidats sans aucune méthode applicable (sauf pour une solution bien sûr, où toutes les cases n'ont plus qu'un seul chiffre candidat)
- Unicité appelée rectangle où les mêmes 2 chiffres apparaissent aux sommets d'un rectangle, dans 2 blocs qui se voient.
Voici 3 exemples de crash pour défaut d'unicité, 2 pour un défaut d'unicité rectangle, le dernier pour un défaut d'unicité bug+1 (pas de case à plus de 2 chiffres-candidats) :
Des techniques existent pour éviter ces 2 défauts d'unicité. Mais un défaut d'unicité évité doit conduire à une solution, sinon la grille est fausse. Même dans ce cas, il faut vérifier que le contraire de l'évitement ne conduit pas à une solution parasite, auquel cas la grille est encore fausse. C'est le cas de la grille Pétunia, qui est fausse pour défaut d'unicité.
De très nombreuses méthodes sont répertoriées sur internet, pour éviter un défaut d'unicité.
9 d'entre elles sont implantées dans ce programme de sudoku :
- Unicité bug+1 Une seule case à 3 chiffres candidats, toutes les autres ayant un ou deux chiffres-candidats : éliminer le chiffre de cette case étant vu plusieurs fois (évitement crash unicité dit bug+1).
- Unicité solo Dans 4 cases d'un rectangle dans 2 blocs, où 3 cases ont les mêmes 2 chiffres, la 4ème case ne peut contenir ces 2 chiffres (évitement crash unicité rectangle).
- Unicité5 dans rectangle Dans 4 cases d'un rectangle dans 2 blocs, contenant 2 chiffres de base, supprimer le chiffre de 2 cases opposées, reliées en lien fort avec les 2 autres cases (évitement crash unicité rectangle).
- Unicité duo 2 dans rectangle
- Unicité trio 3 forme 1 dans rectangle
- Unicité trio 3 forme 2 dans rectangle
- Unicité 4 dans rectangle
- Unicité duo
- Unicité LT
Cette importante richesse de méthodes est source de nombreux résultats spectaculaires permettant de casser une grille très difficile. C'est aussi une source d'erreurs de programmation.
En cas de plantage dû à une méthode défaillante, le calcul ne se termine pas normalement, et le message sybillin suivant apparaît :
Lancement du calcul automatique complet. Dans ce cas, il faut resélectionner la grille et relancer le calcul.
Voici 5 exemples de défaut d'unicité évités :
Malgré cela, il existe des cas où l'évitement doit êre corroboré, c'est-à-dire que l'un des chiffres d'une case du rectangle ne doit pas rendre une autre case du rectangle assujettie à un des 2 chiffres du rectangle :
Cette question de la corroboration d'un évitement de défaut d'unicité est méconnue. Il existe quelques exemples de grilles publiées dans les journaux, qui se révèlent fausses pour défaut d'unicité, du fait de la non prise en compte de ce fait. La solution de ces grilles contient ainsi des rectangles complets à 2 chiffres, sans que cela ne soit reconnu.
Il est prévu une implantation progressive de nouvelles méthodes évitant le défaut d'unicité. Il en existerait plus de 20, ce qui constitue une mine de résolution de grilles de sudoku.
|
- Le clavier virtuel
|
Un clavier virtuel a été implanté dans le programme. Il est activé en cochant l'option "Activation du clavier virtuel" dans l'écran des Filtres et Options. Attention, il faut, après l'enregistrement de l'écran des filtres et options en cliquant sur l'icône , sortir du programme puis le recharger, pour que l'option soit validée. Ce clavier virtuel n'apparaît pleinement qu'en mode plein écran.
Quand on clique dans une des 2 zones de titre (titre de la grille ou de la nouvelle archive), un clavier virtuel apparaît à l'écran et on peut renseigner ces titres en cliquant sur des caractères de ce clavier virtuel.
Ce clavier est beaucoup plus riche qu'un clavier physique. Non seulement, on peut activer le mode majuscule en cliquant sur CapsLock, mais on peut choisir des caractères grecs, des notes de musique, des caractères informatiques, des caractères de business, émoticons, motifs de cartes à jouer, etc... Cette liste pourrait être enrichie par d'autres caractères de différents pays : Chinois, Indien, Japonais, Arabe, Hébreu, etc...
En fin de saisie, il faut fermer la fenêtre du clavier virtuel en cliquant sur le ruban rouge intitulé "Exit clavier virtuel" en haut de cette fenêtre.
Ce clavier virtuel permet donc la saisie des caractères du nom d'une grille ou du nom d'une archive, avec des caractères exotiques, ce qui ne peut être le cas avec un clavier physique. Les noms ainsi créés sont donc identifiables de manière originale.
|
- Utilisation des différents navigateurs
|
Ce programme de résolution de grilles Sudoku fonctionne correctement avec les 2 navigateurs suivants : Firefox (Mozilla), Chrome (Google).
Il fonctionne aussi avec les 2 navigateurs suivants : Opera (Norvégien) et Safari (Apple).
Il fonctionne même avec les 2 navigateurs Microsoft : Internet Explorer 11 et Edge. Ces 2 navigateurs supportent maintenant le Web Storage, qui est le nouveau moyen de stockage de données côté client, remplaçant les cookies de manière plus performante. Mais Internet Explorer 11 n'est plus supporté et remplacé par Edge.
Les cookies ne sont plus acceptés par les navigateurs Chrome et Opera. De même que les cadres ("frames") sont considérés comme obsolètes par la plupart des navigateurs.
En conséquence, les cookies et les cadres ("frames") ne sont pas utilisés par ce programme de sudoku, bien qu'acceptés avec restrictions par les 2 navigateurs de Microsoft.
|
- Limitations de l'utilisation de l'imprimante en couleur
|
Il existe 2 limitations pour l'utilisation en couleur d'une imprimante :
- Les fonds d'écran en couleur à imprimer sont difficilement accessibles par les navigateurs, afin d'épargner les cartouches des imprimantes. Seuls, les navigateurs Chrome et Edge acceptent d'imprimer les fonds d'écran.
- L'utilisation même de la couleur pour l'impression est également limitée.
|
- Messages d'erreurs
|
Les dysfonctionnements identifiés et corrigés sont indiqués par un message sous la grille commençant par l'alerte Attention. Leur liste, incomplète, est la suivante :
- calcul impossible car déjà effectué ou crash en cours ou solution immédiate en cours. Pas de calcul sur une solution de grille
- calcul impossible car il faut un minimum de 17 cases initialisées
- calcul interdit en cours de saisie de nouvelle grille : sauvegarder la grille avant de la calculer
- calcul trop long. Butée si le nombre d'hypothèses de calcul est trop élevé
- double clic gauche intempestif. Clic gauche trop long sur une icône, déclenchant une répétition intempestive de l'action
- impossible d'effacer des grilles dans une des 4 archives de bsae. Tentative interdite d'effacement d'une grille dans une des 4 archives de base
- impossible de sélectionner un chiffre éliminé par l'opération manuelle précédente
- la case ne contenant plus que 2 chiffres, sélectionner un chiffre au lieu d'invalider l'autre
- méthode dont les variantes ne sont pas activées. Pour sélectionner une variante particulière d'une méthode, il faut avoir sélectionné auparavant cette méthode, et qu'elle ait donné des résultats
- pas d'annulation action manuelle s'il s'agit de la grille initiale
- pas d'hypothèse à corriger sur étape initiale
- pas de retour possible aux 4 archives de base (éliminant toutes les autres archives); cocher la case des options correspondante pour activer cette fonction
- pas de validation de variante si une variante n'est pas sélectionnée
- pas de variante. Il n'existe pas de variante de la méthode sélectionnée
- Cas d'interdiction de calcul intempestifs. Il est nécessaire de recharger la grille en cours pour pouvoir exécuter un calcul
- Grille générée fausse pour défaut d'unicité, soit pour une deuxième solution, soit pour un défaut bug+1 direct. Il est possible de modifier cette grille pour la rendre soluble, en renseignant de nouvelles cases, en particulier celles qui sont concernées par un défaut d'unicité
- impossible d'éliminer un chiffre déjà éliminé par l'opération manuelle précédente
- impossible de sélectionner un chiffre éliminé par l'opération manuelle précédente
- Calcul interdit après un calcul; sélectionner la grille à calculer au préalable
- Calcul interdit après la sélection d'une méthode; sélectionner la grille à calculer au préalable
- Calcul interdit après la génération d'une grille; sélectionner la grille à calculer au préalable
Cette liste des messages est non exhaustive, et sera augmentée, en fonction des erreurs qui ne manqueront pas d'apparaître lors d'une utilisation intensive de ce programme de sudoku.
La chasse aux erreurs de programmation informatiques (bugs), est une fonction nécessaire pour des programmes lourds comme celui-là.
Un outil de développement existe dans ce programme pour faciliter cette recherche : à condition de cocher l'option dans l'écran des filtres et options, une icône supplémentaire est ajoutée aux icônes principales pour tester des bouts de code externes.
|
- Bugs occasionnels identifiés et non résolus avec recherche de palliatifs
|
Si une erreur est constatée et non corrigée, il faut se résoudre à utiliser un palliatif.
3 bugs occasionnels ont été constatés, sans qu'un solution ou une correction n'ait été encors trouvée :
- Après l'exécution d'un calcul d'une grille par ordinateur, il est parfois constaté que la première étape de calcul fait appel à une hypothèse, alors qu'il existe au moins une méthodes applicable. Dans ce cas, le palliatif consiste à resélectionner cette grille et à relancer le calcul.
- Si on sélectionne toutes les variantes d'une grille (pour une méthode donnée, ou pour toutes les méthodes applicables), puis si on sélectionne ensuite une variante particulière de cette liste, le retour à toutes les variantes se fait mal. Comme palliatif, il faut resélectionner l'icône de l'ensemble des variantes en haut de l'écran, avant de sélectionner une méthode particulière.
- Sur téléphone portable, l'appui sur une case de la grille est parfois défectueux car, au lieu de faire apparaître le tableau interne de la case, rien ne se passe. Le palliatif consiste alors à appuyer sur une autre case, avant de réappuyer sur la case en question.
Il existe certainement d'autres bugs, à identifier et, soit à corriger, soit à en trouver un palliatif.
2 cas incertains ont été constatés :
- Si l'application d'une méthode fait apparaître une solution erronée, une correction est nécessaire. C'est le cas de certaines méthodes pour éviter des défauts d'unicité. Le palliatif est de considérer que la grille générant ce type d'erreur est fausse !
- Si un plantage occasionnel intervient et qu'il persiste, le palliatif consiste alors à réinitialiser le programme en ne conservant que les 4 archives de base (cf ci-dessus). Pour l'instant, il n'existe plus de plantage connu, tous ceux étant apparus ayant été corrigés. Mais cela ne veut pas dire qu'il n'en apparaîtra pas; dans ce cas, il faut donc réinitialiser en revenant aux 4 archives de base.
Il est fait appel à la sagacité de développeurs, qui ont accès au code source (programme en open source), pour résoudre ces bugs.
La difficulté est que ces bugs n'apparaissent souvent que de manière occasionnelle et aléatoire.
Pour résoudre ces bugs, il faut donc avoir conservé une trace de la grille qui a occasionné un de ces bugs, pour relancer la procédure qui a occasionné ce bug, afin de le reproduire, pour essayer de la résoudre.
Il s'agit là d'un vaste domaine d'étude, très fécond : celui des bugs identifiés non résolus, dont il faut trouver un palliatif.
La résolution d'un dysfonctionnement, ou bug, s'effectue en 3 étapes :
- Apparition d'un dysfonctionnement
- Identification de l'origine de ce dysfonctionnement par encadrements successifs d'écritures autour de cette origine, pour la localiser
- Correction de ce dysfonctionnement
Avantage du palliatif : S'il est facile à réaliser, cela évite de se casser la tête pour résoudre le bug !
La chasse aux bugs des méthodes de résolution, pour impossibilité ou défaut d'unicité
Une manière d'identifier des bugs de méthodes de résolution, est de résoudre une grille, puis, connaissant ce résultat, de lancer un calcul de toutes les méthodes applicables, que ce soit sur la grille de départ, ou même sur la grille à une étape de son calcul.
Si, parmi les chiffres rouges apparaissant à l'issue de ce calcul de toutes les méthodes applicables, il en est qui font partie de la solution, c'est qu'il y a un bug sur une de ces méthodes.
Il faut alors balayer l'ensemble des méthodes de la liste, pour identifier celle ayant engendré ce bug. Il ne reste plus alors qu'à résoudre ce bug sur un cas concret.
C'est ainsi qu'un bug de la méthode Squirmbag a été identifié sur la grille Erable, et a pu être résolu : le chiffre rouge d'une case était erroné, parmi les 5 lignes du Squirmbag, car, en le sélectionnant, il ne reste plus que 4 colonnes qui constituent un groupe fermé, donc correct ! Donc, pas d'erreur; la méthode Squirmbag n'est pas applicable dans ce cas concret.
Une résolution avec contraintes a été implantée, mais sa résolution complète n'étant pas terminée, cette partie de programme a été suspendue pour l'instant.
De plus, au fur et à mesure de la mise au point de ce logiciel de sudoku, de nombreuses erreurs sont apparues et ont été corrigées. Mais le nettoyage de ces erreurs devenues obsolètes est à faire, ainsi que, aussi, le nettoyage du code, pour le rendre DRY (Don't Repeat Yourself).
Enfin, les images de ce programme d'Aide ont évolué, et certaines sont à actualiser, la présentation ayant évolué. Là aussi, un gros travail de nettoyage reste à faire.
Car ce programme de sudoku sur internet comporte environ 25000 lignes de code, et a nécessité 10 ans de travaux. Sa structure est maintenant opérationnelle, et peut servir de modèle pour la réalisation d'applications sur internet, ce qui constitue un vaste domaine.
|
- Liste des méthodes implantées dans ce programme de sudoku avec exemples
|
La liste numérotée des méthodes implantées est la suivante :
- 34- Toutes les méthodes applicables
- 1- Singleton nu (case à un seul chiffre)
- 2- Solo
- 3- Jumeaux
- 4- Duo ou Trio
- 5- Triples
- 6- Quadruples
- 7- Jumeaux Isolés
- 8- Triples isolés
- 9- Gratte-ciel
- 10- Boucle
- 11- Turbot fish
- 12- Sue de Coq (L'arme et la soie)
- 13- W-Wing (L'aile de l'aigle)
- 14- Rectangle vide
- 15- 2-String Kite (Cerf-volant)
- 16- L'attaque du cobra
- 17- X-Chain (Color trap)
- 18- XY-Wing (L'aigle et sa proie)
- 19- Swordfish (l'espadon)
- 20- Forteresse maxilien
- 21- X-wing et Finned X-wing
- 22- XY-Chain (La griffe du tigre)
- 23- A.I.C.-Chain (l'approche du tigre)
- 24- Death Blossom
- 25- ALS-XY-Wing
- 26- Jellyfish
- 27- Squirmbag
- 28- 3D Medusa
- 29- Nishio
- 30- Y-Wing
- 31- Chaînage ALS
- 32- Crash unicité
- 0- Crash impossibilité
Dans cette liste, les rubriques 0, 31, 32, 33 et 34 sont particulières :
- La rubrique 0 concerne les crashs pour impossibilité, au nombre de 5
- La rubrique 31 concerne une méthode lourde, le chaînage ALS, qui est parfois très longue. Il est alors nécessaire de réduire son utilisation en diminuant le nombre de calculs de cette méthode dans l'écran des filtres et options.
- La rubrique 32 concerne les méthodes permettant d'éviter un crash pour défaut d'unicité. Il en existe 8 dans ce programme de sudoku. De nombreuses autres méthodes d'évitement de crash unicité seront implantées ultérieurement.
- La rubrique 33 concerne les crashs pour défaut d'unicité, au nombre de 2 : bug + 1, rectangle.
- La rubrique 34, en première ligne, ne fait pas partie des méthodes. Elle permet, en la sélectionnant, de calculer, pour la grille en cours, l'ensemble des méthodes applicables, c'est-à-dire permettant la suppression de chiffres candidats, avec leurs nombre de variantes. Ceci est indiqué dans la liste des messages sous la grille.
Des exemples sont présentés ci--après, dans une liste non exhaustive, certaines méthodes présentant un grand nombre de variétés, comme les chaînes du tigre, le chaînage ALS ou les chaînes 3D Medusa.
Grille fausse
Voici un exemple en 7 phases illustrant l'emploi du programme :
Exemple de grille avec tableau interne de la case A1 survolée par la souris
Puis même grille après clic gauche sur le chiffre 7 de ce tableau interne
Puis même grille avec tableau interne de la case B2 survolée par la souris
Puis même grille après clic droit sur le chiffre 3 de ce tableau interne
Puis même grille avec tableau interne de la case D7 survolée par la souris
Puis même grille après clic gauche sur le chiffre 4 de ce tableau interne
Puis même grille après clic gauche sur le chiffre 1 du tableau interne de la case B1 (pas d'affichage de ce tableau interne)
Exemple de grille rendue erronée par la dernière opération manuelle avec la case C4 devenue vide
Exemple de grille initiale
Exemple de cette grille à une étape intermédiaire
Exemple de cette grille avec sa solution finale
| | |
|