Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
863 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Sudoku et recherche en largeur/profondeur

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Sudoku et recherche en largeur/profondeur

n°1457084
frankie_fl​owers
Posté le 14-10-2006 à 00:34:00  profilanswer
 

Salut,
 
J'ai comme TP d'Intelligence Artificielle le travail suivant :
 
Programmer la résolution d'une grille de sudoku (9*9 pour commencer), en utilisant une recherche en largeur puis une recherche en profondeur.
 
Je pense avoir compris le concept de recherche en largeur/profondeur.
Pourtant je ne vois absolument pas comment l'appliquer au problème du Sudoku.
 
Arrêtez moi si je me trompe :  
Pour pouvoir parler de largeur ou profondeur, il faut pouvoir représenter les différents états d'une grille sous forme d'un arbre de profondeur > 2.
Or je ne vois pas comment construire un arbre des etats du Sudoku, si ce n'est un arbre de profondeur 1, avec la grille de départ en noeud père, et toutes les grilles remplies possibles en noeuds fils.
 
A moins que l'on puisse faire un arbre avec des noeuds représentant des grilles incomplètement remplies  :??:  Mais comment construire et parcourir cet arbre  :??:

mood
Publicité
Posté le 14-10-2006 à 00:34:00  profilanswer
 

n°1457088
Giz
Posté le 14-10-2006 à 01:04:36  profilanswer
 

Imagine l'arbre de solution du sudoku c'est à dire TOUTES les grilles réalisables en feuilles...il y en a une bonne chier ;). Maintenant tu pars d'une grille vide (c'est la racine de ton arbre). Ensuite tu construis ses fils c'est à dire TOUTES les grilles ayant exactement une valeur de fixée...l'ensemble de ces grilles se situe à la profondeur 1 donc. Pour la recherche en largeur il faut donc que tu génères et que tu stockes en mémoire TOUTES les grilles de profondeur n avant TOUTES les grilles de profondeur n+1.
La recherche en profondeur part d'un côté de l'arbre, par exemple à gauche et génére tous ses fils avant de passer aux noeuds de profondeur inférieure.
Pour le parcours :
- largeur d'abord : tu dépile le noeud parent puis tu empiles les fils. A la prochaine itération, tu dépile par le bas.
- profondeur d'abord : tu dépile le noeud parent puis tu empiles les fils. A la prochaine itération, tu dépile par le haut (normalement quoi).


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
n°1458111
frankie_fl​owers
Posté le 16-10-2006 à 16:12:00  profilanswer
 

Donc dans mon cas je prends comme racine de l'arbre la grille remplie avec quelques numeros ("l'enoncé" ).
Ensuite je construis l'arbre, jusqu'à ce que j'arrive a la profondeur où toutes les cases sont remplies.
 
C'est ça ?
 
C'est seulement a ce moment que je verifie la validité des grilles ?
D'autre part il n'y a pas besoin de vérifier si un état existe déjà dans l'arbre du fait que le nombre de cases remplies est différent pour chaque profondeur.

Message cité 2 fois
Message édité par frankie_flowers le 16-10-2006 à 16:12:38
n°1458172
MagicBuzz
Posté le 16-10-2006 à 16:59:22  profilanswer
 

C'est pas un peu bourrin comme méthode pour résoudre le Sudoku ça ?
 
J'ai bossé quelques heures sur un algo un peu plus naturel (qui reprend la même démarche que l'homme). Il est incomplet -il résoud que les "facile"-, mais je dirais "vite fait là comme ça" que j'utilise genre 500 octets en mémoire à tout péter, et que je suis 1000 fois plus rapide (à 10^2 près je pense ;))

Message cité 1 fois
Message édité par MagicBuzz le 16-10-2006 à 16:59:53
n°1458319
sircam
I Like Trains
Posté le 16-10-2006 à 20:36:20  profilanswer
 

Même avec un ignoble backtracking, ça file à toute vitesse. Utiliser des algos genre "dancing links" et toussa, je pense pas que ça change quoi que ce soit pour résoudre une grille (usage "normal" ).
 
Bah, c'est un TP, le but c'est de manipuler l'une ou l'autre structure de données. [:spamafote]


---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
n°1458653
MagicBuzz
Posté le 17-10-2006 à 12:45:23  profilanswer
 

Ben moi mon truc c'est pour faire une appli PDA, ça change tout si j'ai besoin que de 1 Mo de mémoire et 90% de CPU en moins ;)

n°1459174
Giz
Posté le 17-10-2006 à 22:31:47  profilanswer
 

frankie_flowers a écrit :

Donc dans mon cas je prends comme racine de l'arbre la grille remplie avec quelques numeros ("l'enoncé" ).
Ensuite je construis l'arbre, jusqu'à ce que j'arrive a la profondeur où toutes les cases sont remplies.
 
C'est ça ?


 
Oui  :jap:  
 

frankie_flowers a écrit :

C'est seulement a ce moment que je verifie la validité des grilles ?


 
Oui tu peux (mais lent :o). Le backtracking te permet de couper une branche de l'arbre dès qu'une contrainte ne peut être satisfaite. En clair, il stoppe la recherche en profondeur du chemin en exploration (celui que l'on creuse) dans l'arbre et passe au chemin voisin (le prochain à droite ... si on fait la recherche en profondeur de gauche à droite). Au lieu de générer "bêtement" une grille (les fils) et vérifier si une contrainte n'est pas violée, on peut construite directement les bons fils...si cet ensemble est vide, alors la branche en cours de "creusage" est abandonnée...et on creuse le chemin voisin. Une bonne résolution du sudoku réside dans le codage du problème (utiliser les bonnes structures de données), pas vraiment dans l'algorithme (y'a pas 36000 sortes d'algo pour ce problème, à part le backtracking....il n'y a pas d'heuristique intéressante à ma connaissance sur ce problème :/).
 

frankie_flowers a écrit :

D'autre part il n'y a pas besoin de vérifier si un état existe déjà dans l'arbre du fait que le nombre de cases remplies est différent pour chaque profondeur.


 
Dans ce problème un état ne peut pas être égal à un de ses prédécesseur. Par conséquent, tu ne peux pas cycler si c'est ce que tu veux dire ; au fur et à mesure que tu creuses, tu ajoutes un chiffre sur ta grille.


---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3
n°1459572
MEI
|DarthPingoo(tm)|
Posté le 18-10-2006 à 14:34:43  profilanswer
 

MagicBuzz a écrit :

C'est pas un peu bourrin comme méthode pour résoudre le Sudoku ça ?
 
J'ai bossé quelques heures sur un algo un peu plus naturel (qui reprend la même démarche que l'homme). Il est incomplet -il résoud que les "facile"-, mais je dirais "vite fait là comme ça" que j'utilise genre 500 octets en mémoire à tout péter, et que je suis 1000 fois plus rapide (à 10^2 près je pense ;))


Les meilleurs algo en C resoude ça bien plus rapidement que ça methode (car j'ai deja fait ça en TP et avec le pilage/depilage & co j'etait genre 100 000 fois plus lent que le meilleur avec liste chainé :D).
 
Apres c'est un exercie pour l'utilisation des files/piles je pense.
 


---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
n°1459573
MEI
|DarthPingoo(tm)|
Posté le 18-10-2006 à 14:36:00  profilanswer
 

frankie_flowers a écrit :

Donc dans mon cas je prends comme racine de l'arbre la grille remplie avec quelques numeros ("l'enoncé" ).
Ensuite je construis l'arbre, jusqu'à ce que j'arrive a la profondeur où toutes les cases sont remplies.
 
C'est ça ?
 
C'est seulement a ce moment que je verifie la validité des grilles ?
D'autre part il n'y a pas besoin de vérifier si un état existe déjà dans l'arbre du fait que le nombre de cases remplies est différent pour chaque profondeur.


En principe, si t'arrives à la fin, ta grille est forcement bonne. Apres tu peut reverifier, mais rien que ça c'est pas si simple. ;)
 
Apres tu peut faire une version multisolution, mais attention au cas ou l'on met que des cases vides ;)


---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
n°1459577
MEI
|DarthPingoo(tm)|
Posté le 18-10-2006 à 14:40:14  profilanswer
 

Giz a écrit :

Oui  :jap:  
 
 
 
Oui tu peux (mais lent :o). Le backtracking te permet de couper une branche de l'arbre dès qu'une contrainte ne peut être satisfaite. En clair, il stoppe la recherche en profondeur du chemin en exploration (celui que l'on creuse) dans l'arbre et passe au chemin voisin (le prochain à droite ... si on fait la recherche en profondeur de gauche à droite). Au lieu de générer "bêtement" une grille (les fils) et vérifier si une contrainte n'est pas violée, on peut construite directement les bons fils...si cet ensemble est vide, alors la branche en cours de "creusage" est abandonnée...et on creuse le chemin voisin. Une bonne résolution du sudoku réside dans le codage du problème (utiliser les bonnes structures de données), pas vraiment dans l'algorithme (y'a pas 36000 sortes d'algo pour ce problème, à part le backtracking....il n'y a pas d'heuristique intéressante à ma connaissance sur ce problème :/).
 
 
 
Dans ce problème un état ne peut pas être égal à un de ses prédécesseur. Par conséquent, tu ne peux pas cycler si c'est ce que tu veux dire ; au fur et à mesure que tu creuses, tu ajoutes un chiffre sur ta grille.


Les meilleurs algo ne font quasi pas de brute force. Mais les mecs bossent dessus depuis longtemps. :D
 
Sinon une bonne optimisation est de calculer les chiffres candidats de chaque case et de les ordonner par nombre de candidats croissant. Ensuite quand on les traitent ils y aura beaucoup plus vite des solutions ecartées. Par contre je sais pas trop si le temps de reordonnement est long ou pas.


---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
mood
Publicité
Posté le 18-10-2006 à 14:40:14  profilanswer
 

n°1459606
sircam
I Like Trains
Posté le 18-10-2006 à 14:57:20  profilanswer
 

MagicBuzz a écrit :

Ben moi mon truc c'est pour faire une appli PDA, ça change tout si j'ai besoin que de 1 Mo de mémoire et 90% de CPU en moins ;)


Un backtracking bourrin ne va pas forcément prendre un temps signficativement plus élevé qu'un algo plus fin. Il se peut même qu'il consomme moins d'espace mémoire. Je ne parle pas de cette solution "basique" avec des arbres cependant.   [:pingouino]  


---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
n°1459617
masklinn
í dag viðrar vel til loftárása
Posté le 18-10-2006 à 15:10:18  profilanswer
 

MEI a écrit :

Les meilleurs algo ne font quasi pas de brute force.


Ca c'est sûr. Habituellement, ils utilisent des approches multiples successives e.g. http://users.pandora.be/vandenberg [...] ?how2solve


Message édité par masklinn le 18-10-2006 à 15:12:24

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
n°1461042
frankie_fl​owers
Posté le 20-10-2006 à 01:33:58  profilanswer
 

Bon en fait comme j'ai pas de PC en ce moment, j'ai laissé mes collègues faire le TP en java :D
Je vais essayer de poster ce qu'ils ont fait si y'en a que ça intéresse.

n°1461379
Trap D
Posté le 20-10-2006 à 14:21:10  profilanswer
 

Pour ceux que ça pourrait intéresser, il y a eu une longue discussion sur le Sudoku ici : http://www.developpez.net/forums/s [...] hp?t=54373


Message édité par Trap D le 20-10-2006 à 14:22:45

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Sudoku et recherche en largeur/profondeur

 

Sujets relatifs
moteur de rechercheHashMap recherche optimisée?
recherche sur disque durComment inserer un petit moteur de recherche ?
Moteur de recherche Imposer une methode Equals pour une recherche dans une List
Faire une seule recherche de 2 types de chaine de caractèreZone de liste - largeur des colonnes
recherche de données dans excel sans ouvrir les fichiers 
Plus de sujets relatifs à : Sudoku et recherche en largeur/profondeur


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR