Algorithm description with rule 1

Using rule 1 (move as many objects of the same color as possible from the source to the destination) the total number of color blocks will never increase. In the solved position there are exactly C color blocks, while in the mixed position there are up to CxN colorblocks.

The example on the last page has only 19 and not 4x5=20 color blocks because two yellow objects in container 4 are merged and define only one block.The following situations may occur:

Destination empty, one color in source,

before move after move

This move is useless, so we do not allow it.
Destination empty, more than 1 color in source

before move after move

The number of blocks does not change.
Destination not empty. All source blocks fit into the destination container.

before move after move

The number of blocks decreases by 1.
Destination not empty. Not all source blocks fit into the destination container.

before move after move

The number of blocks does not change.

Because only moves of type 3 decrease the number of blocks we know that if there are B blocks in the initial mixed position we have solved the puzzle if and only if we have done exactly B − C moves of type 3 because there are exactly C blocks left in the solved position.

The algorithm uses a twodimensional dynamical array states[x,y] of lists with 0<= x<= B - C and y=0 at the beginning. states[x,y] is the list of all puzzle positions which are reached from the initial mixed position by x moves which decrease the number of blocks and y moves which do not decrease the number of blocks. The list states[0,0] contains only the start position, all other states[x,0] contain an empty list. The following pseudo code shows how the other array elements are populated.

y=0
solutionfound=false
repeat
     newstates=0
     for i = 0 to B − C
          states[i,y+1].Create //Create column y+1 and initialize with empty lists
     for x = 0 to B − C − 1
          for all list elements s of states[x,y] //expand states[x,y]
               create all new possible positions p which can be generated from s with one move
               for all positions p found
                    if the number of blocks decreased by one
                          add p to states[x+1,y]
                    else add p to states[x,y+1]
                    newstates = newstates + 1
     if states[ B − C, y] is not empty
          solutionfound=true;
          y0=y
     y = y + 1
until solutionfound or newstates=0

If the repeat loop returns with solutionfound=false no solution to the puzzle exists.
Else we reconstruct the move sequence backwards from states[ B − C, y0] to states[0,0] which takes B − C + y0 moves.

It is important for the algorithm to work that a move never increases the number of blocks because this would mean that new positions would be added to a list already expanded in the algorithm above. But with rule 2 exactly this may happen and we need some extra considerations in this case. This is dealt on the following page.

To keep the number of generated positions low, the containers within a position are sorted lexicographically. In this way the solution position for example is unique despite the fact that the locations of the empty containers are arbitrary. To prevent positions to be generated multiple times we compute a hash value in the range 0 <= h < 2^32 and use an array with 2^32 bits to flag the positions already generated. We do not handle hash collisions which results in some generated positions which are not added to the states array.
The hash function itself uses random numbers for the hash value generation, so the hash collisions are different in each program run for the same initial position. I never observed different outcomes caused by the hash collisions within the limitations for the number of generated positions which are imposed by the available RAM anyway.

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