Ernst Althaus, Markus Blumenstock, Nick Rassau, Felix Martin Schuhknecht, Anton Quentin Zimdars

Sorting Colored Balls in Colored Tubes

Introduction

Sorting colored balls in colored tubes. Explore the colored balls in colored tubes puzzle, proving move minimization is NP-hard. We detail solvability and an efficient breadth-first search algorithm for optimal solutions.

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.

Review

This paper introduces a formal analysis of a "colored balls in colored tubes" puzzle, drawing inspiration from a German television game show. The problem tasks players with moving colored balls into tubes matching their respective colors, utilizing a single auxiliary uncolored tube. The authors investigate fundamental properties concerning the solvability of such configurations, laying the groundwork for understanding the inherent structure of the puzzle. This initial exploration sets the stage for a deeper dive into the computational challenges associated with optimal play. A significant theoretical contribution of the work is the proof that minimizing the number of moves required to solve the puzzle is an NP-hard problem. This complexity result is rigorously established through a reduction from the well-known Feedback Arc Set Problem, demonstrating a strong connection between this seemingly simple puzzle and a core problem in graph theory. Beyond the theoretical hardness, the authors present a practical algorithm designed to compute minimal sequences of moves. This algorithm leverages a breadth-first search approach, which is intelligently accelerated by incorporating a lower bound on the remaining moves. This lower bound itself is ingeniously derived by solving a smaller instance of the Feedback Arc Set Problem, illustrating a clever feedback loop between the theoretical understanding and the practical algorithmic design. The practical efficacy of the proposed algorithm is validated through experimental results. The study shows that instances comprising 7 colored tubes, each of height 4, can be solved within a reasonable timeframe. A particularly insightful finding from these experiments is that the number of tubes significantly impacts the running time more critically than the individual heights of the tubes. This observation provides valuable guidance for future research and for understanding the scalability of the problem. Overall, the paper offers a comprehensive analysis, bridging theoretical complexity, algorithmic design, and empirical performance for an engaging combinatorial puzzle.

Full Text

Comments

You need to be logged in to post a comment.