Mathematical formulation for Dr. Eureka

Question

I have to prepare an algorithm to solve the puzzle part of Dr. Eureka, a multiplayer game from Blue Orange Games. This is part of a research project that also involves computer vision and robotics. The game also involves agility and dexterity, but here I am looking for advice on the logic puzzle part only. I am not familiar with the formalization of these kinds of puzzles, so it is my hope that someone here could give some directions.

The puzzle is somewhat similar to the Tower of Hanoi. Each player has three transparent tubes and six plastic balls, of three different colors (two balls of each color). All the balls are inside the tubes, at some random initial configuration, forming stacks. The goal is to rearrange these stacks of balls inside the tubes to match the arrangement shown in the picture of a card (see the picture below).

These tubes are akin to the pegs of the Tower of Hanoi, in that the balls are allowed to be removed from one tube (stack pop operation) and added to the top of another stack (stack push operation), only one at a time. Differently to the Towers of Hanoi, there are no restrictions on what balls are allowed on top of what other balls (in Hanoi's a larger disk is not allowed on top of a smaller one). Among the six balls, there are two balls of each of three colors, meaning there are eight possible permutations that serve as solutions to each card. Also, it does not matter which real tube matches which in the card's illustration, i.e. the order of the tubes might be rearranged. Additionally, a tube may be flipped over, up-side-down, to present a valid solution to the game, as shown below.

My idea is to formalize this as a graph, where each node represents a configuration state of the game, and the edges represent the moves. Then I would try to use something like Dijkstra's algorithm to find the solution. This would be a very general, almost "brute force" approach. However, this problem seems way too similar to the Tower of Hanoi which has an elegant simple solution. If compared to the Tower of Hanoi, Dr. Eureka has less strict rules on the allowed moves, but it also has more general initial conditions. So I wonder if there could be some simpler way to solve this problem.

Any hint or advice is welcome.

Answer 1

Represent a configuration as a string of three "A"s, three "B"s, three "C"s, and two "|"s. The ABC represent balls and the | represent moving on from one tube to the next. The total number of configurations is then a multinomial coefficient (11 choose 3,3,3,2) which equals 11!/(3!3!3!2!), which equals 92400. That's pretty small; and the graph you're interested in is the same no matter what configuration you're looking for.

[EDITED to add:] Oops, as Bass points out in comments the state space is even smaller than that because there are only two balls of each colour, not three. So it's 8!/(2!2!2!2!) = 2520. Fewer still if, as Rodrigo Da Silva Guerra suggests in comments, we ignore the order of the tubes. (If the robot is supposed to be putting the tubes in the right order, we probably shouldn't ignore the order of the tubes.)

So, while there might be a nice elegant algorithm that always finds a solution, and there might (though I rather doubt it) even be a nice elegant algorithm that always finds an optimal solution, the super-simple approach of just building the graph and doing Dijkstra (or A*, or Floyd-Warshall, or whatever) seems clearly sufficient -- and probably easier to adapt to other similar puzzles or variants of the same puzzle.

You mention robotics, which I take to mean you're going to make an actual physical thing actually move the tubes around. In which case you would have to work very hard to make an implementation of Dijkstra's algorithm (or whatever) slow enough to have any impact on the performance of your robot!

Answer 2

Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS

Thank you for all the comments.