9
$\begingroup$

enter image description here

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi, welcome to the site and thanks for the answer! I will accept this answer until some better would arrive. $\endgroup$ – BmyGuest Jun 12 '16 at 15:52
  • 2
    $\begingroup$ My best, found by computer, is also worth 32 points (but is one move shorter): 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 $\endgroup$ – 2012rcampion Jun 12 '16 at 16:38
  • 1
    $\begingroup$ Thanks for the link on D20 faces. As your 32move solution seems to be 'optimum' as verified by other answers, I'll keep it as the accepted one. $\endgroup$ – BmyGuest Jun 12 '16 at 17:34
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 for clarity and verification. As the answer is not different than the first correct answer to this puzzle (found without computer) I keep the accepts answer, but I appreciate your posting very much. $\endgroup$ – BmyGuest Jun 12 '16 at 17:24
7
$\begingroup$

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

enter image description here

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).

$\endgroup$
  • $\begingroup$ Very nice. And now all the graph-theory experts can jump on and show the optimum solution :c) $\endgroup$ – BmyGuest Jun 12 '16 at 15:51
  • 4
    $\begingroup$ Thanks! Care to add directionality arrows pointing towards higher numbers, for intuitive puzzlers who like to go with the flow? $\endgroup$ – WBT Jun 12 '16 at 16:50
  • $\begingroup$ Was the code really needed? From looking at your graph, could one not simple state it 'naturally' as "starting with 1 always find the 'best' path to the next higher number?" This is very easily doable by just looking at your graph, as there rare very few steps in between subsequent number-nodes. $\endgroup$ – BmyGuest Jun 12 '16 at 17:28
  • 1
    $\begingroup$ @BmyGuest I don't think I ever actually mentioned any code in my answer. But sure, if that sort of stuff floats your boat; I personally prefer to use methods without manual work, since I tend to make lots of mistakes. $\endgroup$ – 2012rcampion Jun 12 '16 at 17:32
  • $\begingroup$ "path-finding algorithm" sounded very computer-based to me, hence my question. I do agree with your systematic approach though. $\endgroup$ – BmyGuest Jun 12 '16 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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