# Is there an algorithm which solves the puzzle game Mummy Mystery?

I had the puzzle board game Mummy Mystery from Maze Ways (a version of the game GoGetter) as a kid, and just out of curiosity I tried my hand at making a computer program which will generate solutions to any of the individual puzzles included with it. For those not familiar with the game: it consists of nine tiles, each depicting the segments of a pathway, and a 3x3 grid with various characters drawn on the outside edges. The goal of each puzzle is to arrange the tiles on the grid, in any order and orientation, so that certain characters are connected via complete pathways (and sometimes the goal is to avoid connecting them). In the classical version of the game, there are no 'dead ends' allowed; the pathway can't simply stop in the middle of the grid and not be continued on the adjacent tile. Some versions will contain other unique features, but this is the basic premise.

Does anyone know of an algorithm which is able to help solve this type of puzzle, or a similar one, in a time-efficient way? I think I'm close to finding a way of generalizing the puzzle which might allow it to be solved, but it involves assigning prime numbers to each pair of nodes and dealing with massive numbers which probably aren't compatible with my computer. I have a very basic understanding of group theory, but I'm unsure how it could be used to help in this situation.

There's a very simple polynomial time algorithm: you try placing the tiles in all possible positions and orientations, and see whether each one achieves the goal. When you find one that does, you stop. This is an O(1) algorithm. The constant (which is larger than $$9! \cdot 9^4$$, which is simply the number of possible position-orientation layouts, and doesn't assign any time for checking what's connected to what) is large, but that's life.