What is the optimal solution to a 3 Hexagon "Game"

Question

I recently created a "game" in java that involves three hexagons placed in a triangle formation with each hexagon sharing two sides. If this is unclear I will try and include a picture for reference.

The game has a random four of thirteen unique vertices highlighted and the goal is to shift the highlighted vertices either clockwise or counterclockwise along the hexagons to the four locations where a vertex is shared by more than one hexagon.

I would like to add a feature that shows the optimal pathing for the vertices to reach the winning state but have not been able to come up with anything that works well. Would anyone be able to point me in the right direction?

My game for reference

Answer 1

Following the strategy described by mathmandan, all positions can be solved, and I get the following results:

$$\begin{array}{c|c} \text{Moves} & \text{Positions} \\ \hline 0 & 1 \\ 1 & 6 \\ 2 & 24 \\ 3 & 93 \\ 4 & 231 \\ 5 & 269 \\ 6 & 85 \\ 7 & 6 \end{array}$$

The 'hardest' positions requiring $7$ moves are $(2, 6, 7, 8)$ and $(2, 6, 9, 13)$ and the rotations/reflections of these positions (using the numbering system in the image in the OP's original post). If we label the three hexagons:

 A
B C

and let '$+$' and '$-$' mean 'rotate clockwise' and 'rotate counter-clockwise', resp., then to solve $(2,6,7,8)$ you can use the sequence of moves:

B+ A+ B- C- B- A- A-

To flesh out mathmandan's method a little at OP's request:

First, every position can be uniquely identified by a $4$-tuple $(a,b,c,d)$ with $0 < a < b < c < d \leq 13$. There are ${13 \choose 4} = 715$ such $4$-tuples. We will use these tuples as keys into a dictionary that will keep track of how to get from one position to another (tuples are immutable in python, so that's convenient!).

Each of the $6$ possible moves corresponds to some cyclic permutation of $6$ elements of $\{1,2,...,13\}$. For example, the permutation I call $B+$ can be written (in the usual permutation cycle fashion) $(5,4,10,8,9,7)$. And $B-$ is simply the reverse of that: $(7,9,8,10,4,5)$.

So if we are in position $(1,4,7,8)$, and we apply $B+$, then as an intermediate step, we get $(1,10,5,9)$. The $1$ is left alone; and each of the other numbers is replaced by the next value to the right in the cycle (and we wrap around at the end so $ 7 \rightarrow 5$).

But then recall that all our positions must have $a<b<c<d$; so we must sort the result. Then when apply $B+$ to $(1,4,7,8)$, we get $(1,5,9,10)$. So code up a function that takes a position and any of the $6$ cyclic permutations and returns the position after the move.

Now given a position $p = (a,b,c,d)$, we can make a list of the $6$ 'neighbors' of $p$. Actually, note that it may not always be exactly $6$ neighbors - because if we apply either of $B+$ or $B-$ to, say, $(1,2,3,6)$, we get $(1,2,3,6)$; and we don't really want to have a position be it's own neighbor. So we can code up a function $findNeighbors(p)$ that returns a list of the distinct neighbors of $p$.

The next step is to build a dictionary that will tell us how many moves it takes to get from any position $p = (a,b,c,d)$ to the 'home' position $(3,4,5,10)$. Here's some (untested!) code in python that assumes you've already implemented the $findNeighbors$ function elsewhere:

positionDict = {}
level = 0
levelPositions = [(3,4,5,10)] # start with the home position
while True:

    # mark the positions for this level by adding them to the dictionary
    for p in levelPositions:
        positionDict[p] = level

    # find which neighbors are one move further than this level
    nextLevelPositions = []
    for p in levelPositions:
        for neighbor in findNeighbors(p):
            if neighbor not in positionDict:
                # we haven't visited this position yet
                if neighbor not in nextLevelPositions:
                    # and nobody else in this level has marked it yet, so..
                    nextLevelPositions.append(neighbor) 

    if len(nextLevelPositions)==0:
        # we are done
        break

    levelPositions = nextLevelPositions
    level += 1

Okay, so much for the preparations! Now that we have that dictionary, you can find an optimal path from $p$ to the home position without much work.

First, loop over each of the 'moves' $A+, A-, B+,...$ and find the one that, when applied to $p$, yields a position $pNext$ with the lowest value of $positionDict[pNext]$; that's the next move to make. Then let $p = pNext$, and then keep repeating this process until you reach the home position (i.e., until $positionDict[p] = 0$).

I actually optimized a bit in a few places and stored the 'best move' for each position while building the $positionDict$, but the above will get you there.

In closing, this is a very handy technique to have in your toolbelt. With different definitions of 'position' and 'findNeighbors', you can use it to navigate from one place to another in a maze, or to speedily traverse a tree-like data structure, and so on.

Answer 2

If I've understood the game correctly, there are $\binom{13}{4} = 715$ possible game states, since there are $13$ vertices and $4$ of them must always be highlighted. It shouldn't be too hard to just solve the game from each one of those possible states (using a computer, probably, and assuming the game is always solvable!).

Abstractly, you could make a graph with $715$ vertices and an edge from one vertex to another whenever there is a move between the corresponding states. Clearly the "winning" state vertex requires $0$ moves to win. Then, all of its neighbors require exactly $1$ move to win. All of their neighbors (except the winning vertex, which was already determined) require $2$ moves, and so forth until you don't have any neighbors left.

If you reach all of the vertices in this fashion, then the game is always solvable, and you can recover the optimal solution from each game state (vertex), by reading its required number of moves, and always moving to a neighbor with one fewer required move.

If, on the other hand, you exhaust all the neighbors but you still have vertices left unsolved, then it means that there are some states which are unsolvable. This would mean that your "state graph" was disconnected.