1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Thanks, I guess what I was going for was a time efficient and not a polynomial time algorithm. That number is large, and if my computer can do 1000 iterations per second, it will still take almost a month to complete a full analysis. I'm aware that there are much faster computers out there, but my question was more about a convenient way to generalize the puzzle which will provide an instantaneous solution. $\endgroup$
    – Ramanujan1729
    Nov 27, 2019 at 23:23
  • 1
    $\begingroup$ I would assume that "polynomial time" would refer to a variant where the size of the grid is not fixed. $\endgroup$
    – Eric Wofsey
    Nov 27, 2019 at 23:24
  • $\begingroup$ Right, I was originally planning to generalize this to larger grids. I'll edit the question. $\endgroup$
    – Ramanujan1729
    Nov 27, 2019 at 23:44
  • $\begingroup$ @Ramanujan: it's not a polynomial time algorithm, and John Hughes is being disingenuous to claim that it is. Polynomial in what? In a constant? If that's your criterion, John, then it's also an exponential-time algorithm, isn't it? $\endgroup$
    – TonyK
    Nov 27, 2019 at 23:51
  • 1
    $\begingroup$ You might be interested in reading about Donald Knuth's "Algorithm X". It can be adopted to solve a wide range of similar problems. en.wikipedia.org/wiki/Knuth%27s_Algorithm_X $\endgroup$
    – awkward
    Nov 28, 2019 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .