Sudoku

[sebhoa]

Bonjour,

Je me permets d'ouvrir une nouvelle discussion, histoire de séparer les sujets. La discussion générale est bien dense et je me dis qu'en séparant les divers sujets (power4, sudoku, etc.) ce sera plus facile de s'y retrouver.

J'ai déposé mon code à propos du sudoku. Il y a beaucoup de lignes de codes, c'est loin très loin d'être satisfaisant en terme de bonnes pratiques et même de conception... mais je ne vais pas trop continuer à le triturer (faut aussi faire des choses importantes ;-) ). Je le mets donc à dispo si certains veulent le récupérer et jouer un peu avec.

Ma conclusion : les techniques humaines sont nombreuses, mais il y aura toujours des grilles pour y résister. Au final le plus efficace semble être de travailler avec des chaines de caractères et faire du backtrack associé à de la propagation de contraintes (voir l'article Solving Every Sudoku Puzzle par Peter Norvig.

@sebhoa
Bonjour , j'ai parcouru votre lien , c'est amusant de voir comme tout le monde tourne autour des mêmes concepts.
Pour ce qui concerne la propagation des contraintes , j'avais aussi par le passé des codes où je regardais tous les uniques ou cachés et allait jusqu'au bout de la logique d'élimination en surveillant à chaque tour que je faisais bien bouger la grille,, mais il fallait terminer de temps en temps par l'exploration de choix.
Bien évidemment l'auteur préconise de commencer par les choix à plus faible nombre de valeurs.
Donc même si je ne vois pas au global de concept révolutionnaire , je retiens effectivement la simplification d'utiliser des chaines pour tester des valeurs plutôt que des for , l’implémentation par groupes comme vous le faites déjà qui permet de simplifier les calculs . Pour les dictionnaires de possibles et l'utilisation de copies de grilles pour tester les choix, j'avais déjà essayé.
Je pense que la différence de temps de performance doit venir effectivement de la combinaison de tous ces concepts qui font gagner du temps au prix d'une actualisation permanente des dictionnaires un peu comme une gestion rigoureuse des candidats à la main :-)
Comme vous, je ne pense pas insister plus sur ce sujet , j'ai été très content d'arriver à implémenter assez simplement des classes et de la récursivité qui finissent par compléter la grille.
Je pense que c'est un défi interessant et pas hors de portée pour des gens qui veulent appréhender ces concepts avec un jeu simple dans ses régles et assez fun.
Je trouve la programmation des jeux à 2 un peu plus complexe de part les stratégies tenant compte des réactions de l'autre à integrer et au final je me dis que tous les codes de ces jeux ne sont que l'informatisation des heures qu'on a déjà passé sur le jeu réel , donc le niveau du code doit qd meme bien dependre de l'expertise du codeur dans le jeu réel.
Je termine pas un constat , c'est bien aussi de temps en temps d'essayer de résoudre un sudoku pas trop facile avec un crayon et une gomme et sans ecrire les candidats , ca reveille les neurones ....

@sebhoa
Mon code de récursivité

def sudoku (i1,j1):
    '''
    main code, using recursivity to calculate the grid
    at each turn, if the case can be filled with a value ,
    the case with minimum choices is choosed
    else , it tries to propose another value , if impossible return false value
    '''    
    if grille_pleine():return                  
    if case_choices(i1,j1)  :
        grida[i1,j1] = case_choices(i1,j1) [0]
        if not sudoku(*case_min()) : return sudoku( i1,j1)        
    grida[i1,j1] = 0
    return False

[sebhoa]

@JiPiBi J'avoue ne pas comprendre comment ce code peut fonctionner car 1. pour moi return <=> return None donc if not sudoku(*..) sera toujours vrai non ? 2. si jamais on passe effectivement pas return False... donc on remet i1, j1 comme case vide mais comment vous testez les autres candidats ? pour moi il manque une boucle for sur les candidats de i1, j1 qqc comme : for e in case_choices(i1,j1): grida[i1,j1] = e Le jeu. 8 nov. 2018 à 15:46, JiPiBi <notifications@github.com> a écrit :

…

@sebhoa <https://github.com/sebhoa> Mon code de récursivité def sudoku (i1,j1): ''' main code, using recursivity to calculate the grid at each turn, if the case can be filled with a value , the case with minimum choices is choosed else , it tries to propose another value , if impossible return false value ''' if grille_pleine():return if case_choices(i1,j1) : grida[i1,j1] = case_choices(i1,j1) [0] if not sudoku(*case_min()) : return sudoku( i1,j1) grida[i1,j1] = 0 return False — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJl3G-nj4pHDcbCtk-eoIwoaCVbhg8wTks5utBmsgaJpZM4YRwbg> .

[sebhoa]

Ah oui ca y est : en fait vos appels sudoku retournent tous False (enfin None et False) mais qd la grille est pleine ben elle est pleine et donc tous les appels récursifs se terminent... ok je vois. Et sinon vous appelez 2 fois finalement votre case_choices... on peut gagner du temps là non ? Le jeu. 8 nov. 2018 à 16:44, JiPiBi <notifications@github.com> a écrit :

…

Et pourtant il tourne.. Qd je fais if not sudoku(case suivante), il lance d abord la fonction sudoku et regarde sa réponse sur les cases en aval et la seule reponse qui est en fait retournée est False si blocage sinon on va au bout . Je ne renvoies jamais True, je continue à explorer les autres cases tant que ça ne bloque pas. Pour relancer ma fonction dans la meme case , je ne garde que les candidats de valeur supérieure à la valeur actuelle de la case : je ne tourne donc pas en rond.. Tout est dans la fonction case choices Envoyé depuis mon smartphone Samsung Galaxy. -------- Message d'origine -------- De : Sébastien Hoarau ***@***.***> Date : 08/11/2018 13:07 (GMT+01:00) À : flotpython/recreation ***@***.***> Cc : JiPiBi ***@***.***>, Mention ***@***.***> Objet : Re: [flotpython/recreation] Sudoku (#6) @JiPiBi J'avoue ne pas comprendre comment ce code peut fonctionner car 1. pour moi return <=> return None donc if not sudoku(*..) sera toujours vrai non ? 2. si jamais on passe effectivement pas return False... donc on remet i1, j1 comme case vide mais comment vous testez les autres candidats ? pour moi il manque une boucle for sur les candidats de i1, j1 qqc comme : for e in case_choices(i1,j1): grida[i1,j1] = e Le jeu. 8 nov. 2018 à 15:46, JiPiBi ***@***.***> a écrit : > @sebhoa <https://github.com/sebhoa> > Mon code de récursivité > > def sudoku (i1,j1): > ''' > main code, using recursivity to calculate the grid > at each turn, if the case can be filled with a value , > the case with minimum choices is choosed > else , it tries to propose another value , if impossible return false value > ''' > if grille_pleine():return > if case_choices(i1,j1) : > grida[i1,j1] = case_choices(i1,j1) [0] > if not sudoku(*case_min()) : return sudoku( i1,j1) > grida[i1,j1] = 0 > return False > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > < #6 (comment)>, > or mute the thread > < https://github.com/notifications/unsubscribe-auth/AJl3G-nj4pHDcbCtk-eoIwoaCVbhg8wTks5utBmsgaJpZM4YRwbg> > . > — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub< #6 (comment)>, or mute the thread< https://github.com/notifications/unsubscribe-auth/AeRAQtOIhG6bg41jQNdyN6pwRrk5xXf1ks5utB6CgaJpZM4YRwbg>. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJl3GzruPf7Ykwgi2kcBDndz_CvFVG2Rks5utCcqgaJpZM4YRwbg> .

Sur une grille simple je gagne quelques centièmes en ajoutant la variable . Sur votre 1ere grille du fichier sudoku17 en faisant tout en récursivité et sur mon vieux PC je suis à 8s..... En fait en cherchant à comprendre comment faire ma boucle sur les valeurs je suis tombé sur un truc dingue : Au lieu de tester l impact sur les cases aval, il suffit de faire return sudoku(* case_min()) et je ne fais pas la boucle... Et là Champagne👑: mon temps passe à 0.08 secondes avec un code de fonction qui fait 7 lignes (6 si je ne prends pas la variable intermédiaire)... Je vais avoir du mal à m'en remettre... Envoyé depuis mon smartphone Samsung Galaxy.

-------- Message d'origine -------- De : jpbozo <jpbozo@hotmail.fr> Date : 08/11/2018 14:51 (GMT+01:00) À : flotpython/recreation <reply@reply.github.com> Objet : Re: [flotpython/recreation] Sudoku (#6) J'avais effectivement une variable de plus pour stocker le résultat , mais comme je ne voyais pas de temps différent je l'avais supprimée. Votre remarque me fait me rendre compte que je peux aussi peut etre ameliorer de faire appel à la recursion sur la meme case tant que je n'ai pas épuisé les candidats : peut etre gain de temps . Je vais tester Merci de la remarque qui m'a donné une idée. Ça aide les remarques 😀 Envoyé depuis mon smartphone Samsung Galaxy.

-------- Message d'origine -------- De : Sébastien Hoarau <notifications@github.com> Date : 08/11/2018 13:59 (GMT+01:00) À : flotpython/recreation <recreation@noreply.github.com> Cc : JiPiBi <jpbozo@hotmail.fr>, Mention <mention@noreply.github.com> Objet : Re: [flotpython/recreation] Sudoku (#6) Ah oui ca y est : en fait vos appels sudoku retournent tous False (enfin None et False) mais qd la grille est pleine ben elle est pleine et donc tous les appels récursifs se terminent... ok je vois. Et sinon vous appelez 2 fois finalement votre case_choices... on peut gagner du temps là non ? Le jeu. 8 nov. 2018 à 16:44, JiPiBi <notifications@github.com> a écrit :

Et pourtant il tourne.. Qd je fais if not sudoku(case suivante), il lance d abord la fonction sudoku et regarde sa réponse sur les cases en aval et la seule reponse qui est en fait retournée est False si blocage sinon on va au bout . Je ne renvoies jamais True, je continue à explorer les autres cases tant que ça ne bloque pas. Pour relancer ma fonction dans la meme case , je ne garde que les candidats de valeur supérieure à la valeur actuelle de la case : je ne tourne donc pas en rond.. Tout est dans la fonction case choices Envoyé depuis mon smartphone Samsung Galaxy. -------- Message d'origine -------- De : Sébastien Hoarau ***@***.***> Date : 08/11/2018 13:07 (GMT+01:00) À : flotpython/recreation ***@***.***> Cc : JiPiBi ***@***.***>, Mention ***@***.***> Objet : Re: [flotpython/recreation] Sudoku (#6) @JiPiBi J'avoue ne pas comprendre comment ce code peut fonctionner car 1. pour moi return <=> return None donc if not sudoku(*..) sera toujours vrai non ? 2. si jamais on passe effectivement pas return False... donc on remet i1, j1 comme case vide mais comment vous testez les autres candidats ? pour moi il manque une boucle for sur les candidats de i1, j1 qqc comme : for e in case_choices(i1,j1): grida[i1,j1] = e Le jeu. 8 nov. 2018 à 15:46, JiPiBi ***@***.***> a écrit : > @sebhoa <https://github.com/sebhoa> > Mon code de récursivité > > def sudoku (i1,j1): > ''' > main code, using recursivity to calculate the grid > at each turn, if the case can be filled with a value , > the case with minimum choices is choosed > else , it tries to propose another value , if impossible return false value > ''' > if grille_pleine():return > if case_choices(i1,j1) : > grida[i1,j1] = case_choices(i1,j1) [0] > if not sudoku(*case_min()) : return sudoku( i1,j1) > grida[i1,j1] = 0 > return False > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > < #6 (comment)>, > or mute the thread > < https://github.com/notifications/unsubscribe-auth/AJl3G-nj4pHDcbCtk-eoIwoaCVbhg8wTks5utBmsgaJpZM4YRwbg> > . > — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub< #6 (comment)>, or mute the thread< https://github.com/notifications/unsubscribe-auth/AeRAQtOIhG6bg41jQNdyN6pwRrk5xXf1ks5utB6CgaJpZM4YRwbg>. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJl3GzruPf7Ykwgi2kcBDndz_CvFVG2Rks5utCcqgaJpZM4YRwbg> .

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#6 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AeRAQkskAGIEEUvgGgoIZdivtQOP6KOOks5utCqrgaJpZM4YRwbg>.

Heu c'était trop beau , je rebouche la bouteille, c'est pas le bon résultat .....