What is the 'best' way to tilt through a D20?

Question

A regular D20 die (icosahedron) as depicted above has the number 1 to 20 arranged on its faces such that the sum of opposing faces is 21. Each triangular face touches three other faces directly by a shared edge, f.e. (1)-{7,13,19}.

Find an optimum series of face-to-face tilts with the following rules:

• You may start with any chosen face shown (i.e. facing upwards)
• You may show the same face more than once during the series.
• The complete series should have shown each number at least once
• The sequence of numbers needs to contain the ascending order of the numbers 1 to 20.

Of course there are many such sequences, so the condition to optimize is the following:

• Each tilt move which lowers the shown number from what it was before counts as a negative point.
• Minimize the amount of negative points.

What is the sequence of tilts with the lowest score?

---

Some clarifications

• I do believe that "regular" D20 dice have identical numbering, but I might be wrong. Therefore the die used for this puzzle is the one depicted above.

• This would be a valid tilting sequence of the D20 from above (face-by-face):

  19,1,13,5,15,12,2,20,14,6,9,19,3,19,9...

• This would be a valid number sequence:

  14,11,1,5,8,2,1,7,6,3,4,5,6,12,11,7,8,1,2,9,10,11,12,13,14,7,18,15,16,17,18,19,3,20

  ( This sequence can not be gotten by tilting the D20 face-by-face, though!! )

• The score for the sequence above would be:

  14,11,1,5,8,2,1,7,6,3,4,5,6,12,11,7,8,1,2,9,10,11,12,13,14,7,18,15,16,17,18,19,3,20

  = 12 negative points

Answer 1

We should obviously start at $1$.

a) Numbers $2,\ldots,6,8$ are surrounded by higher vaules, so getting there will cost us at least one point.
b) $7$ is surrounded by higher values or $1$, so getting to $7$ will also cost us (at least!) one point. Similarly, we have $9$ surronded by higher and $6 \in \text{a)}$; $10$ with higher and $8 \in \text{a)}$.
c) Looking backwards now, getting to $20,\ldots,13$ from $19,\ldots,12$ accordingly will cost us at least one point since they are surrounded by values lower than the preceding number (eg. $19\rightarrow\text{lower}\rightarrow 20$).
d) Getting from $10$ to $11$ will cost us at least one point, beacouse leaving $10$ will require us to get to number higher than $11$ (directly or via $8$). Path from $11$ to $12$ will also cost us 1 point - it goes through $13$ or $9-19$ or $9-6-\{14,16\}$ or $4 - \{14,18\}$.

Therefore the whole path will use at least 19 negative points.

Best I have found: $1$,7,15,12,$2$,20,8,16,$3$,19,9,11,$4$,18,$5$,18,4,14,$6$,9,19,1,$7$,17,10,$8$,16,6,$9$,6,16,8,$10$,12,15,5,13,$11$,13,5,15,$12$,15,5,$13$,11,4,$14$,20,2,12,$15$,7,17,3,$16$,3,$17$,10,12,15,5,$18$,4,11,9,$19$,3,16,8,$20$
worth 32 points.

It seems that the D20 doesn't have any strict mathematical pattern that would describe positioning of the tiles (related). Therefore checking all possibilities on the transitions that require more than one point is necessary.

Answer 2

One should note that we may break this problem down into a number of subproblems:

What is the path from $n$ to $n+1$ containing the least number of negative points?

It is relatively clear that concatenating the solutions to this problem for each $n=1,\ldots,19$ yields an optimal solution, since every valid sequence can be split into subpaths passing from $n$ to $n+1$ in the appropriate order.

I don't see any particular clever method for doing this, though there might be one - essentially, we are trying to find paths on a directed acyclic graph crossing the fewest number of edges backwards. The graph is also planar, which might be useful.

However, I couldn't figure out how to do this without brute force. So, I implemented Dijkstra's algorithm (with certain optimizations due to the weight of every edge being either $0$ or $1$) to solve each of these subproblems. The result was the (not unique) optimal path, traversing $32$ edges backwards:

1, 7, 17, 10, 12, 2, 20, 8, 10, 17, 3, 16, 6, 14, 4, 18, 5, 18, 4, 14, 6, 9, 11, 13, 1, 7, 17, 10, 8, 16, 6, 9, 6, 14, 20, 8, 10, 8, 16, 6, 9, 11, 4, 14, 20, 2, 12, 15, 5, 13, 11, 4, 14, 20, 2, 12, 15, 7, 17, 3, 16, 3, 17, 7, 15, 5, 18, 4, 11, 9, 19, 9, 6, 14, 20

Answer 3

As an aid to other puzzlers, here is a graph of the allowable face transitions:

Notice the numerous pentagons that appear in the graph: this is because the dual of the icosahedron is the dodecahedron, so the face adjacency graph of one is the vertex adjacency graph of the other.

We can model the problem by remembering the last "in sequence" node (face) we visited. This state variable can take on 20 different values. Combined with the 20 different faces, there are a total of 400 different states: small enough to be easily searched by computer.

My method starts by creating 20 copies of the above graph, which I'll call "levels" (I imagine them stacked one above the other like floors in a building). Each level has a single unidirectional edge leading to the next level, to and from the face corresponding to the number of the higher level. For example, face 2 on level 1 is connected to face 2 on level 2.

The remaining 600 edges are all bidirectional, but have different weights in each direction. Going from a higher-numbered face to a lower-numbered face costs $1$, and going from a lower-numbered face to a higher-numbered face costs a small amount $\varepsilon$. (In my particular implementation, $\varepsilon=10^{-3}$.) This forces a path-finding algorithm to prioritize finding the path with the fewest decreases ("negative points" in the question) over finding one with the fewest edges (although because $\varepsilon>0$ we will find the shortest path out of those which share the lowest score).

Finally, I find the shortest path from face 1 on level 1 to face 20 on level 20, yielding:

1,13,5,18,2,20,8,16,3,16,6,14,4,18,5,18,4,14,6,9,19,1,7,17,10,8,16,6,9,19,3,17,10,12,15,5,13,11,13,5,15,12,15,5,13,11,4,14,20,2,12,15,7,17,3,16,3,17,10,12,2,18,5,13,1,19,9,6,14,20

With a cost of 32.037 (32 "negative points" over 69 edges, or 70 faces).