This Riddler puzzle is about arranging pool balls using a robot!

You own a start-up, RoboRackers™, that makes robots that can rack pool balls. To operate the robot, you give it a template, such as the one shown below. (The template only recognizes the differences among stripes, solids and the eight ball. None of the other numbers matters.)

First, the robot randomly corrals all of the balls into the wooden triangle. From there, the robot can either swap the location of two balls or rotate the entire rack 120 degrees in either direction. The robot continues performing these operations until the balls’ formation matches the template, and it always uses the fewest number of operations possible to do so.

Using the template given above — a correct rack for a standard game of eight-ball — what is the maximum number of operations the robot would perform? What starting position would yield this? How about the average number of operations?

Extra credit: What is the maximum number of operations the robot would perform using any template? Which template and starting position would yield this?

Here is my solution:

[Show Solution]

One way to think about this problem is as a graph. Imagine each vertex of the graph corresponds to a different arrangement of the pool balls, and we add an edge connecting two different arrangements if it’s possible to transition from one to the other in one move (either with a swap or a rotation). Then, the problem becomes: “which vertex in the graph is farthest in path-length from the target vertex?”. When two vertices are connected by an edge, we’ll call them “neighbors”. Note that the edges in this graph are bi-directional because all the moves are reversible.

Our general approach will be to label each vertex with a whole number that corresponds to the smallest number of moves required to reach the target vertex. In effect, we are computing what is called the graph eccentricity of the target vertex.

Here is a greedy approach that achieves the desired labeling.

- Create the graph by enumerating all possible unique arrangements of pool balls and adding an edge between each pair that are one move apart.
- Label the target vertex “0”. Then set $i=0$ and:
- For each vertex with label $i$, visit all of its neighbors. For each of those neighbors that is currently unlabeled, assign it the label $i+1$.
- Set $i\mapsto i+1$ and repeat from Step 3 until all vertices in the graph have been labeled.

Now that all vertices have been labeled, the vertices with maximal label correspond to those that require the most moves to be reached. In order to reconstruct the path back to the target vertex, we go in reverse order:

- Call the maximum label $d$. Then pick any vertex with label $d$. Call this the “current vertex”. Set $i=d$ and repeat:
- Enumerate the neighbors of the current vertex and pick any of them that has label $i-1$.
- Add the newly chosen vertex to the path and set it to be the new current vertex.
- Set $i\mapsto i-1$ and repeat from Step 2 until we reach $i=0$.

And it’s as simple as that! Note that we *must* do the second sequence in reverse. If we try to start from the target and work our way towards one of maximum-label vertices, there is no guarantee that we’ll be able to pick a valid max-length path because some paths will end in dead ends (they will not be max-length). When we work in reverse, however, all paths with decreasing labels must find their way back to the target because of how the labeling was constructed.

The approach I described above is a variant of , which is a popular method for solving recursively defined problems.

### Numerical solution

I coded up the procedure above and here is what I found:

- The graph has 51480 vertices 1673106 edges (yikes!).
- Each vertex has 65 neighbors. This is because from any position, there are 49 possible ways of swapping a stripe and a solid, 14 ways of swapping the eight-ball with one of the other balls, and 2 possible rotations.
- Once we finish labeling all the vertices, the largest label is $6$. This means it will take at most six moves to get to the target arrangement.
- Here is the distribution of the labels on the vertices

distance to target |
0 |
1 |
2 |
3 |
4 |
5 |
6 |

number of vertices |
1 |
65 |
1253 |
9653 |
27422 |
12946 |
140 |

So in fact, there are 140 different vertices that are max-length away from the target vertex. We can convert the frequencies listed above into probabilities by dividing by 51480, the total number of vertices. Then, this becomes a probability distribution. Computing its expected value, we obtain $\frac{51697}{12870}\approx 4.017$. So it takes about 4 moves on average to reach the target arrangement assuming we start from a position (vertex) that is chosen uniformly at random. Here is a plot of the distribution:

And finally, here is a plot of a possible sequence of moves that takes you to the target vertex from one of the 140 worst-case starting vertices.

### Extra credit

If we look for the “longest shortest path” between *any two vertices* in the graph, then we are computing what is known as the diameter of the graph. This is much more difficult to compute than the eccentricity of a particular vertex, because it involves computing the eccentricities of all vertices! Crunching the numbers took a little over an hour, and the answer is… 8. Below I show an example of a worst-case path of length 8.

In hindsight, it’s clear that the diameter can’t be any larger than 8. To see why, it suffices to show that we can get from any position to any other position in 8 moves or fewer. Here is how you do it. First, swap the eight-ball to move it to its correct location. This takes at most one move. Now, consider the remaining seven solids and seven stripes. In the worst case, all of them are out of place. So it will take at most seven additional swaps to fix it, which makes 8 total moves.

Note that in this argument, I didn’t make use of any rotations! This implies that we can always get from one configuration to another in 8 moves without using rotations. So if the shortest path between two configurations has length 8, then there also exists a shortest path that doesn’t use rotations. In the 8-length solution above, I chose the one that doesn’t have any rotations. Rotations are important in other cases, however. For example, in the original problem of achieving the eight-ball configuration, if we disallow rotations, the solution will have length 8 rather than 6.

Your solution didn’t consider the 120 degree rotation you’re allowed. Does that make a difference?

Thanks for the comment! Upon re-reading my post I noticed I used the wrong figures by accident, so those have been updated.

To answer your question: I do consider the 120-degree rotation as a possible move in my solution. You can see in my first solution (the one with length 6) that the first move is a 120-degree clockwise rotation. Rotations aren’t common, though — I don’t think that one should never need to do more than one rotation in a shortest path.

In my remark at the very end of the post, I argue that 8 moves is an upper bound (it’s always possible to get from one position to another in 8 moves or fewer) and in demonstrating this, I use an argument that doesn’t require any rotations. That means that when the shortest path between two configurations has length 8, you don’t need to use rotations. That being said, rotations can be important for shorter paths. In the original problem, if rotations aren’t used, it’s impossible to make it in 6 moves (it takes 8). I added some text at the end of my solution to clarify.

You definitely don’t need more than one rotation, because rotations commute with swaps (if a swap is regarded as operating on two particular balls, as opposed to two particular positions). So you can arrange for all rotations to occur (for instance) first, but consecutive rotations can be replaced by a single rotation.

… I think. Though rotation definitely operates on positions, not balls, so maybe this argument leaks.

No, the statement is correct but not quite correctly formulated.

For any swap-then-rotation, there is a rotation-then-swap which leads to the identical final state. Specifically, if you rotate first, you then swap the rotated positions of the balls you would have swapped first.

That rule lets you move all rotations to the beginning. Then it’s clear that there is no need to perform two rotations, since RR=L, LL=R, and RL=LR=identity.

You do a nice job of explaining your solution, I would have liked to see a diagram explaining your graph. Also, maybe some of the smaller rack sizes. 🙂

Great work though!