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  

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).

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.

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 )

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.

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

 
Oui    
 

 
Oui tu peux (mais lent ). 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 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é ).
 
Apres c'est un exercie pour l'utilisation des files/piles je pense.
 

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

Les meilleurs algo ne font quasi pas de brute force. Mais les mecs bossent dessus depuis longtemps.
 
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.

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.    

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

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

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