7
$\begingroup$

Here's an interesting puzzle.

This is called "Rudenko's Disk" (Brainwright) — finding information or solves for it online isn't all that challenging, which would largely ruin the fun here, so don't go looking it up. Here's what the puzzle looks like:

color-wheel

The puzzle consists of 7 movable Dots, colored roughly Red, Orange, Yellow, Green, Cyan, Blue, and Pink. In the picture they are in the middle, in the order listed, starting at the bottom right and running clockwise around the center circle (which does not move). These Dots are in a track which runs around the center, counter-clockwise from where the Pink Dot sits, around the center circle to where the Red Dot sits, then branches off in both directions to form the two visible track arms at the upper and lower extremities of the puzzle. Each of these arms runs through a series of colored positions, also ranging through the same set of colors in the same order (Red, ..., Pink). The two arms are completely symmetric. Though not visible with the Dots in their current position, the Dots on the center track are also sitting on like-colored positions - Red Dot on Red, ..., Pink Dot on Pink.

The colors' order is important. Looking at the right-hand part of the puzzle, at the "Y" where the three sections of the track meet, each colored Dot can only move as far down any of the three track parts as their own color. Thus, the Red Dot cannot move beyond the Red position (so can never be farther from the "Y" than it is right now, regardless of which section track it is on). The Green Dot can move halfway along any of the three track sections, but not beyond there. The Pink Dot can move to any position on any of the track sections.

Two final notes. First: if they are pushed as far down the track as possible, the Dots will sit exactly on their own colored position. And second: in practical terms, only one Dot can be inside the "Y" at a time - that is to say, for a Dot to traverse through the "Y" from one track onto another, any Dots on the third track must be pushed all the way to (or beyond) the Red position.

Ok - now that all the mechanical considerations are covered, hopefully intelligibly, on to the objective.

How many Dot moves will it take to move all 7 Dots from their current positions on the center track to their appropriate positions on the upper track?

$\endgroup$
  • $\begingroup$ Computer-aided solutions: OK or not? $\endgroup$ – Gareth McCaughan May 30 '17 at 21:41
10
$\begingroup$

While the solution of the tower of Hanoi also applies to this puzzle, there is a shorter solution!

Let's number the pieces 1 to 7, where 1 is the red, innermost piece which corresponds to the smallest disk of the Hanoi tower. Whereas the Hanoi puzzle does not allow you to place a larger disk onto a smaller one, that is allowed on this puzzle. The Rudenko disk's only restriction is that you can place at most n-1 disks on top of disk n. This is a weaker restriction that allows you some short cuts. Here is a picture of the first shortcut:

enter image description here

This generalises, and allows you to reduce the problem of moving a stack of $n$ disks to the simpler problems of moving a stack of $n-2$ disks three times, and moving the two largest disks twice. This leads to a solution for which the length satisfies the equality $L(n) = 3·L(n-2) + 4$. From this and the fact that $L(1) = 1$, and $L(2) = 3$, you can prove by induction that if $n$ is even, say $n=2k$, then $L(2k) = 5·3^{k-1} - 2$, and if $n$ is odd, $n=2k-1$, then $L(2k-1) = 3^k - 2$.

This is a considerable saving compared to the Hanoi solution of $L(n)=2^n-1$. For the 7 pieces in this puzzle you can do it in $79$ moves instead of $127$.

Here is a picture with the full solution:

Full solution

For more details you can look at the Hanoi page on my website.

$\endgroup$
  • $\begingroup$ What madness is this?! You are, of course, correct. But you clearly stole the optimal solution from this blog post ... oh. wait. Hehe. Actually I see from that blog that apparently not even the designer knew the shortcut. My puzzle had no instructions included in it at all, so maybe they've stopped providing the non-optimal "optimal" 127 step solution entirely. $\endgroup$ – Rubio May 31 '17 at 13:26
4
$\begingroup$

The number of moves required is

$2^7-1=127$.

This resembles

the Towers of Hanoi, though the constraint isn't quite the same. Here's the point. Number the discs from 1 (red) to 7 (pink). In order to get disc $n$ from one track to its rightful place on another track, you need all the lower-numbered discs out of that track (because any of them will block its path on the track they're on). So, suppose we want to transfer all the discs from track A to track B. We need, in particular, to transfer the pink disc to the far end of track B, which we can only do once we have moved all the other discs to track C. And after doing this we will have to move all those other discs from track C to track B. This is exactly the same structure as we see with the Towers of Hanoi, and it leads to the same recurrence relation and the same number of moves (and, indeed, essentially the same solution).

$\endgroup$
  • $\begingroup$ Sorry Gareth - it seems you (and I) are wrong about the optimal solution. Moving the checkmark to Jaap's answer! $\endgroup$ – Rubio May 31 '17 at 13:29
  • $\begingroup$ Coooool. Rubio, I said it wasn't obvious that the puzzle was exactly isomorphic to ToH. (But clearly I didn't take that seriously enough...) $\endgroup$ – Gareth McCaughan May 31 '17 at 14:54
2
$\begingroup$

Gareth is right. This is the same as the Towers of Hanoi. The interesting thing is that this means that there is a very easy algorithm for solving it. The nice thing is that the solution can end on either side, so we do not need to worry about which direction to do the first move (although this is not too complicated as it is just a polarity issue).

  1. Move the red one every alternate move in a cycle (let's say clockwise).
  2. Make whatever other move keeps the order correct (or actually is possible - there will only be one possible move, assuming the home track has the same restrictions).

By correct I mean in the correct color order (so you can put orange on yellow, but not the other way around).

So the first few moves would be (calling the three positions top, middle, and bottom):

  • Red to the top (Solves the case for $n=1$)
  • Orange to the bottom
  • Red to the bottom (Solves the case for $n=2$)
  • Yellow to the top
  • Red to the middle
  • Orange to the top
  • Red to the top (Solves the case for $n=3$)
  • Green to the bottom
  • Red to the bottom
  • ...

You get the idea. If you look at the odd moves, you will see that the red is simply cycling top$\rightarrow$bottom$\rightarrow$middle$\rightarrow\cdots$ If you know this algorithm, you can impress people with the Towers of Hanoi at parties. And with this game, it seems.

$\endgroup$

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.