Sorting Colored Balls in Colored Tubes

Abstract

We consider a game that was played in a German television show that is similar to the sorting balls puzzle. In it, we are assumed to move one colored ball after another in a set of colored tubes so that in the end, each ball is in the tube of its color. We are allowed to use one additional (uncolored) tube. We show general properties for solvability and that the problem of minimizing the number of moves is NP-hard, which is done by a reduction from the Feedback Arc Set Problem. Furthermore, we give an implementation of an algorithm to compute such a minimal sequence of moves. The algorithm is based on breadth-first search and accelerated by a lower bound on the number of moves from the current configuration to the final one that is obtained by solving a small instance of the Feedback Arc Set Problem. Our experiments show that instances with 7 colored tubes of height 4 can be solved in a reasonable amount of time and that the number of tubes is much more critical for the running time than the heights of the tubes.