# Rolling tetrahedra

The image below depicts a number of tetrahedral dice sporting face colors of red, yellow, blue, and green in a consistent orientation. These dice exist on a triangular tessellation of the plane, and at any time they may move to any adjacent triangle by rolling over onto the appropriate face. They may never be moved or reoriented by any other procedure.

Your goal is to move the dice to the colored circles (all of which are currently visible) in such a way that the colors match. Moreover, you must do this in the minimum number of moves possible.

• Does solving the problem require a proof of optimization? Oct 3, 2023 at 12:22
• Yes, I would like a proof. The optimum can be deduced intuitively, even without pencil and paper (although this would make it easier). Oct 3, 2023 at 19:07

## 1 Answer

Here is a solution in 37 moves.

How I got there:

As the tetrahedra roll, the orientation of each at any position is determined by its initial position and orientation. See the accepted answer to an earlier question concerning the movement of a tetrahedron on a plane for more detail. For each of the eight dice, I filled the lattice with the color of its bottom face. This shows which targets each die can stand on with matching color.

The numbers on the targets and letters on the dice are referenced in this table showing with which targets each die can be paired, along with the number of moves needed to get there. Note that the 'D' die must go to target 7, and target 5 can only be matched with the 'H' die. This forces the 'B' die to target 4, and the remaining options are very limited. $$\begin{array}{|c|c|}\hline&1&2&3&4&5&6&7&8\\ \hline A&3&&6&&&&&15\\ \hline B&3&&&7&&&&\\ \hline C&&6&&&&3&&\\ \hline D&&&&&&&4&\\ \hline E&&&2&&&&&7\\ \hline F&9&&4&&&&&5\\ \hline G&9&6&&&&5&4&\\ \hline H&&&&7&7&&&\\ \hline\end{array}$$ Specifically, with dice B/D/H and targets 4/5/7 excluded, that leaves the following table: $$\begin{array}{|c|c|}\hline&1&2&3&6&8\\ \hline A&3&&6&&15\\ \hline C&&6&&3&\\ \hline E&&&2&&7\\ \hline F&9&&4&&5\\ \hline G&9&6&&5&\\ \hline\end{array}$$ Targets 2 and 6 must match with dice C and G, and we choose C-6 and G-2 since 3 + 6 is less than 5 + 6. As for A/E/F and 1/3/8, we can case based on whether we choose A-1 or F-1, and optimize the resulting 2x2. A-1, E-3, and F-8 are optimal. Adding up all the values for our pairs, we wind up with 37.

• @RobPratt See edit. There's not much left for programming. Oct 4, 2023 at 0:36
• Thanks (+1). Given your cost matrix, I confirmed optimality via linear programming. Oct 4, 2023 at 1:14
• Good solution. For completion's sake, I appended the final lines of the computation. Oct 4, 2023 at 2:45