Forum Programmation.ruby algorithme de force brute

bonjour,

je suis en train de travailler sur un sujet de programmation en Ruby de façon à me faire la main sur le langage.

Le sujet porte sur un puzzle comportant 3x3 pièces. J'ai mis en place les classes : Piece, Puzzle, Tas, Solver ainsi que toutes les méthodes permettant de manipuler le puzzle.

Chaque pièce est composée de 4 faces qui doivent être jointives 2 à 2. Sur chaque face, une partie d'un animal est dessiné en relief : soit la partie supérieur (tête), soit la partie inférieure. Il y a 4 sortes d'animaux : coccinelle, sauterelle (grillon), araignée, abeille.

Sauf erreur de ma part, la combinatoire est d'environ 9!*4, soit 1451520.

Quelques infos en vrac :

• Les cases du puzzle sont numérotées de 1..9 pour les z'humains et de 0..8 pour mon logiciel
• Les pièces recevront des valeurs numériques de 0 à 8 pour représenter les figurines animales
• Les pièces s'assembleront paire à paire : (0,1), (2,3), (4,5), (6,7)
• Le puzzle est numéroté de cette façon :

 0 1 2
 3 4 5
 6 7 8

Pour résoudre le puzzle, il faut replacer les pièces dans un certain ordre et faire en sorte que les parties hautes et basses s'assemblent.

J'ai réalisé 2 solveurs :

• le premier est purement aléatoire et n'a aucun intérêt, si ce n'est de documenter l'API,
• le second est semi-aléatoire :
  • je choisis une pièce aléatoire dans le tas pour laquelle j'applique une rotation aléatoire
  • puis, je remplis successivement les cases 1, 3, 5, 7 en calculant les contraintes de placement, puis en choisissant une pièce au hasard dans la liste des possible,
  • je répète ensuite l'opération avec les coins : cases 0, 2, 6, 8.

Conclusion :

• mon algorithme semi-aléatoire me permet de découvrir que le puzzle n'a qu'une seule solution avec 4 variantes (liées à la rotation du l'ensemble du puzzle), cela reste tout de même à confirmer,
• c'est pour cela que je souhaite réaliser une méthode de balayage systématique.

Je n'arrive pas très bien a voir comment réaliser ce balayage. Les paramètres sont les suivants :

• en entrée : tas, puzzle,
• en sortie les puzzles résolus,
• les variants : angle de rotation des pièces et ordre dans lequel les pièces sont disposées dans sur le puzzle.

Habituellement, cela se réalise avec une belle fonction récursive, dans laquelle on embarque tous les paramètres et on agit sur les variants. Je sèche. L'objet de ce message est aussi d'échanger sur Ruby, algorithmique. L'objet de ce message n'est pas d'avoir une solution toute faite, mais plutôt d'obtenir des pistes de réflexion.

Liens :

• voici le code source et la doc : https://github.com/mqu/divers/tree/master/puzzle

bien à vous.