Discussion :

[Eldergrim]

Bonjour,

Je cherche à écrire un petit programme pour résoudre les problèmes/puzzles de type hashi (voir ici si vous ne connaissez pas).

J'avais commencé en implémentant des règles que nous, humains, appliquons, et ça fonctionne jusqu'à un certain point. Mais pour certains qui sont plus difficiles au bout d'un moment il faut faire une supposition et aller voir plus loin si c'était un choix valide.
C'est là que le backtracking est sensé entrer en jeu.

J'arrive à appliquer ce type d'algo sur un problème comme le sudoku mais pas pour hashi. Soit mon programme se termine avant, soit il ne se termine pas du tout. Et à debuguer c'est difficile à cause de la récursivité.

Quelqu'un aurait-il déjà fait cet exercice ? Si oui j'aimerais bien un petit coup de main.

Merci d'avance

[Flodelarab]

Bonjour

Pour le sudoku, comme pour hashi, je fais tous les cas possibles. Pourquoi ne fais-tu pas cela ?

Quand à la récursivité, je ne te dis pas tout le mal que je pense d'elle. Seuls les mathématiciens aiment la récursivité.

[Eldergrim]

Pour le sudoku, tester tous les cas possibles revient à tester 1, 2, 3, etc jusque 9. Tous les cas sont relativement faciles à identifier.

Pour le hashi, tel que je comprends l'algo de backtracking, pour un nœud N un cas c'est une combinaison des x liens possibles avec les y voisins.
Ça me parait un peu complexe de devoir faire la liste de tous les cas possibles pour chaque nœud.

Est-ce que je comprends bien cette histoire ? Autrement dit, est-ce que le test à faire à chaque itération c'est bien de tester une combinaison complète pour un nœud ?

[dourouc05]

Es-tu sûr de la qualité de tes "règles humaines" ? Cette technique de retour en arrière est principalement prévue pour reconsidérer des choix posés précédemment (en remontant dans un arbre), mais il faut qu'ils soient enregistrés comme tels… Pour le Sudoku, tu appliques des règles de logique pour imposer de nouveaux chiffres, avec la certitude que ces déductions sont correctes : as-tu les mêmes propriétés ? Sinon, il vaut mieux tout considérer comme une supposition (choisie intelligemment par ces règles, certes), chaque nœud correspondant à une telle supposition (vraie d'un côté, fausse de l'autre, avec un arbre binaire, en toute généralité).

[Eldergrim]

Salut,

A priori les règles de déduction que j'ai appliquées sont correctes. Leur vérification est basée sur leur résultat, mais je n'ai pas constaté d'erreurs pour le moment.
Cependant dans certaines situations ces règles ne suffisent pas à trouver une solution. Il faut aller voir plus loin (des coups futurs) pour savoir si on tombe dans une impasse ou sur une solution.
J'aurais pu écrire plus de règles, mais c'est assez fastidieux et ça fait beaucoup de code à écrire.

C'est pour cette raison que je me suis tourné vers le backtracking, qui lui est sensé essayer toutes les possibilités et ramener la bonne (ou la première bonne qu'il trouve).
Dans un premier temps de manière brute sans affiner les choix grâce aux règles dont je parlais plus haut. C'est sensé marcher aussi, même si c'est plus long.
La difficulté que j'ai est d'identifier pour un nœud toutes les possibilités. Pas tellement de les vérifier, les règles du jeu sont assez simples. Mais bien de les lister.

Si on prend l'exemple du sudoku, à un moment dans l'algo on a une boucle qui va de 1 à 9 qui représente l'ensemble des possibilités pour une cellule.
Dans mon cas, le hashi, je sais pas sur quoi faire ma boucle.

De ce fait je suis en train de tenter une autre approche. Boucler sur les liens potentiels et les vérifier. J'ai juste peur que ça fasse beaucoup d'appels récursifs et que je rencontre une erreur technique avant d'avoir un résultat. J'imagine que je pourrais passer cet algo en itératif, mais je ne suis pas très à l'aise avec ces manipulations.
Je vais commencer par des petits problèmes pour valider le fonctionnement.

Tout avis/conseil/remarque est le/la bienvenu(e)

[Flodelarab]

Voici une approche qui me semble possible:

Tu fais une liste L des liens possibles en absolu.
Puis une liste X des liens qui s'excluent mutuellement.

Tu prends L et tu considères la quantité de chaque lien à 0.
Les valeurs possibles sont:

• -1: impossible
• 0: indéterminé
• 1: 1 lien
• 2: 2 liens

Tu pointes sur le premier lien de L.

1. Tu incrémentes la quantité de ton lien en court.
2. Tu passes à -1 tous les liens suivants étant exclus par ton lien et X.
3. Si cela n'est pas cohérent (numéro dans l'un des ronds dépassé), tu remontes au lien précédent (valide, c'est-à-dire différent de -1), en n'oubliant pas de remettre les liens à -1 à leur valeur précédente.
4. Si cela est cohérent, tu passes au lien suivant (valide, c'est-à-dire différent de -1) et tu reprends à l'opération 1.

Quand tu sors de la liste L par le bas, avant de valider, tu vérifies que le nombre de liens distribués est égal au nombre de liens que tu attends (et connais). Sinon, il faut reprendre l'exploration.

Quand tu sors de la liste L par le bas, tu as fini et trouvé une solution qui marche.
Quand tu sors de la liste L par le haut, tu as fini et le problème n'a pas de réponse valide.

L'avantage est que tu fais tous les cas possibles. Pas d'oubli. Et au fur et à mesure, tu construis une éventuelle solution.
L'inconvénient est que tu fais tous les cas possibles. Le temps de traitement peut devenir un problème pour une grille immense.

[dourouc05]

Si on prend l'exemple du sudoku, à un moment dans l'algo on a une boucle qui va de 1 à 9 qui représente l'ensemble des possibilités pour une cellule.
Dans mon cas, le hashi, je sais pas sur quoi faire ma boucle.

Justement, je ne l'implémenterais pas comme ça . Il me paraît plus logique (approche de type programmation par contraintes) d'avoir, pour chaque case, un ensemble de valeurs possibles, c'est-à-dire qui incluent déjà toutes les déductions possibles (il y a déjà un 4 dans la ligne, inutile de tester cette valeur). Ainsi, quand tu crées ton arbre, tu fais autant de nœuds que de valeurs possibles pour la case sur laquelle tu décides de brancher (ou bien seulement deux : imposer une telle valeur d'un côté, la retirer de l'ensemble des valeurs considérées de l'autre).

Ici, tu pourrais effectuer un branchement sur un lien à créer du puzzle et créer trois nœuds dans l'arbre de recherche : zéro, un ou deux ponts (voire moins en exploitant des déductions).

L'inconvénient est que tu fais tous les cas possibles. Le temps de traitement peut devenir un problème pour une grille immense.

En fait, ça ne m'étonnerait pas que ton algorithme ait une complexité en temps dans le pire cas optimale : le Sudoku est déjà dans la classe de complexité NPC (http://math.stackexchange.com/questi...le-np-complete), donc pas d'algorithme qui, dans le pire cas, n'a pas une complexité exponentielle — en gros.

(e) Apparemment, à en croire Wikipedia, on a le même genre de résultat pour les jeux de Hashi : https://en.wikipedia.org/wiki/Hashiwokakero.

@Eldergrim : ça peut te donner une autre idée pour résoudre le problème (trouver des cycles hamiltoniens). Bon, la transformation n'est probablement pas si simple que ça (vive la théorie de la complexité !), mais tu as des algorithmes "efficaces" pour trouver ces cycles hamiltoniens (https://en.wikipedia.org/wiki/Hamilt...lem#Algorithms).

[Eldergrim]

Hello,

En fait j'en étais arrivé à la conclusion que j'allais essayer avec les 3 états que tu cites: 0, 1 ou 2 pour un lien. Ca devrait fonctionner, même si ça peut difficilement être pire en termes d'optimisation.
J'avais pensé à limiter le nombre de valeurs possibles à chaque noeud (grâce à une intelligence en fonction du contexte) si je rencontre un problème de performance. Je ne sais pas encore quel niveau d'exigence je dois atteindre.

Pour ce qui est des cycles hamiltoniens, je n'en suis pas encore à ce niveau de connaissance théorique. Ne brûlons pas les étapes . Mes cours de facs sont relativement lointains et les notions de complexité sont devenues floues avec le temps.

Dès que j'ai réussi à faire tourner le truc correctement je vous tiens au courant.
En tous cas je suis content que des gens compétents aient pris le temps de me répondre sur ce forum. Je pense que je repasserai sous peu avec d'autres problèmes.

[Eldergrim]

Bonjour,

Quelques nouvelles en ce fort agréable vendredi (pas à cause de la pluie, juste parce que c'est vendredi).
En suivant vos conseils j'ai réussi à enfin implémenter et faire fonctionner correctement mon algo de backtracking.
J'ai décidé de boucler sur les liens et d'utiliser les 4 états suggérés par Flodelarab.
Rapidement, avec la taille des problèmes qui augmente, les perfs se sont révélées très insuffisantes pour passer les tests qui doivent être passés.

J'ai donc commencé à mettre en place une étape préliminaire pour simplifier le problème avant de lancer le backtracking.
Cette étape préliminaire est constituée de plusieurs tests sur des cas particuliers, qui limitent les choix possibles pour certains liens.
Il me reste des cas à gérer, mais d'ores et déjà 12 cas sur 13 passent en moins d'une seconde.

Par contre le 13ème je l'ai laissé tourner 45 minutes et pas de résultats (une grille de 24 * 24). Mais en tous cas la démarche semble bonne. Je vais continuer à mettre en place les cas particuliers qui manquent.
Ca aurait été pas mal d'utiliser les tests préliminaires en cours de backtracking aussi, mais j'ai l'impression que le rollback va devenir compliqué à gérer.

[dourouc05]

!

mais j'ai l'impression que le rollback va devenir compliqué à gérer.

Et si tu sauves dans ton arbre d'exploration la solution courante ? Ça devrait être tout pour continuer. Quand tu te rends compte qu'une branche est foireuse, tu libères des parties de l'arbre et reprends une solution à explorer. (Implémentation assez simple, pas exceptionnelle niveau mémoire, selon la manière de stocker ta solution…)

[Eldergrim]

Bonjour,

Finalement je n'ai pas eu à faire les tests "intelligents" en cours de backtracking. Il a suffit que j'en applique quelques uns supplémentaires avant et le tour fut joué.
En tous cas c'était assez formateur comme exercice.

Merci pour votre aide.