Algorithm description with rule 2

Using rule 2 (move only one object from the source to the destination) the total number of color blocks increases in the following case:

Destination empty, at least two objects with the same color on top of the source container

before move after move

The described algorithm on the last page does not work if some moves increase the total number of blocks. We can fix this situation if we count empty containers as one block too. Then in the situation above the number of blocks does not change. The disadvantage is that when states[ B − C, y0] is populated and the algorithms returns with solutionfound=true, the positions in states[ B − C, y0] have the property that any container contains only objects of one single color or is empty, but do not necessarily represent the solved position.

In other words the algorithm now finds the shortest move sequence to a position where any container holds at most objects of one color - for example this position if we have four colors and two empty containers:

To complete the solving process some obvious additional moves have to be made. We choose a position from states[ B − C, y0] with the fewest necessary number of correction moves . But the algorithm to completely solve the puzzle now is only near-optimal.

< Home > <Color Sort Puzzles> <Algorithm description 1>

© 2021  Herbert Kociemba