Color Sort Puzzles

There are many puzzle apps like "Water Sort Puzzle", "Ball Sort Puzzle", "Sand Sort Puzzle", "Sort Hoop", "Sort Stack", "Sort It 3D" etc. etc. which share the same idea. You have C containers of equal size, each container holds N equal objects with the same color. Different containers also differ in the color of their objects, so there are total of C*N objects and exactly N objects have the same color.

Example with C = 4 and N = 5.

Now the objects are mixed and a number K of empty containers are added, K=2 in this example

You can move objects from a source container into a destination container if the destination is empty or the source and the destination have the same top color. There are two possible additional rules:

Move as many objects with the same color from the source to the destination as possible (objects are liquid, sand etc.). Or
Move just one object from the source to the destination (objects are balls, hoops etc.)

Goal of the game is to undo the mixing and we have N full containers with the same color again.

An optimal solution for the situation above using rule1 is for example

1→5, 3→5, 4→1, 4→5, 1→4, 1→3, 2→1, 2→5, 2→6, 2→1, 2→5, 4→6, 3→4, 3→1, 3→4, 1→3, 1→6

and takes 17 moves.

Using rule 2 a near-optimal solution will take 18 moves

1→5, 1→6, 3→5, 4→6, 4→5, 4→6, 1→4, 3→4, 3→1, 3→4, 2→3, 2→5, 2→6, 2→3, 1→3, 1→3, 2→5, 1→6

Probably this solution is also optimal. But for rule 2 the algorithm used cannot guarantee optimality.

In this paper from 2022 it is shown that this sort of problem ist NP-complete. This refers to the question if a given configuration is solvable at all and also to the question of the shortest solution if a configuration is solvable.

On the following page I describe an algorithm, which is very efficient to solve puzzles of this type optimally. I wrote a GUI program which implements this algorithm and which you can use to create,edit, analyze and play puzzles of this type.

download windows x64 exe

The sourcecode is available here

https://github.com/hkociemba/WaterBallSortPuzzleOptimalSolver

< Home > <Algorithm description 1> <Algorithm description 2>