8
$\begingroup$

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.

enter image description here

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.

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

1 Answer 1

11
$\begingroup$

Here is a solution in 37 moves.

enter image description here

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.
enter image description here
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.