6
$\begingroup$

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

Example of a solved puzzle

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.

Flipped over solution

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thank you for your insight! The way you suggest representing the confugurations is quite useful. It does not account for flip overs and rearranging the order of the tubes, but it is a very nice starting point. Regarding the robotics part, you are right, we will have a robot actually planning trajectories and moving things around. However, the robotics is the part I have the most experience, this is my main field. My problem was on solving the puzzle on a higher level of abstraction. $\endgroup$ – Rodrigo Da Silva Guerra Jul 25 '18 at 18:30
  • $\begingroup$ Flipovers and rearrangements are a matter of what edges the graph has; that representation was just intended to provide an easy way of counting its vertices. $\endgroup$ – Gareth McCaughan Jul 25 '18 at 18:33
  • $\begingroup$ I totally agree that brute force is the way to go. Given the spec of "six plastic balls, of three different colors (two balls of each color)" though, using three of each letter might be considered "use of excessive force" in a court of law :-) $\endgroup$ – Bass Jul 25 '18 at 19:00
  • $\begingroup$ (Oh, and since the order of the tubes doesn't matter, you should always sort the tubes by number of balls, breaking ties by alphabetically comparing the colours of the balls from top to bottom. This probably brings the number of possible positions to hundreds, or at most thousands.) $\endgroup$ – Bass Jul 25 '18 at 19:06
  • $\begingroup$ Sorry about the excessive use of comments, but still one more thing to point out: If it's a speed competition, it would probably be a mistake to use a general "abstract" solution to the puzzle, even if one existed: you'd want to use an extra input for calculating the cost of each edge in the graph: the current position of the robot arm will have a big effect on how long it's going to take to actually perform each transition from a particular state to the next one in the solution path. $\endgroup$ – Bass Jul 25 '18 at 19:24
0
$\begingroup$

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

Thank you for all the comments.

$\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.