Engineer's Book

————— PHYSICS – SPACE – ALGORITHMICS ——-

Algorithmique 01 – Complexité – Comment Résoudre un Sudoku ?

Written By: Jean-Paul Cipria - Jan• 02•17
Sodoku - Résolution par carré 3x3 ou Swordfish

Sudoku – Résolution par Rectangle 3×3 ou Swordfish ? Mince ! Il ne fonctionne pas ! (Croix rouges à la fois sur colonne et ligne !)

Comment résoudre un Sudoku ?
Quelquefois nous n’arrivons pas à résoudre de façon « logique » une partie de Sudoku. Est-ce dû à notre inexpérience ou le logiciel de jeu nous a t-il présenté une partie avec obligation de choix arbitraire ?


.

.
Created :2017-01-02 21:33:24. – Modified : 2017-05-15 10:36:02.


Expériences En Construction

Expériences En Construction



.

Pourquoi trouver l’algorithme Sudoku ?

Pourquoi nous bloquons quelquefois ?

Je me trouve la plupart du temps à résoudre un sudoku extrême sur une application Android [GENINA-2017] entre 3 et 5 minutes après avoir pointé les possibilités. Quelquefois les regroupements permettant de trouver une solution par élimination successive ne fonctionnent plus. Le jeu se trouve dans une position où il faut faire un choix arbitraire d’une valeur et dérouler les possibilités pour constater si cela fonctionne ou pas. Ce qui n’est pas de jeu ! Il m’intéresse donc de faire vérifier par algorithme programmé s’il y a une solution déductive ou si le jeu est bloqué. Il faut alors employer la « brute force ». Ce qui fonctionne aussi. Mais je le redis, ce n’est pas de jeu. Na !

Attitudes de physicien ou de comptable (manager) ?

En tant que physicien notre « câblage mental » est particulier. Nous exerçons avec excellence dans la difficulté des problèmes et nous errons avec médiocrité dans la complexité des choses. Ainsi nous sommes d’excellents « résolveur » de problèmes et de médiocres comptables. Observez que la plupart de informaticiens recrutés par des … psychologues sont des … chimistes plus accro de la complexité que de la difficulté. C’est une idée toute faite des recruteurs sur la fonction d’un informaticien. Il doit gérer d’où découle un grand nombre de problèmes non résolus. En entreprise quand on ne sait pas , on ne fait pas. Dont acte ! En France on ne fait pas et quand on fait  c’est bien organisé mais non fonctionnel. Mais tout le monde est content ? Cela ne fonctionne pas mais c’est bien versionné !

Résoudre les problèmes (physicien) ou gérer la pénurie (comptable) ?

En tant qu’exercice abordons donc un problème complexe pour aller dans le sens des béotiens. Ce n’est pas de la physique quantique mais il faut bien s’organiser dans les matrices et ne pas se mélanger les pinceaux entre lignes, colonnes, valeurs et tableaux de valeurs et tables en forme de bitmaps … la galère du physicien, le bonheur du manager !

Sodoku - Doublons et Manques

Sudoku – Doublons et Manques – Gestion Matricielle et par BitMap.

Stratégie de résolution de l’algorithme ?

Dans une première partie il faut être sûr de maîtriser l’ensemble des règles. Comme pour le stratège Sun Tzu [TZU-500 b.J.C.] , il faut s’assurer de ne pas perdre avant de penser à gagner quoi que ce soit. Cela semble frileux ? Mais oui, les stratèges sont patients. Et, à quoi bon essayer si on est  … mort ! Donc « Le premier pas de la stratégie est celui-ci : Mieux vaut ne pas mourir avant d’avoir gagné. » C’est ainsi que nous traduisons Sun Tzu. Mais ce n’est qu’un jeu.

Le premier pas de la stratégie est celui-ci : Mieux vaut ne pas mourir avant d’avoir gagné.
Jean-Paul Cipria

Comment trouver une solution construite ?

Vérifier la solution fournie ?

Vérification des lignes et des colonnes

Dans le sudoku il faut tout faire … à l’envers. De la même façon nous partons sur ce problème par une solution et nous trouvons les algorithmes qui nous permettent de vérifier s’il n’y a pas d’erreur. Dans l’exemple fourni les lignes et les colonnes « matchent » aux règles sauf … pour les carrés 3*3. On s’en fiche un premier temps. Nous déroulons la vérification sur les lignes et sur les colonnes. Dans l’exemple nous avons insérés des « erreurs ». Le programme les pointent et les comptent.

Avant de savoir « algorithmer » il faut déjà savoir ne pas se tromper. Et si cela arrive … s’en apercevoir et … corriger. Trois petits points …

Tables de vérification

Sodoku - Doublons et Manques

Sudoku – Doublons et Manques de valeurs par BitMap et Comptage Simple.

Réponses Matlab

Réponse Matlab

Fin de réponse Matlab

Vérification des carrés 3×3

La table A2 est remplie entièrement. Les positions 1 à 9 représentent un BITMAP de la valeur chiffrée contenue dans la case : par exemple nous déplaçons le bit à droite pour incrémenter une valeur.

% un  =[1 0 0 0 0 0 0 0 0];
% deux=[0 1 0 0 0 0 0 0 0];

Ainsi nous pouvons faire un OU logique de toute une ligne par (un | deux | trois … etc) qui devra donner en final : (1 1 1 1 1 1 1 1 1) soit une suite de neuf. L’endroit où il y a un zéro représente une valeur manquante. De la même méthode nous pouvons déterminer les valeurs en doublons en triple .. etc.

Début Programme Matlab : exemple du bloc carré (1:3 , 1:3)

Fin Programme Matlab

Comment construire une table correcte ?

Algorithme Possible ?

Cet algorithme s'assure qu'il n'existe pas d'impossibilité et choisi parmi les possibles mais ...
Pour tous les blocs de 1 à 9.
.. Colonne par Colonne du Bloc courant et Ligne par Ligne :
.... Faire la liste des valeurs possibles sur la ligne,  colonne et bloc courant.
.... Tirer au hasard dans cette liste des possibles.

Cet algorithme fonctionne pas !

Exemple de non solution

L’algorithme fonctionne comme prévu mais ne trouve pas de solution
Matlab début

Fonction : Construction d'un Sudoku juste par tirage aléatoire.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Erreur : Il n'y a plus de valeurs disponibles !
Bloc : 5 - Ligne : 6 - Colonne : 6

3     1     5     4     2     8     0     0     0
2     4     9     7     1     6     0     0     0
7     6     8     5     9     3     0     0     0
9     7     3     8     6     5     0     0     0
5     8     4     1     7     9     0     0     0
6     2     1     3     4     0     0     0     0
1     5     6     0     0     0     0     0     0
4     9     2     0     0     0     0     0     0
8     3     7     0     0     0     0     0     0

Matlab fin
La construction par vérification successive d’une liste des possibles ligne, colonne et bloc tombe pratiquement sur une impossibilité à un degré n de progression de l’algorithme. Pourquoi ? Parce que il peut y avoir 21 possibilités lorsque nous sommes sur une case. S’il n’y a pas assez de redondance, les 9 chiffres vont se présenter de manière unique en dehors de la case sans répétitions ligne ou colonne ou bloc et élimine ainsi la possibilité d’une valeur possible sur la case !

Comment détecter les possibles et impossibles ?

Un stratégie de jeu possible ?

Le jeu est de type « COMPLEXE » et non pas « difficile ». C’est à dire que la stratégie va consister à ? Décomplexifier ou simplifier. Ce qui semble banal, trivial comme disent ceux qui nous prennent pour des abrutis, et qui ne l’est pas, du tout !

Nous avons la position de toutes les solutions partielles. Il faut « calculer » les positions de toutes les possibilités. Il apparait souvent alors des valeurs uniques. La simplification optimum consiste à fixer d’abord la position de toutes les solutions uniques. Ce qui décomplexifie de manière optimum le jeu. Il faut donc faire un « tour » de 1 à 9 pour les béotiens ou de ce que nous voyons au premier abord puis par cercles concentriques ou extension ligne-colonne-carré pour ceux qui ont une vue de faucon. 😉 Faucon le fasse en premier. C’est l’optimum au sens du critère « simplification de complexité » qui le susurre. Mais vous faites comme vous voulez ?

Références

Applications Android

  • [GENINA-2017] : Application Android Sudoku du site Genina :
    http://www.genina.com
    Nous jouons sur ce logiciel qui fonctionne pas trop mal mais la pub en plein écran si nous laissons le Wifi actif.
    .

Stratégie

.

.
Jean-Paul Cipria
12/01/2017

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Anti-Spam Quiz: