Accueil > > > TOUS LES SUDOKU DU MONDE
TOUS LES SUDOKU DU MONDE
Information sur la source
Description
Ce code illustre une nouvelle fois la récursivité. Il se charge de calculer tous les sudoku possibles selon ce que vous lui donnez en entrée. Si vous ne lui donnez rien, il se "contentera" de vous sortir toutes les grilles de sudoku existantes (oui oui, les 6'670'903'752'021'072'936'960. grilles possibles ! enfin, soyons franc, votre PC risque fortement d'être à court de mémoire avant que vous n'en voyez la couleur !). Le tout tient en moins de 80 lignes de code... vive la récursivité (la source est abondamment détaillée). En moyenne, il lui faut 0.2 secondes pour résoudre une grille diabolique... Je l'ai laissé tourner pendant une heure et demie sur mon PC, j'ai recu 2 000 000 de solutions...ce qui prend 1.52 Go (il y a une option pour enregistrer les solutions dans un fichier). Bonne lecture du code !
Source
- Private Sub Solver(Grille_A_Solver() As Long)
- 'Fonction récursive principale : elle prend en paramètre une grille et cherche à la remplir.
- 'L'idée de base est d eprocéder par petits pas :
- 'Cette fonction cherche UN emplacement vide.
- 'Si elle n'en trouve pas, la grille passé en paramètre est déjà complète : parfaite.
- 'Si elle en trouve un, elle essaie successivement d'y placer les nombres de 1 à 9. Si elle peut placer par exemple un 1, elle s'auto appelle alors avec une grille un peu moins vide.
- 'De proche en proche, on obtien finalement une grille parfaitement remplie..et seules les combinaisons qui ont une probabilité d'être vraies sont testées.
-
- 'Pour un très bon tutorial sur la récursivité : (sous formes d'algorithmes)
- 'http://www.siteduzero.com/tuto-3-23774-1-la-recursivite.html
-
-
- Dim i As Long, j As Long, k As Long, Case_Etait_Vide As Boolean
-
- 'Si on a une solution et que l'on en a demandé une seule, c'est terminé !
- If Termine And Not (AfficherToutesSoluces) Then Exit Sub
- NBIterations = NBIterations + 1
-
- 'i,j => parcourent le tableau
- 'k parcourt les nombres de 1 à 9
- 'Case_Etait_Vide indique si on a effectué une opération sur le tableau
- Case_Etait_Vide = False
- For i = 1 To 9
- For j = 1 To 9
- If Grille_A_Solver(i, j) = 0 Then
- 'C'est une case vide, on va tenter de la remplir
- For k = 1 To 9
- If Try_To_Add(Grille_A_Solver, k, i, j) Then 'Si on a le droit d eplace k à l'emplacement i,j
- 'Remplir la grille avec ce nombre, et la passer en paramètre à Grille_A_Solver.
- Grille_A_Solver(i, j) = k
- Solver Grille_A_Solver()
- 'Puis la remettre à zéro pour la suite.
- Grille_A_Solver(i, j) = 0
- End If
- Next
- Case_Etait_Vide = True: Exit For
- End If
- Next
- If Case_Etait_Vide Then Exit For
- Next
-
- 'Si on a jamais trouvé de case vide, c'est fini !
- If Case_Etait_Vide = False Then
- NBSolutions = NBSolutions + 1
- AfficherSolution "TERMINE !!!! (Delta T = " & Int((Timer - Debut) * 100) / 100 & "s - Solution n°" & NBSolutions & ", cas traités : " & NBIterations & ")", Grille_A_Solver
- Termine = True
- DoEvents
- End If
- 'Debug.Print NBIterations
-
- End Sub
Private Sub Solver(Grille_A_Solver() As Long)
'Fonction récursive principale : elle prend en paramètre une grille et cherche à la remplir.
'L'idée de base est d eprocéder par petits pas :
'Cette fonction cherche UN emplacement vide.
'Si elle n'en trouve pas, la grille passé en paramètre est déjà complète : parfaite.
'Si elle en trouve un, elle essaie successivement d'y placer les nombres de 1 à 9. Si elle peut placer par exemple un 1, elle s'auto appelle alors avec une grille un peu moins vide.
'De proche en proche, on obtien finalement une grille parfaitement remplie..et seules les combinaisons qui ont une probabilité d'être vraies sont testées.
'Pour un très bon tutorial sur la récursivité : (sous formes d'algorithmes)
'http://www.siteduzero.com/tuto-3-23774-1-la-recursivite.html
Dim i As Long, j As Long, k As Long, Case_Etait_Vide As Boolean
'Si on a une solution et que l'on en a demandé une seule, c'est terminé !
If Termine And Not (AfficherToutesSoluces) Then Exit Sub
NBIterations = NBIterations + 1
'i,j => parcourent le tableau
'k parcourt les nombres de 1 à 9
'Case_Etait_Vide indique si on a effectué une opération sur le tableau
Case_Etait_Vide = False
For i = 1 To 9
For j = 1 To 9
If Grille_A_Solver(i, j) = 0 Then
'C'est une case vide, on va tenter de la remplir
For k = 1 To 9
If Try_To_Add(Grille_A_Solver, k, i, j) Then 'Si on a le droit d eplace k à l'emplacement i,j
'Remplir la grille avec ce nombre, et la passer en paramètre à Grille_A_Solver.
Grille_A_Solver(i, j) = k
Solver Grille_A_Solver()
'Puis la remettre à zéro pour la suite.
Grille_A_Solver(i, j) = 0
End If
Next
Case_Etait_Vide = True: Exit For
End If
Next
If Case_Etait_Vide Then Exit For
Next
'Si on a jamais trouvé de case vide, c'est fini !
If Case_Etait_Vide = False Then
NBSolutions = NBSolutions + 1
AfficherSolution "TERMINE !!!! (Delta T = " & Int((Timer - Debut) * 100) / 100 & "s - Solution n°" & NBSolutions & ", cas traités : " & NBIterations & ")", Grille_A_Solver
Termine = True
DoEvents
End If
'Debug.Print NBIterations
End Sub
Conclusion
Just enjoy it !
Historique
- 14 avril 2008 16:34:44 :
- Correction de mini-problèmes graphiques
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Transfert de Données [ par guilloo ]
Salut, je travaille sur une appli qui doit pouvoir transmettre des données (mbd access) via Internet mais mes employeurs (je suis en stage) ne veulent
Besoin d'aide!! Avez vous la solutions ?? [ par spliter ]
Pouvez-vous m'aider, mon projet a un bog et je ne comprend pas pourquoi. J'ouvre un fichier .txt que j'ai créer et je le lis (au début je n'es rien de
récursivité en vb [ par fouesoft ]
salut,je cherche à programme la fonction factorielle en récursif ... comment faire pour la condition d'arrêt en vbfouesoft
MSFLEXGRID EXCEL [ par KC62 ]
Bonjour a tous ! en cette belle journée ensoleilléMa question est simple coment transferer le contenu dune MSflexgrid vers un fichier excel ! si vs av
SOS media 9 + durée d'un media [ par KC62 ]
bonjour a tous voila mon souci est media 9. je sais 'est de la folie de gérer sa mais bon, petit challenge perso...je voudrais savoir comment récupére
EXCEL + VBA + MATRICE, besoin de lastuce du jour [ par KC62 ]
slt a tous ! je developpe une appli pour un magasin de vetement. je cherche a simplifié la saisi des articles et de leur stock. ainsi en saisissant la
Solutions d'une equations du 3ème degré. [ par lesdentsduweb ]
Bonjour !!Y'a-t-il un solveur sur VB pour résoudre une équation du 3ème degré.C'est à dire à partir des coefficients a,b,c,d de l'équation ax3 + bx² +
VB + excel + graphique [ par KC62 ]
Salut a tous ! Je cherche a générer des graphique dans une form a partir d'un tableau ( celui-ci récupéré dun base SQL) Jusqu'au tableau sa c'est géré
Do events ? kesako sa ? [ par KC62 ]
Salut a tous ! Dans un but d'appronfondir clairement ma culture VB. je cherche qq'1 qui pourrait m'expliquer ce que le do Events fair exactement ? dan
probleme avec une combobox [ par airfox ]
bonjour, Je viens de commencer en VB et j'ai un probleme avec une combobox. explication : dans ma combobox j'ai un choix à faire entre plusieu
|
Derniers Blogs
IMAGINE CUP 2012, MAKE A SIGN EN FINALEIMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg
Voilà qui est fait, la nouvelle est officielle ! L'équipe belge "Make a Sign" va au pays des kangourous défendre son projet dans la catégorie Software Design. http://www.imaginecup.com/CompetitionsContent/Competition/WorldwideFinalists.aspx V...
Cliquez pour lire la suite de l'article par junarnoalg KINECT 1.5 IS OUT !KINECT 1.5 IS OUT ! par Vko
La version 1.5 du Kinect For Microsoft vient tout juste de sortir ! Plein de nouveautés: Tracking de squelette en Near Mode Détection en position assise Détection faciale avec un SDK dédié Documentation et des guideline (enfin) Un out...
Cliquez pour lire la suite de l'article par Vko LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc
Mise à jour des Web API du 14 Mai
Réservez dès maintenant votre journée du 20 juin pour le Windows Azure Dev Camp 2012 à Paris
Mise à jour de Team Foundation Service
MechCommander 2 sur Windows 8
Entity Framework 5 Release Candidate e...
Cliquez pour lire la suite de l'article par richardc REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITERREACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc
Une mauvaise utilisation de rx lors de l'écriture d'une couche d'accès à des services peut conduire à des cas embarassants avec des erreurs mal gérées, des appels qui ne partent lorsqu'ils le devraient, et même des résultats incorrects . le tout nuis...
Cliquez pour lire la suite de l'article par Groc SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVESSHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg
Dernièrement, nous avons migré le site
myTIC
vers un nouveau serveur SharePoint 2010. Dans les contenus que nous vouloins récupérer, nous avions un certain nombre de blogs.
Nous avons utilisé les commandes Power...
Cliquez pour lire la suite de l'article par junarnoalg
Forum
RE : DATAREPORTRE : DATAREPORT par cmarcotte
Cliquez pour lire la suite par cmarcotte
Logiciels
sDEVIS-FACTURES vlPRO (8.1.0.3)SDEVIS-FACTURES VLPRO (8.1.0.3)sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa... Cliquez pour télécharger sDEVIS-FACTURES vlPRO 974 Application Server (12.2.4.6)974 APPLICATION SERVER (12.2.4.6)Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc... Cliquez pour télécharger 974 Application Server vPicture (1.4.2.1)VPICTURE (1.4.2.1)Avec vPicture, hébergez vos images facilement et rapidement.
vPicture est un utilitaire simple, ... Cliquez pour télécharger vPicture Easy-Planning (2.2.1.6)EASY-PLANNING (2.2.1.6)Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au... Cliquez pour télécharger Easy-Planning COM-BACKUP (2.0)COM-BACKUP (2.0)
COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...
Cliquez pour télécharger COM-BACKUP
|