Sudoku
Opened this issue · 6 comments
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
Heu c'était trop beau , je rebouche la bouteille, c'est pas le bon résultat .....