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)

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

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