Quelle est la meilleure façon de résoudre ce genre de jeu?

Question

Ce soir, j'ai essayé de résoudre un puzzle en bois alors je me demandais quelle est la meilleure façon de trouver une solution à ce genre de problème programmatique. Le but est de combiner un ensemble de solides (comme des pièces de tetris en trois dimensions) ensemble pour former une forme de manière réalisable qui tient compte du fait que les pièces peuvent être attachées ou glissées dans la structure seulement si elles s'adaptent le genre de mouvement (ignore les rotations, seulement 90 ° de tours).

Vérifiez this image pour comprendre ce que je veux dire.

Answer 1

Dans ma dernière classe CS, nous avons créé un solveur de puzzle générique fonctionnant en ayant des états représentés en tant qu'objets en C++. Chaque objet avait une méthode pour comparer l'état qu'il représentait à un autre état. Cela a été utilisé pour la mémo, afin de déterminer si les états avaient déjà été vus. Chaque état avait également une méthode pour générer des états directement accessibles à partir de cet état (c'est-à-dire faire tourner un bloc, placer un bloc, déplacer un bloc). Le solveur a travaillé en maintenant une file d'états, en faisant apparaître un état au début de la file d'attente, en vérifiant si c'était l'état désiré (c'est-à-dire résolu). Sinon, la mémo (nous avons utilisé un ensemble haché) a été vérifiée pour voir si l'état avait déjà été vu. Sinon, les états accessibles à partir de l'état actuel ont été générés et ajoutés à l'arrière de la file d'attente. Une file vide signalait un casse-tête insoluble.

Il serait difficile de conceptualiser quelque chose comme ça pour la 3D, mais c'est l'approche de base de la résolution informatisée de casse-tête.

Answer 2

Comme c'est un problème plus ou moins petit car pour un ordinateur il y a un petit nombre de combinaisons possibles, j'essaierais un algorithme de recherche simple. Je veux dire un algorithm qui vérifie toutes les configurations possibles et qui continue du résultat de cette configuration jusqu'à ce qu'il finisse dans une configuration finale, dans votre cas le cube.

Le problème semble être d'écrire un programme qui est capable de faire tous les contrôles d'état et les transformations d'un état à un autre. Parce que vous devez voir si la configuration est physiquement possible.

Answer 3

Apparaît comme un sous-ensemble plus facile d'un problème d'empaquetage en trois dimensions polyomino. Il y a plusieurs scholarly papers sur ce sujet.

Answer 4

Si le casse-tête que vous voulez gérer est celui de la photo que vous avez liée, alors il est probablement possible de simplement chercher dans un arbre des solutions possibles jusqu'à ce que vous trouviez votre chemin vers le bas. Si chaque pièce du puzzle est un nombre de cubes attachés à leurs faces, et je dois résoudre le puzzle en insérant chaque pièce dans un plus grand cube, 4 fois sur chaque bord comme les cubes de composition, alors je procéderais comme suit.

Déclarez un cube arbitraire de chaque pièce comme origine. Observez qu'il y a 24 rotations possibles pour chaque pièce du puzzle, une orientation pour chaque face possible du cube d'origine vers le haut, 4 fois les rotations possibles autour de l'axe vertical dans cette position. Tentative d'élimination de l'espace de recherche en recherchant les orientations possibles produisant la même pièce finale, si une rotation donnée, suivie d'une translation du cube d'origine vers l'un des autres cubes de la pièce, donne exactement la même occupation volume comme une rotation précédemment considérée, retirez cette rotation de la considération future.

Retirez un morceau du sac. S'il n'y a pas de pièces dans le sac, alors c'est une solution. Boucle à travers chaque cellule du volume de la solution, et chaque rotation de la pièce tirée pour chaque cellule.Si la pièce est complètement à l'intérieur du volume de recherche et ne chevauche aucun autre morceau, revenez dans ce paragraphe. Sinon, passez à la rotation suivante, ou s'il n'y a plus de rotations, passez à la cellule suivante, ou s'il n'y a plus de cellules, revenez sans solution.

Si le dernier paragraphe revient sans solution, alors le puzzle était insoluble.