hackalexandres32
Messages postés37Date d'inscriptiondimanche 25 novembre 2007StatutMembreDernière intervention 3 novembre 20081 29 févr. 2008 à 03:07
A super men le look aussi BRAVO!!!!!
greatdanger
Messages postés1Date d'inscriptionsamedi 11 février 2006StatutMembreDernière intervention18 février 2008 18 févr. 2008 à 18:32
mhmmmmmm cool programme
j'aime bien le SuDoKu
cs_macromed
Messages postés30Date d'inscriptionmardi 5 octobre 2004StatutMembreDernière intervention25 février 2007 23 juil. 2006 à 01:46
L'exe dot etre remplacer par ex_ pour que le téléchargement fonctionne, merci :)
Titix50
Messages postés1Date d'inscriptionlundi 15 mai 2006StatutMembreDernière intervention16 mai 2006 16 mai 2006 à 17:45
Bonjour tout le monde,
J'ai realisé un programme de résolution du Sudoku suivant la méthode "à la main".
Je résouds automatiquement 90% des Sudokus. Les 20% restants peuvent être résolus juste en intégrant dans la programmation un choix aléatoire d'un nombre(en suivant bien sûr toutes les contraintes).
Si quelqu'un veut des précisions....
ddurandet
Messages postés5Date d'inscriptiondimanche 4 décembre 2005StatutMembreDernière intervention20 mars 2006 20 mars 2006 à 09:29
Bonjour Cacophrene.
Comme tu le dis, chaque méthode à ses avantages et ses inconvénients.
Pour moi la méthode des stratégies à aussi l'avantage de rester dans le domaine du casse-tête et d'une "résolution logique" du Sudoku, le casse-tête n'est plus le Sudoku, mais le programme qui le résoud. Ce que ne fait pas le rebroussement.
Egalement, c'est vrai que l'on ne peut pas prouver qu'une stratégie résout tous les Sudokus, à moins d'être très très fort, mais le rebroussement à le problème inverse, il ne peut pas prouver que l'on peut résoudre logiquement un Sudoku.
Je crois que ce sont deux visions différentes de l'application elle même. Le rebroussement permet de connaître la/les solutions d'un Sudoku. L'approche stratégie permet de savoir si l'on aurait pu résoudre ce Sudoku "à la main" en utilisant la même stratégie.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 17 mars 2006 à 18:33
Bonjour !
Voilà du temps libre, enfin, pour répondre à tous ces messages ! Voici ce que je pense de tout ce que j'ai lu :
1. La méthode du rebroussement (dite aussi retour-arrière ou backtracking), autrement dit la méthode employée dans mon programme, présente l'avantage de résoudre TOUTES les grilles de sudoku, et de donner, moyennant une modification mineure du programme actuel (QUI NE LE FAIT PAS !), TOUTES les solutions d'une grille. A cet avantage un inconvénient : le temps de calcul peut être assez long pour certaines configurations. Conclusion : méthode très pratique mais à utiliser avec modération.
2. Toutes les méthodes faisant appel à des stratégies plus ou moins fines. Elles ont un avantage CONSIDERABLE sur le rebroussement : elles sont toujours rapides ! Hélas, là encore, il y a un inconvénient : il peut être TRES DIFFICILE d'apporter la preuve que ces méthodes résolvent TOUTES les grilles et en donnent TOUTES les solutions. Conclusion : sauf à être fort en algorithmique, vous aurez du mal à démontrer que vos solveurs fonctionnent à tous les coups. N'oublions pas ce grand théorème : ce n'est pas parce que cela fonctionne dans tous les cas testés que cela fonctionne toujours. En maths, ce qui fonctionne toujours est au bas d'un raisonnement. Conclusion : à utiliser avec prudence !
Voilà tout.
Cordialement,
Cacophrène
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 12 mars 2006 à 14:01
Bonjour tout le monde !
Merci pour vos encouragements, pour vos remarques diverses (fonctionnement, le bug de la réinitialisation, etc...). Je n'ai que peu de temps en ce moment mais je corrige tout ça avec le retour du soleil ;-).
A bientôt,
Cacophrène
jdenver
Messages postés1Date d'inscriptionmercredi 11 janvier 2006StatutMembreDernière intervention23 janvier 2006 23 janv. 2006 à 22:52
Je me suis lancé dans un algo en Delphi (désolé) sans savoir tout le travail que vous aviez déjà été fait. Je résouds toutes les solutions (uniques et multiples) d'une facon récursive simple et TRES rapide. En gros voilà mes algos.
function SolutionParEssais:boolean
begin
Identifie une case vide quelconque
pour chaque cas possible de cette case
tester si SolutionLogique
Arrêter si solution trouvée
end;
function SolutionLogique:boolean
begin
répéter tant que (Methode1>0) ou (Methode2>0) ou (Methode3>0);
si trouvé alors
Result = true
sinon
Result = SolutionParEssais
end;
cs_gagou9
Messages postés126Date d'inscriptionvendredi 19 septembre 2003StatutMembreDernière intervention20 novembre 2007 6 janv. 2006 à 19:02
Bonjour !
alors j'ai implementé si l'on peut un Solveur de sudoku que j'avai mi sur le site et qui a été desactivé car "trop de sudoklu", mais il resou TOUTES les grille qui sont possibles, et quand il ne peut peut plus resoudre par la logique, il fai des ipotheses. a l'origine en javascript, et d'ailleur toujours actuellement, car je n'ai fai que le rendre utilisable en vb.
je ne l'ai pas sou la main mais si ça vous interresse, vous pouvez dl un prog d'install fai pour un pote a l'origine http://zappiweb.free.fr/telech/install_sudoku.exe,
apres l'install, lorsque vous lancerez le prog, il va vou dirte fichier introuvable : allez voir dans le dossier d'insttall et il y sera !!
voila si vous voulez la source mailez moi !
gagou9[AT]gmail.com
bothan
Messages postés12Date d'inscriptionmercredi 16 juin 2004StatutMembreDernière intervention 3 mai 2010 21 déc. 2005 à 09:05
Bonjour Cacophrene
je viens de tester ton programme de Sudoku court et efficace. bravo
Néanmoins car il ya un mais, il me semble qu'il y a un petit problème dans la routine de reinitialisation que je reprends ici:
Private Sub cmdRéinitialiser_Click()
For iCompteur = 1 To 81 Step 1
With ttbCase(iCompteur)
Let .Text = Empty
Let .Font.Bold = False
Let .ForeColor = vbBlack
End With
Next iCompteur
End Sub
Ici tu reinitialise uniquement le contenu des cases et non les valeurs des variables Ichiffres, ce qui conduit à:
If iIndex = 0 Then
MsgBox "Le programme n'a pas pu trouver de solution à ce sodoku", vbExclamation, "Échec"
Call cmdRéinitialiser_Click
Exit Sub
End If
Il me semble qu'une reinitialisation de la valeur de iChiffres est necessaire pour relancer la resolution.
du type
Dim n as Integer
Private Sub cmdRéinitialiser_Click()
For iCompteur = 1 To 81 Step 1
With ttbCase(iCompteur)
Let .Text = Empty
Let .Font.Bold = False
Let .ForeColor = vbBlack
End With
iChiffres(iCompteur)=0
Next iCompteur
End Sub
A +
ddurandet
Messages postés5Date d'inscriptiondimanche 4 décembre 2005StatutMembreDernière intervention20 mars 2006 13 déc. 2005 à 12:50
Si tu creuse, il y a des associations de triades intéressante. L'une qui me donne de l'espoir, c'est celle ci :
0A0-000-000
0A0-000-000
0A0-000-000
0B0-000-000
0B0-000-000
0B0-000-000
000-000-000
000-CCC-DDD
000-000-000
Si on associe les valeurs des triades A et B, elles ont obligatoirement 4 et seulement 4 valeurs communes avec les triades C et D. Et je pense, (soupçonne) que cette info à de la valeur pour progresser en difficulté. Pour l'instant, je n'ai pas trouvé cette idée ailleurs sur le web, mais je n'ai pas trop cherché non plus. Peut-être aussi que ça n'apporte rien par rapport aux groupes (de 2, 3 ou 4), que c'est juste une autre façon d'attaquer le problème.
Bonne vacances. J'aurai peut-être un peu de temps moi aussi pendant les vacances pour revenir avec quelque-chose de plus concret.
jmsebaux
Messages postés9Date d'inscriptionmercredi 14 mai 2003StatutMembreDernière intervention27 mai 2011 13 déc. 2005 à 10:54
Bonjour,
Effectivement on ne parlais pas de la même chose, l'approche est interressante, je vais essayer de creuser, pour voir si ça ouvre des voies non couvertes par les méthodes classiques.
Mais l'exemple que tu donnes est l'équivalent des méthodes classiques, "l'obligation" de présence est l'équivalent de la méthode des jumeaux ou triplets, c'est à dire, une valeur possible uniquement dans 2 ou 3 cases d'une même ligne ou colonne à l'intérieur d'une même région. On ne sait pas où mais on sait que la valeur est dans 1 de ces cases.
La propagation de l'information est faite implicitement par le "nettoyage" des valeurs possibles (dans ton exemple, on supprime le 3) dans les autres cases de la ligne ou colonne. Les "obligations" ou jumeaux/triplets des régions 1, 5 et 6 nettoies la région 4 et du fait du 3 en région 7, on se retrouve avec une valeur "isolée" pour le 3 dans la région 4.
Je vais partir en vacances à la fin de la semaine ... avec des grilles de sudoku, ça sera l'occasion de réfléchir à ta méthode; Il y a surement quelque chose de sympa à en sortir au niveau des algos de réduction des valeurs possibles.
ddurandet
Messages postés5Date d'inscriptiondimanche 4 décembre 2005StatutMembreDernière intervention20 mars 2006 12 déc. 2005 à 22:42
Bonsoir.
Je pense qu'on ne parle pas des mêmes triades. J'ai fureté rapidement, et je sais que certains se servent des cases comportant les mêmes solutions possibles, pour éliminer d'autres valeurs... je vois à quoi cela correspond par rapport à ma méthode manuelle et je ne veux pas approfondir, je ne voudrais pas tomber sur une solution toute faite :D Disons que je commence à me lasser des Sudoku. L'écriture de l'algorithme et du code pour les résoudre est un autre passe temps qui prolonge le plaisir, alors je fais durer. c'est pour cela que je me suis arrêter ici, parce que c'était à peu près le niveau ou j'étais arrivé.
Je parle des triades alignées. Les intersections entre une horizontale et une zone. Ou entre une verticale et une zone. En attaquant la réflexion par ces triades, on peux enregistrer des informations plus précises que sur une case seule. Disons, une information "floue" vu sous l'angle d'une case, mais qui permet de transporter des "obligations" vers d'autres triades.
000 000 000
000 000 000
000 000 000
000 000 000
000 XXX 000
000 000 000
000 000 000
000 000 000
000 000 000
Ici, Les zéros symbolisent des cases, les xxx symbolisent une triade.
Je tente un exemple d'information que l'on peux maîtriser en regardant les triades (je ne promets pas que dans mon exemple on ne puisse pas faire la même chose avec les méthodes classiques.
120?000?000
400?000?030
560?000?000
000?000?000
000?000?201
000?521?469
030?000?000
000?000?000
000?000?000
Regardez le 3 de la région en haut à droite. Il donne une information à la première triade horizontale de la zone juste en dessous : celle-ci doit (obligation) contenir un trois., même si je ne sais pas encore dans quelle case.
120?000?0C0
400?000?030
560?000?000
000?000?DDD : ici, je sais qui "doit" (D) y avoir un 3
000?000?2C1 : car ici, il ne peut pas y avoir de trois(C comme contrainte)
000?521?469
030?000?000
000?000?000
000?000?000
Donc, sur la même horizontale mais, sur la triade du centre, il ne peut pas y en avoir. C'est une contrainte (C)
120?000?000
400?000?030
560?000?000
000?CCC?DDD
000?DDD?201 : ici, maintenant au centre, la triade "doit" contenir un 3 !*
000?521?469
030?000?000
000?000?000
000?000?000
* Car les deux autres triades de la zone y renoncent.
En repartant du même principe, dans la zone tout en haut à gauche :
12D?000?000
4CD?000?030
56D?000?000
CCC?CCC?DDD
CCC?DDD?201
0CC?521?469
030?000?000
000?000?000
000?000?000
Il n'y a plus qu'une case disponible pour un 3 dans la zone de gauche, au centre.
C'est un exemple simple. Mais on arrive souvent dans les sudoku difficiles à savoir si une valeur doit être dans une triade ou si elle est contrainte. En faisant voyager ces informations, on peut résoudre des sudokus très difficiles. Par exemple ceux ou l'on n'a aucun exemplaire d'un chiffre...
J'espère que j'ai été assez clair et pas trop envahissant.
Si j'ai bien compris, JMSEBAUX, tu n'attaques pas par case mais par petites méthodes successives en reproduisant les méthodes manuelles ? Je penses qu'en agissant ainsi, tu progresse sûrement, mais lentement.. j'espère qu'avec mon principe je pourrai gagner du temps, mais je ne suis pas sûr qu'il soit aussi efficace. Et il sera surtout moins facilement évolutif si je dois rajouter des méthodes de comparaisons.
jmsebaux
Messages postés9Date d'inscriptionmercredi 14 mai 2003StatutMembreDernière intervention27 mai 2011 12 déc. 2005 à 11:12
Pour DDurandet
Ce n'est pas suffisant, mais le principe est le bon. Il faut faire ca non seulement par région (carre de 9 cases) mais aussi par ligne et par colonne ou le même raisonnement s'applique. Quand tu l'aura fait pour 3 valeurs, il faudra aussi le faire pour 4.
Dans mon programme (http://www.vbfrance.com/code.aspx?ID=34358)j'ai impléménté la recherche de groupe de 3 cases ayant de 1 à 3 (idem pour 4) valeurs "isolées" (pas mélangées), en ligne colonne ou région (voir le site: http://www.mots-croises.ch/Manuels/Sudoku/). Ca permet de bien "nettoyer" les valeurs possible dans les autres cases mais ça n'est pas suffisant pour ta grille par exemple.
Même si tu est sur MAC et que tu ne peut pas executer le prog tu peux toujours regarder les sources avec un simple éditeur de texte, comme ça tu pourra comparer tes algos avec ceux de cacophrene et les miens (fichier sudoku.bas)
Je pense rajouter "un jour ..." la recherche de groupe de (3 ou 4) valeurs "mélangées" qui permet de nettoyer les cases ou apparaissent ces valeurs. Mais a première vue ça n'est pas suffisant non plus pour ta grille.
L'autre algo que je pense rajouter est la recherche des positions dites "XY-Wing" (voir toujours sur le site http://www.mots-croises.ch/Manuels/Sudoku/)
bon courage et viens nous faire part de tes progrès.
ddurandet
Messages postés5Date d'inscriptiondimanche 4 décembre 2005StatutMembreDernière intervention20 mars 2006 10 déc. 2005 à 09:57
Oui, une seule solution. Je sais. Je le résous à la main ce qui n'est pas le cas du
500000000
000000000
000000000
000000000
000050000
000000000
000000000
000000000
000000005
La question de la logique de l'ordinateur n'est pas en cause. Ce sont les principes de déduction plus poussés que les simples contraintes cases, lignes horizontales, lignes verticales, qui sont difficiles à programmer.
De mon côté, pas de progrès depuis que j'ai posté, mais je persévère.
PS : je suis arrivé sur votre forum par une recherche générique, et je ne m'étais pas aperçu qu'il s'agissait d'un forum VB. Je suis sur Mac et à ma connaissance, je ne peut pas tester vos exemples, Excusez-moi de cette intrusion. Si je trouve un code qui résout la grille dont je parle, j'essayerai de vous l'expliquer.
JMSebaux : comment oriente-tu ta recherche ? Si tant est que cela peut s'expliquer en quelques mots ? Je me suis orienté vers une travail sur les groupes de 3 cases, horizontales ou verticales, à l'intérieur d'un carré. Chaque triade faisant reporter sur les autres triades ( de sa case et de sa colonne(ou sa rangée) ses contraintes et déduisant des contraintes reçues quelles sont ces obligations. Ceci me permet (en théorie) de faire suivre plus d'informations que sur une approche par case... puisque je peut savoir qu'un 3 par exemple est dans une triade, sans savoir ou il se place vraiment. Grâce a cette infos, je peux dire à toutes les autres triades en relation qu'elles doivent abandonner le trois.
Je ne sais pas si le principe est suffisant, car j'attends là les limites de ma "conceptualisation" et j'ai beaucoup de mal à lier les bonnes triades entre elles.
A suivre...
jmsebaux
Messages postés9Date d'inscriptionmercredi 14 mai 2003StatutMembreDernière intervention27 mai 2011 6 déc. 2005 à 16:57
Bonjour,
La grille proposeé par DDurandet est solvable
J'ai fait un programme suite à mon commentaire pour implémenter les algos dont je parlais.
il est là -> http://www.vbfrance.com/code.aspx?ID=34358
Il trouve une solution unique à cette grille.
Par contre avec les algos que j'ai implémenté il n'arrive pas encore à placer toutes les cases de manière purement déductive. Il faut utiliser le bouton "résoudre" (algo d'essai récursif) pour avoir la solution. Mais elle existe.
Je réfléchis a d'autre algo pour compléter la recherche déductive mais c'est pas facile et je n'y passe pas trop de temps ... je suis un peu faineant.
cs_CMoiChris
Messages postés13Date d'inscriptiondimanche 18 juillet 2004StatutMembreDernière intervention 6 décembre 2005 6 déc. 2005 à 14:27
Salut Cacophrene,
Pas mal du tout ton prog et le visuel de la grille de jeu.
Je te met une très bonne note...
A plus! CMoiChris
cs_CMoiChris
Messages postés13Date d'inscriptiondimanche 18 juillet 2004StatutMembreDernière intervention 6 décembre 2005 6 déc. 2005 à 14:23
Salut ddurandet,
J'ai créé un Sudoku de toute pièce utilisant les "possibles" et les "pas possibles" (je mettrait le prog en ligne un peu plus tard). Malgré cela, la grille que tu nous soummet n'est pas faisable. Il manque des chiffres sur la grille...
Sinon on pourrait aussi résoudre ça???:
500000000
000000000
000000000
000000000
000050000
000000000
000000000
000000000
000000005
Si même une machine (avec une logique à priori sans faille) ne peut résoudre une telle grille, l'homme a un avantage sur elle, il esaye...
Alors pouquoi ne pas tenter "d'essayer" un chiffre et de voir si on peut compléter le grille?
Le prog que j'ai fait créé met les nombres "possibles" dans un .txt qui sert de "mémoire" pour le test des cases.
Mesdames, messieurs, à vos programmes... ;o)
A plus! CMoiChris
ddurandet
Messages postés5Date d'inscriptiondimanche 4 décembre 2005StatutMembreDernière intervention20 mars 2006 4 déc. 2005 à 15:31
Bonjour.
En réponse a Lucyberad : à ma connaissance, le propos de JMsebaux est juste.
Les 3 principes que tu mets en avant ne sont pas suffisants pour résoudre des Sudoku de niveau extrême. Jusqu'à "difficile", la plupart du temps, ça passe, mais pas au delà. Et pourtant, avec de la logique et de la méthode on peut les résoudre et ils ont bien une solution unique.
Je le sais parce que j'ai pour l'instant un programme équivalent qui ne peut pas résoudre certains sudoku
Par exemple :
080070090
097040230
000109000
300000004
015090320
900000007
000803000
041050860
050020070
Ou le zéro symbolise les cases vides.
Si tu veux bien le tester et me dire que ton programme ne le résout pas, ça serait sympa. :-) S'il le résout, ça m'intéresse quand même, ça voudrait dire que j'ai une erreur de mon côté et que je dois retourner plancher.
En fait, j'essaye d'aller plus loin mais ça devient complexe. Il y a bien une donnée que l'on exploite pas dans
le principe que tu décris : c'est celui d'obligation.
Si une case possède plusieurs solutions possibles, mais que les autres cases de sa rangée, sa colonne ou son paquet ne peuvent pas fournir une des valeurs, alors la case est dans l'obligation de choisir ce nombre. Sur le même principe, si deux "mini" colonnes (colonnes à l'intérieur d'un paquet de "9") ne peuvent accueillir un nombre, cela crée une obligation de ce nombre dans la 3eme mini colonne, et cela même si on ne peut pas dire dans cette mini colonne ou se trouve exactement la valeur. Cette obligation crée a son tour une contrainte : la valeur ne peut pas se trouver dans les 2 mini colonnes des cases contiguës formant la verticale complète... C'est, je crois, ce que dit JMsebaux ici :
"En effet, arrivé à un certain stade de la grille (parfois dès le début) il n'y a plus de cases a placées par "choix". Mais par contre on arrive à déduire dans quelles case ne pas placer certaines valeurs. C'est ce que j'appele le "non choix".
Après une série de non choix on peut se retrouver dans des situations de "choix" et ainsi continuer à progresser vers la solution."
Pour l'instant, dans les mots pour moi, c'est clair. Reste plus qu'a en faire un code. Et là, c'est une autre paire de manche :)
violent_ken
Messages postés1812Date d'inscriptionmardi 31 mai 2005StatutMembreDernière intervention26 octobre 20102 27 nov. 2005 à 11:41
chasseurdedemon
Messages postés60Date d'inscriptionmardi 23 décembre 2003StatutMembreDernière intervention15 novembre 2010 27 nov. 2005 à 11:38
salut
est-ce que quelqu'un peux me dire comment faire pour créer une grille de sudoku en vb car moi j'arrive à ce que l'ordi choisis les numéro et les place dans chaque case de la grille mais je me retrouve tout le temp avec le même numéro dans une colone et ligne donc je voulais savoir comment faire pour une fois qu'il a choisi un numéro il le supprime des posibilité de ces choix mais qu'il le remé pour la ligne suivante...
merci d'avence
mokmap NC
perathoner
Messages postés90Date d'inscriptiondimanche 5 novembre 2000StatutMembreDernière intervention26 juillet 2006 16 nov. 2005 à 14:44
Bonjour, J'aimerais savoir où puis-je trouver la dll qui va avec votre ReyXP.ocx ???
Merci d'avance pour vos réponses.
violent_ken
Messages postés1812Date d'inscriptionmardi 31 mai 2005StatutMembreDernière intervention26 octobre 20102 15 nov. 2005 à 21:52
6670903752021072936960 grilles VALIDES
cs_Ulmo
Messages postés24Date d'inscriptionsamedi 14 février 2004StatutMembreDernière intervention 3 avril 2006 15 nov. 2005 à 21:40
crenaud76 : Je pense qu'il y a plutot 9^(9*9)=9^81 differentes grilles soit a peu pres :
196627050475552913618075908526910000000000000000000000000000000000000000000000
violent_ken
Messages postés1812Date d'inscriptionmardi 31 mai 2005StatutMembreDernière intervention26 octobre 20102 14 nov. 2005 à 21:10
Salut à toi carcophène !
Un résolveur de Sudoku ! Quelle bonne idée! Je me suis mis à de jeu il n'y a pas très longtemps, et l'idée d'en faire un programme ne m'était pas encore venue. Maintenant, c'est trop tard ! :-)
Pour ta source, le code utilisé à l'air bon, c'est ultra bien expliqué, le seul problème est qu'il y a un bug (mineur sans doute) au niveau de l'ocx de l'excellent Renfield. (reyxp.ocx) Je lance le programme, et erreur 429: " le composant ne peut créer l'objet". Je ne m'y connait pas en activeX, j'ai pourtant enregistré les ocx (regsvr32) mais çà marche toujours pas...
Est ce qqun pourrait m'aider ?? Merci bcp !
Bonne continuation à tous, et d'avance bravo à Carcophène, même si je n'ai pas encore pu exécuter ta source !
@+
Lucyberad
Messages postés414Date d'inscriptionmercredi 16 juin 2004StatutMembreDernière intervention26 juillet 20073 7 oct. 2005 à 12:19
ben en fait lrosque j'ai voulu commencer a programmer un truc similaire, j'ai voulu faire la meme chose:
proceder par elimination (ou non choix), a la main je les fait pareil quand c'est dur.
en fait le pricipe est simple:
le programe deja doit verifier si le sudoku est valide par le fait que le sodoku n'est pas sous contrainte (2 meme chiffre sur une ligne ou autre).
on regarde quelS chiffreS on peut mettre dans chaque case, des le depart.
donc apres on as forcement une case qui ne possede qu'un chiffre. on le pose et on elimine ce chiffre des possibilité de ceux de la ligne, la case et la collone. ceci fait, le sodoku vas etre resolu.
afin de determiner si il est resolvable, c'est tout simple, si aucune case ne possede un seul et unique choix, on estime alors que le sudoku est insolvable.
voici comment je resout les sudoku, hesitez aps a me dire si c as fonctionnel (en expliquant bien sur ^^).
Lucyberad
jmsebaux
Messages postés9Date d'inscriptionmercredi 14 mai 2003StatutMembreDernière intervention27 mai 2011 6 oct. 2005 à 09:13
Bonjour,
Très bien pour programme. J'ai juste une petite remarque sur les conclusions qui sont "déduites" de la non résolution d'une grille par le programme. Vous concluez que la grille est soit impossible soit à solutions multiples.
En fait non, le raisonnement est trop simple. Il y a beaucoup de grilles qui sont à solution unique mais qui ne sont pas résolue par le programme. Car en fait vous avez oubliez des méthodes de résolution très importantes (mais très difficile à programmer).
Les méthodes que vous avez implémenter sont des méthodes de "choix" qui permette de placer aisément les cases à valeur unique ou les cases à valeurs "isolées" dans une ligne, colonne ou région. C'est déjà bien et ça permet de résoudre quasiment toutes les grilles de difficulté faciles et moyennes
Mais pour les grilles difficiles ou tres difficiles (et pourtant à solution unique) ces méthodes ne suffisent pas. Il faut alors appliquer des méthodes de "non choix".
En effet, arrivé à un certain stade de la grille (parfois dès le début) il n'y a plus de cases a placées par "choix". Mais par contre on arrive à déduire dans quelles case ne pas placer certaines valeurs. C'est ce que j'appele le "non choix".
Après une série de non choix on peut se retrouver dans des situations de "choix" et ainsi continuer à progresser vers la solution.
Si vous arrivez à implémenter la méthode des jumeaux et triplets et des groupes isolés ou mélangés votre programme pourra résoudre une grande partie des grilles très difficiles et toujours de manière entièrement logique et sans retour en arrière après un "choix pour voir" entre 2 possibilités.
Encore merci pour le programme.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 11 août 2005 à 21:14
Merci beaucoup... c'est ma foi fort sympatique et trés agréable... juste un mot, pour le .Rar, je ne l'ai pas (encore) reçu... Je suis allé faire un tour sur le site que tu proposes, pas mal du tout, mais trop riche pour retrouver tes icônes... alors, oui cela me serais utile d'avoir ce fichier de ces icônes, si Rar... -);
...et je te renouvelle mes remerciements...
Amicalement,
Us.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 11 août 2005 à 10:02
Salut us_30 !
Il n'y a aucun problème, prends ce que tu veux tant que tu veux, si ça te convient ! C'est le principe même du site, et je crois que c'est aujourd'hui suffisamment rare - l'accès libre, l'entraide, la gratuité - pour qu'on cherche à le maintenir à tout prix ! Pour les icônes que j'ai utilisées, tu en trouveras bien d'autres sur WinCustomize.com. J'ai pris sur moi de t'envoyer un .rar avec les icônes que j'ai déjà téléchargées pour t'éviter de le refaire en espérant que cela te soit utile.
Bonne programmation,
Cacophrène
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 10 août 2005 à 18:32
Merci... et bien... je m'amuserai prochainement à coder une version personnelle du Sudoku sous Excel... mais franchement, ta présentation du Sudoku est tellement jolie,... que ma foi... je repiquerai bien un peu dans ta source... j'espère que tu n'y prendra pas ombrage ?...
En ce qui concerne des sites évoquant des idées permettant de gagner "un poil" du temps, je pense, comme toi que cela ne présente pas d'intérêt, à partir du moment qu'on estime que la résolution est assez rapide... Ce n'est qu'un p'tit jeu... Il est, pour ma part plus amusant de trouver un algorithme, que de jouer effectivement au sudoku... Je dirais même, qu'à partir du moment qu'on fait bien le tour du problème, le jeu perd tout son intérêt, puisqu'il se résume à une application simple et systématique des "3 règles" déjà évoquées... ET quand, je pense que j'ai vu des sites vendant des petits logiciels pour résoudre le Sudoku, misère... Finalement, rechercher une factorisation est de loin plus amusant ; come-back math !
Amicalement,
Us.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 10 août 2005 à 17:42
Salut us_30 !
Il fonctionne très bien. Très vite aussi. C'est une bonne idée de programmer ce qu'on fait soi-même à la main. Sinon, personnellement, j'en reste là. J'ai parcouru des sites où l'on discute de points plus précis (pour gagner une fraction de seconde, mais à vrai dire quel intérêt ?), mais je ne suis pas emballé. En tout cas, je l'ai dit et je le répète, bravo pour cet algorithme ! Il servira sûrement à ceux qui veulent faire un générateur...
Cordialement,
Cacophrène
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 10 août 2005 à 13:27
Ouppssss... La Sub Marque n'a plus lieu d'être. Elle doit être supprimée... Désolé...
Us.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 10 août 2005 à 13:12
Bonjour,
Voici donc le code pour la résolution du sudoku, programmé sous Excel. La grille doit être écrite dans la plage A1:I9. L'algorithme suit assez fidèlement les étapes décrites l'autre jour. Je n'ai pas poussé trop loin les possibilités qu'on peut en retirer. Par exemple, on peut assez facilement s'en servir pour composer une grille. Ceci est rendu possible grâce à la connaissance des solutions dite "multiple". Pour faire trés simple, si on compose une grille qui n'a pas qu'UNE solution, alors le programme s'arrête et affiche les premiers nombres possibles (en fait non encore rayé). Il suffit alors de repérer une impossibilité (suivant la règle) et de choisir lequel retenir, puis de recommencer... Cette façon de faire pourrait être bien sur automatisée...
A propos de l'autre jour, j'ai maintenant la conviction, que les "3 règles" d'éliminations exprimées, sont suffisantes pour résoudre toute grille. Cette conviction me viens d'un raissonnement assez simple par absurde...
L'Algorithme que je te propose est encore optimisable, si bessoin... Mais au vu de la rapidité (moins de la seconde), je laissé tombé. C'est suffisant comme cela (quelque soit le niveau de difficulté de la grille)...
Maintenant, j'espère que tu pourras reprendre et complèter ton jeu... Pour ma part, peut-être que je finirais par déposer aussi une version...
Amicalement,
Us.
==
Option Explicit
'Tableau des cases avec les 9 valeurs par case
Public C(9, 9, 9) As Long
Sub Sudoku()
'*-*-*-* RESOLUTION DU SUDOKU *-*-*-*
'Variables générique de repérage
Dim X As Long, Y As Long, t As Long
Dim XX As Long, YY As Long, V As Long
Dim CX As Long, CY As Long
Dim Nbs As Long, MemNbs As Long, s As Long, k As Long
'Récupération et formatage des données initiales
For YY = 1 To 9
For XX = 1 To 9
V = Val(Cells(YY, XX)) 'Attention référence Excel
If V <> 0 Then
Call Raye(XX, YY, V)
End If
Next XX, YY
'Algorithme de résolution
Do
'cherche case avec qu'une valeur non rayée
Nbs = 0
For X = 1 To 9
For Y = 1 To 9
If C(X, Y, 0) 1 Then Nbs Nbs + 1: GoTo suite
s = 0
For t = 1 To 9
s = s + C(X, Y, t)
If C(X, Y, t) 0 Then V t
Next t
If s = 8 Then
Call Raye(X, Y, V)
Nbs = Nbs + 1
End If
suite:
Next Y, X
'Test si fini
If Nbs 81 Or MemNbs Nbs Then Exit Do
MemNbs = Nbs 'retient le NB S olution précédemment trouvé
'cherche si un seul élément est présent sur toute une ligne
'(et peut-être déjà utilisé pour les éliminations => répétition optimisable)
For Y = 1 To 9
For t = 1 To 9
k = 0
For X = 1 To 9
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then XX X
Next X
If k = 8 Then
Call Raye(XX, Y, t)
End If
Next t, Y
'cherche si un seul élément est présent sur toute une colonne
For X = 1 To 9
For t = 1 To 9
k = 0
For Y = 1 To 9
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then YY Y
Next Y
If k = 8 Then
Call Raye(X, YY, t)
End If
Next t, X
'cherche si un seul élément est présent dans un carré
For CX = 0 To 2
For CY = 0 To 2
For t = 1 To 9
k = 0
For X = CX * 3 + 1 To CX * 3 + 3
For Y = CY * 3 + 1 To CY * 3 + 3
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then XX X: YY = Y
Next Y, X
If k = 8 Then
Call Raye(XX, YY, t)
End If
Next t
Next CY, CX
Loop
'*-*-*-* Affichage de la solution
For X = 1 To 9
For Y = 1 To 9
For t = 1 To 9
If C(X, Y, t) 0 Then Cells(Y, X) t: Exit For
Next t
Next Y, X
If Nbs = 81 Then
MsgBox "résolu"
Else
MsgBox "solution multiple"
End If
End
End Sub
Sub Marque(ByVal X, ByVal Y, ByVal V)
'Marque Rayé tous les éléments de la case
'sauf pour pour l'élément portant la valeur V
'Variables générique de repérage
Dim t As Long
For t = 1 To 9
C(X, Y, t) = 1
Next t
C(X, Y, V) = 0
End Sub
Sub Raye(ByVal X, ByVal Y, ByVal V)
'Elimination des valeurs dans les cases suivant Y, X, Carré , lorsqu'on connait
'parfaitement une Case C(X,Y,V) => Application de la règle
'Variables générique de repérage
Dim XX As Long, YY As Long
Dim CX As Long, CY As Long
Dim t As Long
'Suivant l'ordonnée Y
For YY = 1 To 9
C(X, YY, V) = 1
Next YY
'Suivant l'abscisse X
For XX = 1 To 9
C(XX, Y, V) = 1
Next XX
'Suivant le carré
CY = (Y - 1) \ 3
CX = (X - 1) \ 3
For YY = CY * 3 + 1 To CY * 3 + 3
For XX = CX * 3 + 1 To CX * 3 + 3
C(XX, YY, V) = 1
Next XX, YY
'Marquage des valeur rayées de la case
For t = 1 To 9
C(X, Y, t) = 1
Next t
'Remet la valeur solution non rayé
C(X, Y, V) = 0
'Marquage indice 0 comme déjà utilisé pour gain de temps
C(X, Y, 0) = 1
End Sub
==
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 9 août 2005 à 08:47
Salut à tous !
* norgas
Je connais cette erreur pour l'avoir déjà rencontrée. Souvent, il faut recompiler le projet en vérifiant que la référence au Rey_SubClasser.dll et le composant ReyXp.ocx sont tous deux bien inscrits là où il faut (menu Projet de VB, respectivement Référence et Composants)
* Manpow
Merci pour le lien !
Cordialement,
Cacophrène
cs_manpow
Messages postés1Date d'inscriptionlundi 8 août 2005StatutMembreDernière intervention 8 août 2005 8 août 2005 à 17:01
Salut,
il m'était moi aussi venu à l'idée de faire un tel solveur, et force est de constater que je ne suis pas le premier !
J'ai également trouvé celui-ci qui est plutot pas mal :
http://sudoku.sourceforge.net/
norgas
Messages postés1Date d'inscriptionjeudi 14 août 2003StatutMembreDernière intervention 8 août 2005 8 août 2005 à 14:03
Bien joué et très joli, mais j'ai une erreur '429':le composant ActiveX ne peut créer l'objet...
Le composant est pourtant bien intégré dans le projet.
D'ou vient l'erreur ?
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 3 août 2005 à 23:01
Bonsoir,
Merci pour l'envoi. Mais hélas, il ne fonctionne pas encore... tant pis, c'est pas grave, je réadapterai ton programme un peu plus tard... Pour l'histoire du Exe retiré du Zip, je ne savais pas... enfin, maintenant, je sais... Merci BruNews...
A+
Us.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 3 août 2005 à 07:35
Salut à tous !
Ah, oui, c'est vrai ça, je viens de me souvenir qu'il est précisé que "tout exécutable sera supprimé lors de l'upload" quand on enregistre sa source... j'aurais dû y penser plus tôt. Bah en tout cas merci pour l'info BruNews.
BruNews
Messages postés21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 3 août 2005 à 00:19
EXE: pas une question de taille, c'est qu'on l'enlève des zips pour n'avoir aucune responsabilité en cas de transmission de virus. Il reste visible dans la liste car cette liste est générée au moment de la réception du zip, on corrigera cela à une prochaine MAJ du site.
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 2 août 2005 à 23:17
Bonsoir,
Pour le Exe c'est hélas toujours la même chose, mais je crois que c'est le site qui limite la taille... donc on n'y peut rien... Sinon par mon e-mail us_30@hotmail.com
Personnellement, je n'ai pas encore cherché ailleurs... Au brouillon, j'ai programmé la résolution avec les idées que j'ai tenté d'expliquer hier... Cela donne un algo composé avec beaucoup boucles imbriquées, mais bon cela me semble pas difficile... il faut juste ne pas se perdre dans les indices... J'essayerai de vous le proposer ici pour ce wek-end, si tout va bien...
A+
Us.
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 2 août 2005 à 20:42
Bonsoir !
Fin d'une journée remplie... j'ai trouvé pas mal de choses sur la résolution des grilles de sudoku. Subtiles et efficaces, sans nul doute. Mais bon ce n'est pas aussi simple que l'algorithme de rebroussement. Pour ma part, étant satisfait du résultat (au niveau rapidité s'entend), je n'envisage pas (ou très vraisemblablement pas) de programmer autre chose sur la question. Mais, bien entendu, le débat sur les autres programmations de la résolution de ce jeu m'intéresse toujours fortement !
Bonne programmation à tous,
Cacophrène
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 2 août 2005 à 14:08
Rebonjour !
Voilà, la journée avance, mes recherches aussi. D'abord, un très bon site anglophone où l'on retrouve les propositions abordées par us_30, et quelques autres :
Ensuite, pourquoi pas un tableau contenant une chaîne "123456789" que l'on ferait diminuer avec un Replace(élément, Empty) jusqu'à réduire la chaîne à un seul élément ? Je vais creuser dans cette direction.
A bientôt,
Cacophrène
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 2 août 2005 à 08:44
Bonjour à tous !
D'abord un grand merci à tous pour vos remarques.
* pit1
Pour les icônes, il faut aller sur le site WinCustomize.com. Tu trouveras des icônes en vrac ("Miscellaneous icons") ou des paquets d'icônes ("IconPackager").
* us_30
Il est vrai que l'algorithme de rebroussement n'est pas ce qu'on fait de plus subtil (même s'il est souvent utilisé). Les trois règles que tu énonces méritent fortement d'être testées, ce qui permettra de voir si elles sont suffisantes et quel gain de vitesse elles apportent (le rebroussement, quant à lui, est très rapide pour les grilles faciles, mais lent pour des grilles marquées "very hard" ou "fiendish" trouvées sur le Net).
Pour l'exe, je remets l'archive .zip avec l'exe... en espérant que ça marche, sinon je peux te l'envoyer par mail ou via MSN. Fais-moi signe si ça ne marche pas.
* crenaud76
Y aurait-il des idées d'algorithmes sur le Net ? Ou même juste un canevas ? Pour le moment, je n'ai encore rien trouvé... :-(
Bonne programmation à tous,
Cacophrène
crenaud76
Messages postés4172Date d'inscriptionmercredi 30 juillet 2003StatutMembreDernière intervention 9 juin 200628 2 août 2005 à 01:22
Us_30 Ta méthode de résolution me semble OK ! Il y a jus teun petit truc que tu n'as pas mentionner et qui est très important ... A partir du moment ou tu as trouver la valeur d'une Case de ta grille, cette valeur devient impossible pour toutes les autres case de la même ligne, de la même colonne et du même bloc de 9 cases. Avec cette méthode "de l'élimination" si je puis dire, il est clair que l'on peut résoudre presque toutes les grille de su doku, à l'exception de deux type de grille de su doku : Celles qui n'ont aucune solution (ben ouais, faut tout de même en parler de celle-ci !!) et celles qui mettent un poitn d'arrêt à notre methode d'élimination purement logique en proposant à un moment donnée n choix possible pour une case, sans qu'aucune méthode ne permette de définir avec certitude à l'avance laquelle est la bonne. Il faut alors "tester", une des valeur, et tenter de reprendre la méthode d'élimination logique. Si on bloque a grille, on revient au point ou on a fait un choix et on teste une autre valeur. Cela se codera très simplement avec une fonction récursive en fait!
Je travaille aussi sur un programme de Su Doku (dont le but n'est pas principalement de trouver la solution à une grille) mais plus de m'aider lorsqu'il y a justement n valeur possible a un instant T. mon soft enregistre tous les coups jouer sur la grille (en vérifiant leur validité au passage) et permet de revenir en arrière de X coups : une sorte de commande Undo façon Microsoft Office. Mais ce qui me plairait le plus c'est de pouvoir générer aléatoirement des grilles de Su Doku !!! Imaginer un peu ! On pourrait se faire des grilles, ce les échanger etc ... quant on sait que pour des Su doku de 9x9 il existe 6 670 903 752 021 0729 36 960 grilles valides, cela laisse réveur !!!
Mais mon souci est la !! Comment faire une grille valide ?? Ce que je sais faire, c'est générer les grilles finales (avec tous les chiffres en place), quel que soit la taille de la grille (4x4, 9x9, 16x16, 25x25 ou 36x36 pour ce qui concerne mon soft), et avec des nombre totalement aléatoire, sans me baser sur les techniques souvent employées de rotation, symétrie et autre substitution de nombre à partir de grilles de référence. Mais ! Car il y a un mais ! je ne toruve aucun algo valable qui permettrait de ne conserver que n nombre à des endroits stratégiques pour être certain d'avoir un su doku valide ! A part la méthode bourrain consistant à stopper mon générateur de grille complétée au bout de x nombres placés et de lancer ensuite le solveur pour vérifier l'unicité de la solution !!! Franchement pas plaisant !!! Je suis persuader que l'on peut trouver un algo qui fera le taff mais je butte encore ... J'ai lu que les grille s proposées par le Times et autres magazines au Japon (les grilles que nous avons en France sont toutes issu des éditions du Times !!) étaient faite à la main par les mecs !!! Je veux bien être gentil mais pas niais !!! Je n'y crois pas un instant !! Un Japonnais qui ne dégainerait pas son clavier pour résoudr eun problème comme ca ?? Je veux aps y croire !!!!!!!!
Alors si vous avez une piste sur le sujet ...
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 1 août 2005 à 21:58
Salut Cacaphrène,
J'ai un petit souci avec le téléchargement. Le EXE présent dans la liste, n'est pas dans le ZIP ? Cela me serais bien utile... peux-tu voir cela, en te remerciant d'avance...
IL y a seulement qlq jours que j'ai découvert le SUDOKU, dans le magazine Science et Avenir de ce mois, et je suis un peu comme Lucyberad, pris de vitesse... mais bon, vu la belle présentation, je ne pense pas faire si bien...
J'ai survolé le code, trés bien commenté au passage, et je me réserve pour faire des remarques lorsque j'aurais pu le voir en fonctionnement (avec le Exe)...
Néanmoins, si je comprends bien l'idée de résolution, c'est d'essayer (presque) toutes les valeurs possibles restantes, en regardant si elles sont cohérentes, sinon on essaye une autre (une valeur suivante)... Cela me semble un peu brute ! mais si le temps de résolution est raisonnable, alors pourquoi pas...
Personnellement, j'avais pensé (aprés mettre amusé à en résoudre à la main) de faire un algorithme qui suivrait ce que je faisais avec mon stylo.
J'explique. (c'est un peu compliqué, pour être clair, désolé...)
Fasse à la grille de départ, j'écris dans chaque case vide toutes les valeurs possibles; c.a.d. de 1 à 9. Puis, je raye les valeurs impossibles, suivant la règle du jeu. C'est à dire, en regardant colonne par colonne, je raye les valeurs déjà connues (donc données au départ). Même chose, ligne par ligne. Puis enfin, en regardant carré par carré de 9 éléments. IL est évident que tous le monde procéde ainsi au départ... C'est ensuite, que les chose deviennent plus intéressante... En effet, il faut trouver un (ou des) principe pour déduire une (ou des) nouvelle valeur, qui ne peut être dû au hasard. Là, j'ai trouvé le principe suivant, c'est tout simplement de regarder colonne par colonne, puis ligne par ligne, puis carré par carré, si parmis les éléments restants, il y en a un qui soit présent qu'une seul fois. Dans ce cas, c'est bien un nouvelle valeur valide. Ensuite, il convient de recommencer le procéssus. La seul question que je ne pose, c'est de savoir si ces 3 règles (pour faire simple) sont suffisantes... Pour l'instant, pour les qlq sudoku que j'ai fais cela fonctionne. JE suis tombé, sur un sudoku, possèdant deux solutions possibles, que je pu démontrer par cette même méthode... alors, bon...
Pour le programmer, je pensais attribuer un tableau de valeur de 9x9x9. En clair (X,Y,V) avec X=Y=V=9. X et Y correspondant à l'abscisse et à l'ordonnée du tableau et V pour les 9 valeurs possibles, en les marquants 0 ou 1, selon qu'ils sont rayés ou pas... Puis à programmer, les boucles correspondantes aux principes expliqués ci-dessus. (Un peu comme le principe du crible d'ératosthène, pour imager...)
Bon, bon... voilà je voulais faire court et pis me voilà encore à écrire des longueurs... A+
Amicalement,
Us.
cs_pit1
Messages postés32Date d'inscriptiondimanche 15 juin 2003StatutMembreDernière intervention17 janvier 2007 1 août 2005 à 21:53
Bravo pour la présentation, ou trouves-tu les icones?
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 1 août 2005 à 07:31
Merci pour ton commentaire Lucyberad.
Juste une précision pour ceux qui voudraient tester le programme. Vous devez avoir l'ocx de Renfield (il n'est pas inclu dans mon zip). Pour cela, allez voir la source http://www.vbfrance.com/code.aspx?id=6656
Merci à tous,
Cacophrène
Lucyberad
Messages postés414Date d'inscriptionmercredi 16 juin 2004StatutMembreDernière intervention26 juillet 20073 31 juil. 2005 à 23:49
ha merde, j'ai été pris de vitesse...
en ce moment dans le journal var-matin (haaa les vacances) page jeux il arrete pas d'en mettre et finalement en en fesant 2-3 j'ai vu que le resoudre etait d'une logique immanse, tout de suite m'est venu l'idée de faire un programme qui les resoud mais j'ai été pris de vitesse lol
de toute facon j'en était qu'as la mise en forme...
bon ben j'ai plus qu'as faire les "compte 99" et autre lol
j'ai quand meme regardé le code et il repond parfaiement aux exigence.
bravo
@+
Lucyberad
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 31 juil. 2005 à 13:22
Bonjour à tous !
Peut-être plus tard... un générateur de sudoku. Mais pas pour l'instant en tout cas.
29 févr. 2008 à 03:07
18 févr. 2008 à 18:32
j'aime bien le SuDoKu
23 juil. 2006 à 01:46
16 mai 2006 à 17:45
J'ai realisé un programme de résolution du Sudoku suivant la méthode "à la main".
Je résouds automatiquement 90% des Sudokus. Les 20% restants peuvent être résolus juste en intégrant dans la programmation un choix aléatoire d'un nombre(en suivant bien sûr toutes les contraintes).
Si quelqu'un veut des précisions....
20 mars 2006 à 09:29
Comme tu le dis, chaque méthode à ses avantages et ses inconvénients.
Pour moi la méthode des stratégies à aussi l'avantage de rester dans le domaine du casse-tête et d'une "résolution logique" du Sudoku, le casse-tête n'est plus le Sudoku, mais le programme qui le résoud. Ce que ne fait pas le rebroussement.
Egalement, c'est vrai que l'on ne peut pas prouver qu'une stratégie résout tous les Sudokus, à moins d'être très très fort, mais le rebroussement à le problème inverse, il ne peut pas prouver que l'on peut résoudre logiquement un Sudoku.
Je crois que ce sont deux visions différentes de l'application elle même. Le rebroussement permet de connaître la/les solutions d'un Sudoku. L'approche stratégie permet de savoir si l'on aurait pu résoudre ce Sudoku "à la main" en utilisant la même stratégie.
17 mars 2006 à 18:33
Voilà du temps libre, enfin, pour répondre à tous ces messages ! Voici ce que je pense de tout ce que j'ai lu :
1. La méthode du rebroussement (dite aussi retour-arrière ou backtracking), autrement dit la méthode employée dans mon programme, présente l'avantage de résoudre TOUTES les grilles de sudoku, et de donner, moyennant une modification mineure du programme actuel (QUI NE LE FAIT PAS !), TOUTES les solutions d'une grille. A cet avantage un inconvénient : le temps de calcul peut être assez long pour certaines configurations. Conclusion : méthode très pratique mais à utiliser avec modération.
2. Toutes les méthodes faisant appel à des stratégies plus ou moins fines. Elles ont un avantage CONSIDERABLE sur le rebroussement : elles sont toujours rapides ! Hélas, là encore, il y a un inconvénient : il peut être TRES DIFFICILE d'apporter la preuve que ces méthodes résolvent TOUTES les grilles et en donnent TOUTES les solutions. Conclusion : sauf à être fort en algorithmique, vous aurez du mal à démontrer que vos solveurs fonctionnent à tous les coups. N'oublions pas ce grand théorème : ce n'est pas parce que cela fonctionne dans tous les cas testés que cela fonctionne toujours. En maths, ce qui fonctionne toujours est au bas d'un raisonnement. Conclusion : à utiliser avec prudence !
Voilà tout.
Cordialement,
Cacophrène
12 mars 2006 à 14:01
Merci pour vos encouragements, pour vos remarques diverses (fonctionnement, le bug de la réinitialisation, etc...). Je n'ai que peu de temps en ce moment mais je corrige tout ça avec le retour du soleil ;-).
A bientôt,
Cacophrène
23 janv. 2006 à 22:52
function SolutionParEssais:boolean
begin
Identifie une case vide quelconque
pour chaque cas possible de cette case
tester si SolutionLogique
Arrêter si solution trouvée
end;
function SolutionLogique:boolean
begin
répéter tant que (Methode1>0) ou (Methode2>0) ou (Methode3>0);
si trouvé alors
Result = true
sinon
Result = SolutionParEssais
end;
6 janv. 2006 à 19:02
alors j'ai implementé si l'on peut un Solveur de sudoku que j'avai mi sur le site et qui a été desactivé car "trop de sudoklu", mais il resou TOUTES les grille qui sont possibles, et quand il ne peut peut plus resoudre par la logique, il fai des ipotheses. a l'origine en javascript, et d'ailleur toujours actuellement, car je n'ai fai que le rendre utilisable en vb.
je ne l'ai pas sou la main mais si ça vous interresse, vous pouvez dl un prog d'install fai pour un pote a l'origine http://zappiweb.free.fr/telech/install_sudoku.exe,
apres l'install, lorsque vous lancerez le prog, il va vou dirte fichier introuvable : allez voir dans le dossier d'insttall et il y sera !!
voila si vous voulez la source mailez moi !
gagou9[AT]gmail.com
21 déc. 2005 à 09:05
je viens de tester ton programme de Sudoku court et efficace. bravo
Néanmoins car il ya un mais, il me semble qu'il y a un petit problème dans la routine de reinitialisation que je reprends ici:
Private Sub cmdRéinitialiser_Click()
For iCompteur = 1 To 81 Step 1
With ttbCase(iCompteur)
Let .Text = Empty
Let .Font.Bold = False
Let .ForeColor = vbBlack
End With
Next iCompteur
End Sub
Ici tu reinitialise uniquement le contenu des cases et non les valeurs des variables Ichiffres, ce qui conduit à:
If iIndex = 0 Then
MsgBox "Le programme n'a pas pu trouver de solution à ce sodoku", vbExclamation, "Échec"
Call cmdRéinitialiser_Click
Exit Sub
End If
Il me semble qu'une reinitialisation de la valeur de iChiffres est necessaire pour relancer la resolution.
du type
Dim n as Integer
Private Sub cmdRéinitialiser_Click()
For iCompteur = 1 To 81 Step 1
With ttbCase(iCompteur)
Let .Text = Empty
Let .Font.Bold = False
Let .ForeColor = vbBlack
End With
iChiffres(iCompteur)=0
Next iCompteur
End Sub
A +
13 déc. 2005 à 12:50
0A0-000-000
0A0-000-000
0A0-000-000
0B0-000-000
0B0-000-000
0B0-000-000
000-000-000
000-CCC-DDD
000-000-000
Si on associe les valeurs des triades A et B, elles ont obligatoirement 4 et seulement 4 valeurs communes avec les triades C et D. Et je pense, (soupçonne) que cette info à de la valeur pour progresser en difficulté. Pour l'instant, je n'ai pas trouvé cette idée ailleurs sur le web, mais je n'ai pas trop cherché non plus. Peut-être aussi que ça n'apporte rien par rapport aux groupes (de 2, 3 ou 4), que c'est juste une autre façon d'attaquer le problème.
Bonne vacances. J'aurai peut-être un peu de temps moi aussi pendant les vacances pour revenir avec quelque-chose de plus concret.
13 déc. 2005 à 10:54
Effectivement on ne parlais pas de la même chose, l'approche est interressante, je vais essayer de creuser, pour voir si ça ouvre des voies non couvertes par les méthodes classiques.
Mais l'exemple que tu donnes est l'équivalent des méthodes classiques, "l'obligation" de présence est l'équivalent de la méthode des jumeaux ou triplets, c'est à dire, une valeur possible uniquement dans 2 ou 3 cases d'une même ligne ou colonne à l'intérieur d'une même région. On ne sait pas où mais on sait que la valeur est dans 1 de ces cases.
La propagation de l'information est faite implicitement par le "nettoyage" des valeurs possibles (dans ton exemple, on supprime le 3) dans les autres cases de la ligne ou colonne. Les "obligations" ou jumeaux/triplets des régions 1, 5 et 6 nettoies la région 4 et du fait du 3 en région 7, on se retrouve avec une valeur "isolée" pour le 3 dans la région 4.
Je vais partir en vacances à la fin de la semaine ... avec des grilles de sudoku, ça sera l'occasion de réfléchir à ta méthode; Il y a surement quelque chose de sympa à en sortir au niveau des algos de réduction des valeurs possibles.
12 déc. 2005 à 22:42
Je pense qu'on ne parle pas des mêmes triades. J'ai fureté rapidement, et je sais que certains se servent des cases comportant les mêmes solutions possibles, pour éliminer d'autres valeurs... je vois à quoi cela correspond par rapport à ma méthode manuelle et je ne veux pas approfondir, je ne voudrais pas tomber sur une solution toute faite :D Disons que je commence à me lasser des Sudoku. L'écriture de l'algorithme et du code pour les résoudre est un autre passe temps qui prolonge le plaisir, alors je fais durer. c'est pour cela que je me suis arrêter ici, parce que c'était à peu près le niveau ou j'étais arrivé.
Je parle des triades alignées. Les intersections entre une horizontale et une zone. Ou entre une verticale et une zone. En attaquant la réflexion par ces triades, on peux enregistrer des informations plus précises que sur une case seule. Disons, une information "floue" vu sous l'angle d'une case, mais qui permet de transporter des "obligations" vers d'autres triades.
000 000 000
000 000 000
000 000 000
000 000 000
000 XXX 000
000 000 000
000 000 000
000 000 000
000 000 000
Ici, Les zéros symbolisent des cases, les xxx symbolisent une triade.
Je tente un exemple d'information que l'on peux maîtriser en regardant les triades (je ne promets pas que dans mon exemple on ne puisse pas faire la même chose avec les méthodes classiques.
120?000?000
400?000?030
560?000?000
000?000?000
000?000?201
000?521?469
030?000?000
000?000?000
000?000?000
Regardez le 3 de la région en haut à droite. Il donne une information à la première triade horizontale de la zone juste en dessous : celle-ci doit (obligation) contenir un trois., même si je ne sais pas encore dans quelle case.
120?000?0C0
400?000?030
560?000?000
000?000?DDD : ici, je sais qui "doit" (D) y avoir un 3
000?000?2C1 : car ici, il ne peut pas y avoir de trois(C comme contrainte)
000?521?469
030?000?000
000?000?000
000?000?000
Donc, sur la même horizontale mais, sur la triade du centre, il ne peut pas y en avoir. C'est une contrainte (C)
120?000?000
400?000?030
560?000?000
000?CCC?DDD
000?DDD?201 : ici, maintenant au centre, la triade "doit" contenir un 3 !*
000?521?469
030?000?000
000?000?000
000?000?000
* Car les deux autres triades de la zone y renoncent.
En repartant du même principe, dans la zone tout en haut à gauche :
12D?000?000
4CD?000?030
56D?000?000
CCC?CCC?DDD
CCC?DDD?201
0CC?521?469
030?000?000
000?000?000
000?000?000
Il n'y a plus qu'une case disponible pour un 3 dans la zone de gauche, au centre.
C'est un exemple simple. Mais on arrive souvent dans les sudoku difficiles à savoir si une valeur doit être dans une triade ou si elle est contrainte. En faisant voyager ces informations, on peut résoudre des sudokus très difficiles. Par exemple ceux ou l'on n'a aucun exemplaire d'un chiffre...
J'espère que j'ai été assez clair et pas trop envahissant.
Si j'ai bien compris, JMSEBAUX, tu n'attaques pas par case mais par petites méthodes successives en reproduisant les méthodes manuelles ? Je penses qu'en agissant ainsi, tu progresse sûrement, mais lentement.. j'espère qu'avec mon principe je pourrai gagner du temps, mais je ne suis pas sûr qu'il soit aussi efficace. Et il sera surtout moins facilement évolutif si je dois rajouter des méthodes de comparaisons.
12 déc. 2005 à 11:12
Ce n'est pas suffisant, mais le principe est le bon. Il faut faire ca non seulement par région (carre de 9 cases) mais aussi par ligne et par colonne ou le même raisonnement s'applique. Quand tu l'aura fait pour 3 valeurs, il faudra aussi le faire pour 4.
Dans mon programme (http://www.vbfrance.com/code.aspx?ID=34358)j'ai impléménté la recherche de groupe de 3 cases ayant de 1 à 3 (idem pour 4) valeurs "isolées" (pas mélangées), en ligne colonne ou région (voir le site: http://www.mots-croises.ch/Manuels/Sudoku/).
Ca permet de bien "nettoyer" les valeurs possible dans les autres cases mais ça n'est pas suffisant pour ta grille par exemple.
Même si tu est sur MAC et que tu ne peut pas executer le prog tu peux toujours regarder les sources avec un simple éditeur de texte, comme ça tu pourra comparer tes algos avec ceux de cacophrene et les miens (fichier sudoku.bas)
Je pense rajouter "un jour ..." la recherche de groupe de (3 ou 4) valeurs "mélangées" qui permet de nettoyer les cases ou apparaissent ces valeurs. Mais a première vue ça n'est pas suffisant non plus pour ta grille.
L'autre algo que je pense rajouter est la recherche des positions dites "XY-Wing" (voir toujours sur le site http://www.mots-croises.ch/Manuels/Sudoku/)
bon courage et viens nous faire part de tes progrès.
10 déc. 2005 à 09:57
500000000
000000000
000000000
000000000
000050000
000000000
000000000
000000000
000000005
La question de la logique de l'ordinateur n'est pas en cause. Ce sont les principes de déduction plus poussés que les simples contraintes cases, lignes horizontales, lignes verticales, qui sont difficiles à programmer.
De mon côté, pas de progrès depuis que j'ai posté, mais je persévère.
PS : je suis arrivé sur votre forum par une recherche générique, et je ne m'étais pas aperçu qu'il s'agissait d'un forum VB. Je suis sur Mac et à ma connaissance, je ne peut pas tester vos exemples, Excusez-moi de cette intrusion. Si je trouve un code qui résout la grille dont je parle, j'essayerai de vous l'expliquer.
JMSebaux : comment oriente-tu ta recherche ? Si tant est que cela peut s'expliquer en quelques mots ? Je me suis orienté vers une travail sur les groupes de 3 cases, horizontales ou verticales, à l'intérieur d'un carré. Chaque triade faisant reporter sur les autres triades ( de sa case et de sa colonne(ou sa rangée) ses contraintes et déduisant des contraintes reçues quelles sont ces obligations. Ceci me permet (en théorie) de faire suivre plus d'informations que sur une approche par case... puisque je peut savoir qu'un 3 par exemple est dans une triade, sans savoir ou il se place vraiment. Grâce a cette infos, je peux dire à toutes les autres triades en relation qu'elles doivent abandonner le trois.
Je ne sais pas si le principe est suffisant, car j'attends là les limites de ma "conceptualisation" et j'ai beaucoup de mal à lier les bonnes triades entre elles.
A suivre...
6 déc. 2005 à 16:57
La grille proposeé par DDurandet est solvable
J'ai fait un programme suite à mon commentaire pour implémenter les algos dont je parlais.
il est là -> http://www.vbfrance.com/code.aspx?ID=34358
Il trouve une solution unique à cette grille.
Par contre avec les algos que j'ai implémenté il n'arrive pas encore à placer toutes les cases de manière purement déductive. Il faut utiliser le bouton "résoudre" (algo d'essai récursif) pour avoir la solution. Mais elle existe.
Je réfléchis a d'autre algo pour compléter la recherche déductive mais c'est pas facile et je n'y passe pas trop de temps ... je suis un peu faineant.
6 déc. 2005 à 14:27
Pas mal du tout ton prog et le visuel de la grille de jeu.
Je te met une très bonne note...
A plus! CMoiChris
6 déc. 2005 à 14:23
J'ai créé un Sudoku de toute pièce utilisant les "possibles" et les "pas possibles" (je mettrait le prog en ligne un peu plus tard). Malgré cela, la grille que tu nous soummet n'est pas faisable. Il manque des chiffres sur la grille...
Sinon on pourrait aussi résoudre ça???:
500000000
000000000
000000000
000000000
000050000
000000000
000000000
000000000
000000005
Si même une machine (avec une logique à priori sans faille) ne peut résoudre une telle grille, l'homme a un avantage sur elle, il esaye...
Alors pouquoi ne pas tenter "d'essayer" un chiffre et de voir si on peut compléter le grille?
Le prog que j'ai fait créé met les nombres "possibles" dans un .txt qui sert de "mémoire" pour le test des cases.
Mesdames, messieurs, à vos programmes... ;o)
A plus! CMoiChris
4 déc. 2005 à 15:31
En réponse a Lucyberad : à ma connaissance, le propos de JMsebaux est juste.
Les 3 principes que tu mets en avant ne sont pas suffisants pour résoudre des Sudoku de niveau extrême. Jusqu'à "difficile", la plupart du temps, ça passe, mais pas au delà. Et pourtant, avec de la logique et de la méthode on peut les résoudre et ils ont bien une solution unique.
Je le sais parce que j'ai pour l'instant un programme équivalent qui ne peut pas résoudre certains sudoku
Par exemple :
080070090
097040230
000109000
300000004
015090320
900000007
000803000
041050860
050020070
Ou le zéro symbolise les cases vides.
Si tu veux bien le tester et me dire que ton programme ne le résout pas, ça serait sympa. :-) S'il le résout, ça m'intéresse quand même, ça voudrait dire que j'ai une erreur de mon côté et que je dois retourner plancher.
En fait, j'essaye d'aller plus loin mais ça devient complexe. Il y a bien une donnée que l'on exploite pas dans
le principe que tu décris : c'est celui d'obligation.
Si une case possède plusieurs solutions possibles, mais que les autres cases de sa rangée, sa colonne ou son paquet ne peuvent pas fournir une des valeurs, alors la case est dans l'obligation de choisir ce nombre. Sur le même principe, si deux "mini" colonnes (colonnes à l'intérieur d'un paquet de "9") ne peuvent accueillir un nombre, cela crée une obligation de ce nombre dans la 3eme mini colonne, et cela même si on ne peut pas dire dans cette mini colonne ou se trouve exactement la valeur. Cette obligation crée a son tour une contrainte : la valeur ne peut pas se trouver dans les 2 mini colonnes des cases contiguës formant la verticale complète... C'est, je crois, ce que dit JMsebaux ici :
"En effet, arrivé à un certain stade de la grille (parfois dès le début) il n'y a plus de cases a placées par "choix". Mais par contre on arrive à déduire dans quelles case ne pas placer certaines valeurs. C'est ce que j'appele le "non choix".
Après une série de non choix on peut se retrouver dans des situations de "choix" et ainsi continuer à progresser vers la solution."
Pour l'instant, dans les mots pour moi, c'est clair. Reste plus qu'a en faire un code. Et là, c'est une autre paire de manche :)
27 nov. 2005 à 11:41
http://www.vbfrance.com/code.aspx?id=6656
@+
27 nov. 2005 à 11:38
est-ce que quelqu'un peux me dire comment faire pour créer une grille de sudoku en vb car moi j'arrive à ce que l'ordi choisis les numéro et les place dans chaque case de la grille mais je me retrouve tout le temp avec le même numéro dans une colone et ligne donc je voulais savoir comment faire pour une fois qu'il a choisi un numéro il le supprime des posibilité de ces choix mais qu'il le remé pour la ligne suivante...
merci d'avence
mokmap NC
16 nov. 2005 à 14:44
Merci d'avance pour vos réponses.
15 nov. 2005 à 21:52
15 nov. 2005 à 21:40
196627050475552913618075908526910000000000000000000000000000000000000000000000
14 nov. 2005 à 21:10
Un résolveur de Sudoku ! Quelle bonne idée! Je me suis mis à de jeu il n'y a pas très longtemps, et l'idée d'en faire un programme ne m'était pas encore venue. Maintenant, c'est trop tard ! :-)
Pour ta source, le code utilisé à l'air bon, c'est ultra bien expliqué, le seul problème est qu'il y a un bug (mineur sans doute) au niveau de l'ocx de l'excellent Renfield. (reyxp.ocx) Je lance le programme, et erreur 429: " le composant ne peut créer l'objet". Je ne m'y connait pas en activeX, j'ai pourtant enregistré les ocx (regsvr32) mais çà marche toujours pas...
Est ce qqun pourrait m'aider ?? Merci bcp !
Bonne continuation à tous, et d'avance bravo à Carcophène, même si je n'ai pas encore pu exécuter ta source !
@+
7 oct. 2005 à 12:19
proceder par elimination (ou non choix), a la main je les fait pareil quand c'est dur.
en fait le pricipe est simple:
le programe deja doit verifier si le sudoku est valide par le fait que le sodoku n'est pas sous contrainte (2 meme chiffre sur une ligne ou autre).
on regarde quelS chiffreS on peut mettre dans chaque case, des le depart.
donc apres on as forcement une case qui ne possede qu'un chiffre. on le pose et on elimine ce chiffre des possibilité de ceux de la ligne, la case et la collone. ceci fait, le sodoku vas etre resolu.
afin de determiner si il est resolvable, c'est tout simple, si aucune case ne possede un seul et unique choix, on estime alors que le sudoku est insolvable.
voici comment je resout les sudoku, hesitez aps a me dire si c as fonctionnel (en expliquant bien sur ^^).
Lucyberad
6 oct. 2005 à 09:13
Très bien pour programme. J'ai juste une petite remarque sur les conclusions qui sont "déduites" de la non résolution d'une grille par le programme. Vous concluez que la grille est soit impossible soit à solutions multiples.
En fait non, le raisonnement est trop simple. Il y a beaucoup de grilles qui sont à solution unique mais qui ne sont pas résolue par le programme. Car en fait vous avez oubliez des méthodes de résolution très importantes (mais très difficile à programmer).
Les méthodes que vous avez implémenter sont des méthodes de "choix" qui permette de placer aisément les cases à valeur unique ou les cases à valeurs "isolées" dans une ligne, colonne ou région. C'est déjà bien et ça permet de résoudre quasiment toutes les grilles de difficulté faciles et moyennes
Mais pour les grilles difficiles ou tres difficiles (et pourtant à solution unique) ces méthodes ne suffisent pas. Il faut alors appliquer des méthodes de "non choix".
En effet, arrivé à un certain stade de la grille (parfois dès le début) il n'y a plus de cases a placées par "choix". Mais par contre on arrive à déduire dans quelles case ne pas placer certaines valeurs. C'est ce que j'appele le "non choix".
Après une série de non choix on peut se retrouver dans des situations de "choix" et ainsi continuer à progresser vers la solution.
Il existe un site très bien fait qui expose clairement ces méthodes.
http://www.mots-croises.ch/Manuels/Sudoku/
avec beaucoup de grilles par niveau de difficulté pour s'exercer
http://www.mots-croises.ch/Sudoku.htm
Si vous arrivez à implémenter la méthode des jumeaux et triplets et des groupes isolés ou mélangés votre programme pourra résoudre une grande partie des grilles très difficiles et toujours de manière entièrement logique et sans retour en arrière après un "choix pour voir" entre 2 possibilités.
Encore merci pour le programme.
11 août 2005 à 21:14
...et je te renouvelle mes remerciements...
Amicalement,
Us.
11 août 2005 à 10:02
Il n'y a aucun problème, prends ce que tu veux tant que tu veux, si ça te convient ! C'est le principe même du site, et je crois que c'est aujourd'hui suffisamment rare - l'accès libre, l'entraide, la gratuité - pour qu'on cherche à le maintenir à tout prix ! Pour les icônes que j'ai utilisées, tu en trouveras bien d'autres sur WinCustomize.com. J'ai pris sur moi de t'envoyer un .rar avec les icônes que j'ai déjà téléchargées pour t'éviter de le refaire en espérant que cela te soit utile.
Bonne programmation,
Cacophrène
10 août 2005 à 18:32
En ce qui concerne des sites évoquant des idées permettant de gagner "un poil" du temps, je pense, comme toi que cela ne présente pas d'intérêt, à partir du moment qu'on estime que la résolution est assez rapide... Ce n'est qu'un p'tit jeu... Il est, pour ma part plus amusant de trouver un algorithme, que de jouer effectivement au sudoku... Je dirais même, qu'à partir du moment qu'on fait bien le tour du problème, le jeu perd tout son intérêt, puisqu'il se résume à une application simple et systématique des "3 règles" déjà évoquées... ET quand, je pense que j'ai vu des sites vendant des petits logiciels pour résoudre le Sudoku, misère... Finalement, rechercher une factorisation est de loin plus amusant ; come-back math !
Amicalement,
Us.
10 août 2005 à 17:42
Il fonctionne très bien. Très vite aussi. C'est une bonne idée de programmer ce qu'on fait soi-même à la main. Sinon, personnellement, j'en reste là. J'ai parcouru des sites où l'on discute de points plus précis (pour gagner une fraction de seconde, mais à vrai dire quel intérêt ?), mais je ne suis pas emballé. En tout cas, je l'ai dit et je le répète, bravo pour cet algorithme ! Il servira sûrement à ceux qui veulent faire un générateur...
Cordialement,
Cacophrène
10 août 2005 à 13:27
Us.
10 août 2005 à 13:12
Voici donc le code pour la résolution du sudoku, programmé sous Excel. La grille doit être écrite dans la plage A1:I9. L'algorithme suit assez fidèlement les étapes décrites l'autre jour. Je n'ai pas poussé trop loin les possibilités qu'on peut en retirer. Par exemple, on peut assez facilement s'en servir pour composer une grille. Ceci est rendu possible grâce à la connaissance des solutions dite "multiple". Pour faire trés simple, si on compose une grille qui n'a pas qu'UNE solution, alors le programme s'arrête et affiche les premiers nombres possibles (en fait non encore rayé). Il suffit alors de repérer une impossibilité (suivant la règle) et de choisir lequel retenir, puis de recommencer... Cette façon de faire pourrait être bien sur automatisée...
A propos de l'autre jour, j'ai maintenant la conviction, que les "3 règles" d'éliminations exprimées, sont suffisantes pour résoudre toute grille. Cette conviction me viens d'un raissonnement assez simple par absurde...
L'Algorithme que je te propose est encore optimisable, si bessoin... Mais au vu de la rapidité (moins de la seconde), je laissé tombé. C'est suffisant comme cela (quelque soit le niveau de difficulté de la grille)...
Maintenant, j'espère que tu pourras reprendre et complèter ton jeu... Pour ma part, peut-être que je finirais par déposer aussi une version...
Amicalement,
Us.
==
Option Explicit
'Tableau des cases avec les 9 valeurs par case
Public C(9, 9, 9) As Long
Sub Sudoku()
'*-*-*-* RESOLUTION DU SUDOKU *-*-*-*
'Variables générique de repérage
Dim X As Long, Y As Long, t As Long
Dim XX As Long, YY As Long, V As Long
Dim CX As Long, CY As Long
Dim Nbs As Long, MemNbs As Long, s As Long, k As Long
'Récupération et formatage des données initiales
For YY = 1 To 9
For XX = 1 To 9
V = Val(Cells(YY, XX)) 'Attention référence Excel
If V <> 0 Then
Call Raye(XX, YY, V)
End If
Next XX, YY
'Algorithme de résolution
Do
'cherche case avec qu'une valeur non rayée
Nbs = 0
For X = 1 To 9
For Y = 1 To 9
If C(X, Y, 0) 1 Then Nbs Nbs + 1: GoTo suite
s = 0
For t = 1 To 9
s = s + C(X, Y, t)
If C(X, Y, t) 0 Then V t
Next t
If s = 8 Then
Call Raye(X, Y, V)
Nbs = Nbs + 1
End If
suite:
Next Y, X
'Test si fini
If Nbs 81 Or MemNbs Nbs Then Exit Do
MemNbs = Nbs 'retient le NB S olution précédemment trouvé
'cherche si un seul élément est présent sur toute une ligne
'(et peut-être déjà utilisé pour les éliminations => répétition optimisable)
For Y = 1 To 9
For t = 1 To 9
k = 0
For X = 1 To 9
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then XX X
Next X
If k = 8 Then
Call Raye(XX, Y, t)
End If
Next t, Y
'cherche si un seul élément est présent sur toute une colonne
For X = 1 To 9
For t = 1 To 9
k = 0
For Y = 1 To 9
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then YY Y
Next Y
If k = 8 Then
Call Raye(X, YY, t)
End If
Next t, X
'cherche si un seul élément est présent dans un carré
For CX = 0 To 2
For CY = 0 To 2
For t = 1 To 9
k = 0
For X = CX * 3 + 1 To CX * 3 + 3
For Y = CY * 3 + 1 To CY * 3 + 3
k = k + C(X, Y, t)
If C(X, Y, t) 0 Then XX X: YY = Y
Next Y, X
If k = 8 Then
Call Raye(XX, YY, t)
End If
Next t
Next CY, CX
Loop
'*-*-*-* Affichage de la solution
For X = 1 To 9
For Y = 1 To 9
For t = 1 To 9
If C(X, Y, t) 0 Then Cells(Y, X) t: Exit For
Next t
Next Y, X
If Nbs = 81 Then
MsgBox "résolu"
Else
MsgBox "solution multiple"
End If
End
End Sub
Sub Marque(ByVal X, ByVal Y, ByVal V)
'Marque Rayé tous les éléments de la case
'sauf pour pour l'élément portant la valeur V
'Variables générique de repérage
Dim t As Long
For t = 1 To 9
C(X, Y, t) = 1
Next t
C(X, Y, V) = 0
End Sub
Sub Raye(ByVal X, ByVal Y, ByVal V)
'Elimination des valeurs dans les cases suivant Y, X, Carré , lorsqu'on connait
'parfaitement une Case C(X,Y,V) => Application de la règle
'Variables générique de repérage
Dim XX As Long, YY As Long
Dim CX As Long, CY As Long
Dim t As Long
'Suivant l'ordonnée Y
For YY = 1 To 9
C(X, YY, V) = 1
Next YY
'Suivant l'abscisse X
For XX = 1 To 9
C(XX, Y, V) = 1
Next XX
'Suivant le carré
CY = (Y - 1) \ 3
CX = (X - 1) \ 3
For YY = CY * 3 + 1 To CY * 3 + 3
For XX = CX * 3 + 1 To CX * 3 + 3
C(XX, YY, V) = 1
Next XX, YY
'Marquage des valeur rayées de la case
For t = 1 To 9
C(X, Y, t) = 1
Next t
'Remet la valeur solution non rayé
C(X, Y, V) = 0
'Marquage indice 0 comme déjà utilisé pour gain de temps
C(X, Y, 0) = 1
End Sub
==
9 août 2005 à 08:47
* norgas
Je connais cette erreur pour l'avoir déjà rencontrée. Souvent, il faut recompiler le projet en vérifiant que la référence au Rey_SubClasser.dll et le composant ReyXp.ocx sont tous deux bien inscrits là où il faut (menu Projet de VB, respectivement Référence et Composants)
* Manpow
Merci pour le lien !
Cordialement,
Cacophrène
8 août 2005 à 17:01
il m'était moi aussi venu à l'idée de faire un tel solveur, et force est de constater que je ne suis pas le premier !
J'ai également trouvé celui-ci qui est plutot pas mal :
http://sudoku.sourceforge.net/
8 août 2005 à 14:03
Le composant est pourtant bien intégré dans le projet.
D'ou vient l'erreur ?
3 août 2005 à 23:01
Merci pour l'envoi. Mais hélas, il ne fonctionne pas encore... tant pis, c'est pas grave, je réadapterai ton programme un peu plus tard... Pour l'histoire du Exe retiré du Zip, je ne savais pas... enfin, maintenant, je sais... Merci BruNews...
A+
Us.
3 août 2005 à 07:35
Ah, oui, c'est vrai ça, je viens de me souvenir qu'il est précisé que "tout exécutable sera supprimé lors de l'upload" quand on enregistre sa source... j'aurais dû y penser plus tôt. Bah en tout cas merci pour l'info BruNews.
3 août 2005 à 00:19
2 août 2005 à 23:17
Pour le Exe c'est hélas toujours la même chose, mais je crois que c'est le site qui limite la taille... donc on n'y peut rien... Sinon par mon e-mail us_30@hotmail.com
Personnellement, je n'ai pas encore cherché ailleurs... Au brouillon, j'ai programmé la résolution avec les idées que j'ai tenté d'expliquer hier... Cela donne un algo composé avec beaucoup boucles imbriquées, mais bon cela me semble pas difficile... il faut juste ne pas se perdre dans les indices... J'essayerai de vous le proposer ici pour ce wek-end, si tout va bien...
A+
Us.
2 août 2005 à 20:42
Fin d'une journée remplie... j'ai trouvé pas mal de choses sur la résolution des grilles de sudoku. Subtiles et efficaces, sans nul doute. Mais bon ce n'est pas aussi simple que l'algorithme de rebroussement. Pour ma part, étant satisfait du résultat (au niveau rapidité s'entend), je n'envisage pas (ou très vraisemblablement pas) de programmer autre chose sur la question. Mais, bien entendu, le débat sur les autres programmations de la résolution de ce jeu m'intéresse toujours fortement !
Bonne programmation à tous,
Cacophrène
2 août 2005 à 14:08
Voilà, la journée avance, mes recherches aussi. D'abord, un très bon site anglophone où l'on retrouve les propositions abordées par us_30, et quelques autres :
http://www.scanraid.com/sudoku.htm
Ensuite, pourquoi pas un tableau contenant une chaîne "123456789" que l'on ferait diminuer avec un Replace(élément, Empty) jusqu'à réduire la chaîne à un seul élément ? Je vais creuser dans cette direction.
A bientôt,
Cacophrène
2 août 2005 à 08:44
D'abord un grand merci à tous pour vos remarques.
* pit1
Pour les icônes, il faut aller sur le site WinCustomize.com. Tu trouveras des icônes en vrac ("Miscellaneous icons") ou des paquets d'icônes ("IconPackager").
* us_30
Il est vrai que l'algorithme de rebroussement n'est pas ce qu'on fait de plus subtil (même s'il est souvent utilisé). Les trois règles que tu énonces méritent fortement d'être testées, ce qui permettra de voir si elles sont suffisantes et quel gain de vitesse elles apportent (le rebroussement, quant à lui, est très rapide pour les grilles faciles, mais lent pour des grilles marquées "very hard" ou "fiendish" trouvées sur le Net).
Pour l'exe, je remets l'archive .zip avec l'exe... en espérant que ça marche, sinon je peux te l'envoyer par mail ou via MSN. Fais-moi signe si ça ne marche pas.
* crenaud76
Y aurait-il des idées d'algorithmes sur le Net ? Ou même juste un canevas ? Pour le moment, je n'ai encore rien trouvé... :-(
Bonne programmation à tous,
Cacophrène
2 août 2005 à 01:22
Je travaille aussi sur un programme de Su Doku (dont le but n'est pas principalement de trouver la solution à une grille) mais plus de m'aider lorsqu'il y a justement n valeur possible a un instant T. mon soft enregistre tous les coups jouer sur la grille (en vérifiant leur validité au passage) et permet de revenir en arrière de X coups : une sorte de commande Undo façon Microsoft Office. Mais ce qui me plairait le plus c'est de pouvoir générer aléatoirement des grilles de Su Doku !!! Imaginer un peu ! On pourrait se faire des grilles, ce les échanger etc ... quant on sait que pour des Su doku de 9x9 il existe 6 670 903 752 021 0729 36 960 grilles valides, cela laisse réveur !!!
Mais mon souci est la !! Comment faire une grille valide ?? Ce que je sais faire, c'est générer les grilles finales (avec tous les chiffres en place), quel que soit la taille de la grille (4x4, 9x9, 16x16, 25x25 ou 36x36 pour ce qui concerne mon soft), et avec des nombre totalement aléatoire, sans me baser sur les techniques souvent employées de rotation, symétrie et autre substitution de nombre à partir de grilles de référence. Mais ! Car il y a un mais ! je ne toruve aucun algo valable qui permettrait de ne conserver que n nombre à des endroits stratégiques pour être certain d'avoir un su doku valide ! A part la méthode bourrain consistant à stopper mon générateur de grille complétée au bout de x nombres placés et de lancer ensuite le solveur pour vérifier l'unicité de la solution !!! Franchement pas plaisant !!! Je suis persuader que l'on peut trouver un algo qui fera le taff mais je butte encore ... J'ai lu que les grille s proposées par le Times et autres magazines au Japon (les grilles que nous avons en France sont toutes issu des éditions du Times !!) étaient faite à la main par les mecs !!! Je veux bien être gentil mais pas niais !!! Je n'y crois pas un instant !! Un Japonnais qui ne dégainerait pas son clavier pour résoudr eun problème comme ca ?? Je veux aps y croire !!!!!!!!
Alors si vous avez une piste sur le sujet ...
1 août 2005 à 21:58
J'ai un petit souci avec le téléchargement. Le EXE présent dans la liste, n'est pas dans le ZIP ? Cela me serais bien utile... peux-tu voir cela, en te remerciant d'avance...
IL y a seulement qlq jours que j'ai découvert le SUDOKU, dans le magazine Science et Avenir de ce mois, et je suis un peu comme Lucyberad, pris de vitesse... mais bon, vu la belle présentation, je ne pense pas faire si bien...
J'ai survolé le code, trés bien commenté au passage, et je me réserve pour faire des remarques lorsque j'aurais pu le voir en fonctionnement (avec le Exe)...
Néanmoins, si je comprends bien l'idée de résolution, c'est d'essayer (presque) toutes les valeurs possibles restantes, en regardant si elles sont cohérentes, sinon on essaye une autre (une valeur suivante)... Cela me semble un peu brute ! mais si le temps de résolution est raisonnable, alors pourquoi pas...
Personnellement, j'avais pensé (aprés mettre amusé à en résoudre à la main) de faire un algorithme qui suivrait ce que je faisais avec mon stylo.
J'explique. (c'est un peu compliqué, pour être clair, désolé...)
Fasse à la grille de départ, j'écris dans chaque case vide toutes les valeurs possibles; c.a.d. de 1 à 9. Puis, je raye les valeurs impossibles, suivant la règle du jeu. C'est à dire, en regardant colonne par colonne, je raye les valeurs déjà connues (donc données au départ). Même chose, ligne par ligne. Puis enfin, en regardant carré par carré de 9 éléments. IL est évident que tous le monde procéde ainsi au départ... C'est ensuite, que les chose deviennent plus intéressante... En effet, il faut trouver un (ou des) principe pour déduire une (ou des) nouvelle valeur, qui ne peut être dû au hasard. Là, j'ai trouvé le principe suivant, c'est tout simplement de regarder colonne par colonne, puis ligne par ligne, puis carré par carré, si parmis les éléments restants, il y en a un qui soit présent qu'une seul fois. Dans ce cas, c'est bien un nouvelle valeur valide. Ensuite, il convient de recommencer le procéssus. La seul question que je ne pose, c'est de savoir si ces 3 règles (pour faire simple) sont suffisantes... Pour l'instant, pour les qlq sudoku que j'ai fais cela fonctionne. JE suis tombé, sur un sudoku, possèdant deux solutions possibles, que je pu démontrer par cette même méthode... alors, bon...
Pour le programmer, je pensais attribuer un tableau de valeur de 9x9x9. En clair (X,Y,V) avec X=Y=V=9. X et Y correspondant à l'abscisse et à l'ordonnée du tableau et V pour les 9 valeurs possibles, en les marquants 0 ou 1, selon qu'ils sont rayés ou pas... Puis à programmer, les boucles correspondantes aux principes expliqués ci-dessus. (Un peu comme le principe du crible d'ératosthène, pour imager...)
Bon, bon... voilà je voulais faire court et pis me voilà encore à écrire des longueurs... A+
Amicalement,
Us.
1 août 2005 à 21:53
1 août 2005 à 07:31
Juste une précision pour ceux qui voudraient tester le programme. Vous devez avoir l'ocx de Renfield (il n'est pas inclu dans mon zip). Pour cela, allez voir la source http://www.vbfrance.com/code.aspx?id=6656
Merci à tous,
Cacophrène
31 juil. 2005 à 23:49
en ce moment dans le journal var-matin (haaa les vacances) page jeux il arrete pas d'en mettre et finalement en en fesant 2-3 j'ai vu que le resoudre etait d'une logique immanse, tout de suite m'est venu l'idée de faire un programme qui les resoud mais j'ai été pris de vitesse lol
de toute facon j'en était qu'as la mise en forme...
bon ben j'ai plus qu'as faire les "compte 99" et autre lol
j'ai quand meme regardé le code et il repond parfaiement aux exigence.
bravo
@+
Lucyberad
31 juil. 2005 à 13:22
Peut-être plus tard... un générateur de sudoku. Mais pas pour l'instant en tout cas.
Cordialement,
Cacophrène