[Ex] Résolveur de Sudoku

Partagez vos scripts, et vos applications AutoIt.
Règles du forum
.
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

[Ex] Résolveur de Sudoku

#1

Message par ZDS »

Voici un résolveur de Sudoku de taille variable.

Il s'agit d'un code que j'ai conçu à partir d'une demande de Guitarist, mais d'un tout autre acabit. Le but étant de résoudre de façon certaine une grille pré-remplie à laquelle il n'existe qu'une seule possibilité. L'interface graphique est adaptée de celle fournie par Guitarist avec Koda, mais entièrement repensée afin de gérer des Sudokus de taille 3x2², 3x3² (taille classique, de 1 à 9), 4x3² (de 1 à 9 et A, B et C) ... jusque 7x5 (1 à 9 et A à Z, pas d'autre caractère potable sous la main ^^).
► Afficher le texteRésolveur de Sudoku
Vous pouvez cliquer sur "Importer" pour y coller une grille. Voici quelques exemples de grilles pour tester :
- 3x3² Facile = 050310020010698540800020000007040080045000910090050700000060007076235090030089050
- 3x3² Débutant = 000400000570000103210605000390080200000701000007020016000802079905000082000009000
- 3x3² Confirmé = 005000601000700000780061900300500000059040030000100006007006120810009007500200800
- 3x3² Difficile = 002300007809000005005009046000003000090127600007480000000572013070940000540800000
- 3x3² Expert = 003040057908060200001350600800700400000008500000014002000430800410080320000000000

Son fonctionnement est simple dans la résolution, il effectue les mêmes opérations jusqu'à arriver à une grille complète :
  • Il remplit d'abord les cases où il n'y a qu'une possibilité possible (selon la ligne, la colonne ou le bloc)
  • Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de la même ligne
  • Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de la même colonne
  • Si il n'y a plus de choix possibles, il remplit les cases où une valeur possible ne peut pas aller ailleurs dans une case de le même bloc
  • Si il n'y a plus de choix possibles, il remplit une case en "TEMPORAIRE" et continue à tenter de remplir la grille
    • Si par le même algo, il arrive à une solution incorrecte (genre deux symboles identiques sur la même ligne) et qu'il ne peut pas terminer, il change la valeur de la case en temporaire par une autre valeur possible
    • Si par le même algo, il arrive à une solution incomplète, il choisit une autre case en temporaire, et il lui affecte une valeur possible, et continue à tenter de remplir la grille
    • Si aucune valeur possible de la grille ne donne de solution correcte, il choisit une autre case
    • Si toutes les cases ont été testées pour toutes les valeurs possibles, il s’arrête, c'est qu'il n'y a pas du tout de solution possible.
Bonne utilisation, et à bientôt !

EDIT 26/09/2011 : Mise à jour du code : ajout d'un système d'heuristiques, et vérification des grilles avant de pouvoir lancer une résolution.
EDIT 27/09/2011 : Mise à jour du code : correction et ajout d'un affichage de l'état de résolution en cours (mode utilisé et cases avec une hypothèse émise affichées en gris).
Modifié en dernier par ZDS le mar. 27 sept. 2011 15:52, modifié 4 fois.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#2

Message par guitarist »

Tu dit que j'ai inventé l'interface mais mon code du depart était bagdad je te rappel :p

Supprime mon nom je n'ai pas fait grand chose et je veux pas avoir l'air important dans ton script :)
Avatar du membre
TT22
Membre émérite
Membre émérite
Messages : 1566
Enregistré le : lun. 18 avr. 2011 15:21
Localisation : La Quatrième Dimension
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#3

Message par TT22 »

C'est très impressionnant :wink:

Mais, il y a un petit problèmes, quand on clique sur résoudre alors que la grille est vide, il se bloque (pareil quand il y a très peu de nombres) il faudrait que ça affiche un message d'erreur, et il faudrait rajouter un bouton "vider la grille" qui efface toutes les cases.

Et éventuellement (mais ça va être compliqué) rajouter une fonction qui permettrait de créer des sudokus :wink:
Cordialement,
TT22
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#4

Message par guitarist »

Si t'a grille est vide il va pas trouver la solution :)
C'est normal faut pas s’inquiéter :p
Kevzi
Niveau 4
Niveau 4
Messages : 78
Enregistré le : dim. 17 juil. 2011 12:36
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#5

Message par Kevzi »

Le script est génial. grâce à vous , je vais plus facilement gagner les concours magazines :lol:
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#6

Message par ZDS »

@TT22:
- Un sudoku classique se remplit d'une seule façon possible, et 99% du temps si l'algo s’arrête avant la fin (déjà il ne bloque pas, tu peux toujours relancer les fonctions ^^), c'est que ta grille de départ n'était pas correcte au départ car elle admettrait plusieurs possibilités (comme une grille vide, qui accepte près de 5 milliards de possibilités de résolution ! très exactement 5 472 730 538...).
- Je peux rajouter un bouton pour effacer la grille, c'est faisable :)
- Je vais essayer d'ici qq temps d'ajouter un système d'heuristiques, et de tentatives de choix de valeurs pour ce genre de problème (mais je préviens de suite, ça risque d'augmenter le temps de résolution de façon exponentielle...!).
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#7

Message par guitarist »

Humm au fait comment on change les dimensions de la grille ?
Avatar du membre
Yle
Niveau 5
Niveau 5
Messages : 167
Enregistré le : mar. 21 avr. 2009 17:22
Localisation : La NORMANDIE -76
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#8

Message par Yle »

Belle réalisation.

Mais avec cette grille : 400081000007200980080060000700005000103000507000100002000070060094006200000450003
Le programme mouline dans le vide. :mrgreen:
Vous devriez mettre un message de "Non résolution" au bout d'un temps x. Qu'en pensez vous ?
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#9

Message par guitarist »

Avec mon programme ça s’arrête au bout de 5 secondes.
Comme celui de ZDS doit etre plus performant ça devrait etre un peu moins j'imagine.
Pas besoin de s’arrêter au bout d'un moment donné, ça servirais à rien :)
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#10

Message par ZDS »

Bonjour.

C'est impossible que le script "mouline", si par mouliner tu entends que le script tourne dans le vide indéfiniment. Le script s’arrête à un moment ou à un autre, car il effectue un nombre maximum fini de boucle.
Si par mouliner tu entends qu'il travaille parfois longtemps sans trouver de solution, en fait ce n'est que cosmétique, il manque juste une progressBar ou autre chose pour dire où en est le script dans son algo.

Sinon pour le fait qu'il ne trouve pas de solution à cette grille, si tu avais lu mon premier message sur son algo avant de "critiquer", ce script n'est pas dans sa version finale:
ZDS a écrit :- A VENIR : Si il n'y a plus de choix possibles, il remplit une case en "TEMPORAIRE" et continue à tenter de remplir la grille
- - - - Si il arrive à une solution incorrecte (genre deux symboles identiques sur la même ligne) et qu'il ne peut pas terminer, il tente avec une autre valeur temporaire
- - - - Si il arrive à une solution correcte, c'est gagné
- - - - Si il n'y a plus de choix possibles pour aucune valeur temporaire possible, il s’arrête, c'est qu'il n'y a pas du tout de solution possible.
A bientôt !

PS: C'est bizarre ton histoire de grille incomplète, moi il me trouve bien la solution suivante :
► Afficher le texteSolution
Ce qui est le plus bizarre, c'est que le script est déterministe, et à aucun endroit, pour des conditions initiales identiques, il ne peut différer dans son fonctionnement d'une exécution à une autre même si les ordis sont différents... Mais bon, ça peut venir d'ailleurs.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#11

Message par guitarist »

Nope chez moi non plus j'ai pas de résolution complète avec ton script et le mien :/
Avatar du membre
Yle
Niveau 5
Niveau 5
Messages : 167
Enregistré le : mar. 21 avr. 2009 17:22
Localisation : La NORMANDIE -76
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#12

Message par Yle »

Bonsoir,

Mon précédent message n'a pas été fait dans le but de critiquer.
J'ai aussi bien lu que ce programme n'était pas terminé et quand je dis, il mouline c'est sous entendu "boucle"

Sur mon Portable équipé d'un CPU Centrino Duo sous XP SP3, au bout de 5 mn, je n'ai aucune solution
Il me remplit 4 cases et n'affiche plus rien. Je clique sur QUITTER et il quitte.

Voir fichier joint
Fichiers joints
Sudoku.JPG
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#13

Message par ZDS »

Quand il "boucle", clique sur les différentes cases vides ou pleines, et dis moi si les boutons de droite (correspondant aux valeurs possibles) changent ou non en fonction de la case qui a le focus. Oublie la question, car si en cliquant sur Quitter, il quitte, c'est qu'il ne boucle pas. Il a bel et bien fini son algo, mais n'a pas résolu la grille, c'est tout. Donc c'est bien ce que je pensais, tu as cliqué sur Résoudre, il a fait ce qu'il pouvait mais n'a pas réussi à résoudre la grille (surement au bout de 15/20 secondes) et tu as patienté pour rien devant ton écran pendant 5 minutes ^^
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
Avatar du membre
Jerome
Niveau 9
Niveau 9
Messages : 661
Enregistré le : mar. 07 avr. 2009 08:35
Localisation : Picardie
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#14

Message par Jerome »

Petit soucis avec le code suivant pour test :


003040057908060200001350600800700400000008500000014002000430800410080320000000003

image :

Image

PS : regarder la case en haut a droite :)

Need de faire une gestion d'erreur sur l'importation (en outre, j'importe dans la meme 3*3 deux fois le meme chiffres :) )

Jérôme
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#15

Message par ZDS »

Avec une grille incorrecte au départ, c'est pas étonnant qu'il fasse n'importe quoi :)

Bref, j'ai ajouté un système de vérification, et aussi un 4ème mode de travail qui correspond à une résolution par essais successifs. Ce système est donc beaucoup plus long car au lieu de résoudre une fois, il peut aller jusqu'à résoudre 9 fois (voire 9x8 mais c'est plus rare (voire 9x8x7 mais c'est encore plus rare (etc...))) une grille avant de tomber sur la réponse correcte.

Bref, je le répète, cet algo ne peut pas "mouliner"; les conditions d'arrêt ont été validées et ne peuvent donc pas boucler indéfiniment (ca reste un système déterministe itératif). La seule condition c'est de ne pas lui donner n'importe quoi à résoudre (n'est-ce-pas Jérôme ^^).

A bientôt !
Modifié en dernier par ZDS le lun. 26 sept. 2011 16:11, modifié 1 fois.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
Avatar du membre
Jerome
Niveau 9
Niveau 9
Messages : 661
Enregistré le : mar. 07 avr. 2009 08:35
Localisation : Picardie
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#16

Message par Jerome »

ZDS a écrit :La seule condition c'est de ne pas lui donner n'importe quoi à résoudre (n'est-ce-pas Jérôme ^^).
A ben tu nous donne ton travail pour qu'on le test ect, moi j'en profiter pour debugger et trouver les truc qui vont pas :)
pierrotm777
Membre émérite
Membre émérite
Messages : 770
Enregistré le : sam. 11 oct. 2008 14:44
Localisation : Bordeaux
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#17

Message par pierrotm777 »

J'obtiens des matrices de 3x2 et non de 3x3 avec l'exemple du post 1 !
guitarist
Niveau 6
Niveau 6
Messages : 235
Enregistré le : mar. 02 déc. 2008 16:59
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#18

Message par guitarist »

Faut changer les globales au début.

D'ailleurs y a un bug si on lance une grille vide. Rien ne se passe alors qu'on devrait voir ne grille apparaître non?
pierrotm777
Membre émérite
Membre émérite
Messages : 770
Enregistré le : sam. 11 oct. 2008 14:44
Localisation : Bordeaux
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#19

Message par pierrotm777 »

Effectivement, en remplaçant dans les Global du début

Code : Tout sélectionner

$SUDOKU_DIMENSION[3] = [6,3,2] 
par 
Global $SUDOKU_DIMENSION[3] = [9,3,3]
Je peux lancer les exemples
Modifié en dernier par pierrotm777 le mar. 27 sept. 2011 14:55, modifié 1 fois.
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 10:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Ex] Résolveur de Sudoku

#20

Message par ZDS »

C'est corrigé en 9,3,3 (désolé c'était un test juste avant de publier).

Pour la grille vide, faut pas non plus tenter le diable, il risque de tourner longtemps (pas indéfiniment, mais très longtemps) pour générer une des 5 milliards de grilles correctes possibles. En plus il affiche un message disant que c'est pas assez rempli, forcer la résolution c'est admettre que ça risque de ne pas répondre correctement ou assez rapidement.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !
Répondre