How can I calculate the minimum number of moves needed in a game involving stacks?

Question

I'm currently programming a game, and I have been stuck on the following problem for a while.

The above figure is a set of stacks. The end-goal is to sort all items by color in the least possible number of moves. For a gameboard like above, computing the solution doesn't take long at all. The problem occurs when the board grows in size, with the maximum board being 8X8 (8 stacks, and 7 colors, with one empty stack) The final solution doesn't need to be exact, the main goal I have is something that's fairly close to the minimum number of moves.

In the above, there would be 6 possible moves:
(1 -> 3) (2 -> 3) (4 -> 3) (2 -> 1) (3 -> 1) and (4 -> 1)

The algorithm I am currently using starts with all of the pieces sorted, and then works backwards to generate the game state.

I currently have a scoring function in place.

# The reversed order of the stacks, with R = Red, Y = Yellow, G = Green, and 0 = Empty
gameFinalState = Set( [R, 0, 0, 0], [Y, G, R, Y], [Y, Y, R, 0], [G, G, G, R] )

# The win state, which I will backtrack from (Also in reverse order)
gameCurrentState = Set ( [R, R, R, R], [Y, Y, Y, Y], [G, G, G, G], [0, 0, 0, 0] )

finalScore = 0

while numberOfStacksIn(gameCurrentState) > 0 {
    topScore = -1
    finalS = None
    currentS = None
    for each finalStack in gameFinalState {
        for integer i = 1 to numberOfItemsInStack(stack) {
            # Empty stacks have no score, and since they are in reverse order, 
            # if the first element is empty they all are empty
            if Set(stack_1, stack_2, ... stack_i) != Set(0) {
                for each currentStack in gameCurrentState {
                    # if there are i elements that are in the correct order of some finalStack
                    if [finalStack[1], ... finalStack[i]] == [currentStack[1], ... currentStack[i]] {
                        # If every element is in the right order
                        if i == numberOfItemsInStack {
                            # This is the highest possible score a stack can have
                            topScore = i
                            finalS = finalStack
                            currentS = currentStack    
                        } else {
                              # If the stack score is equal to the current highest scoring stack
                              if i == topScore {
                                  # A tiebreaker, that scores stacks that have the correct elements and 
                                  # empty spaces since it only takes 1 move to move the
                                  # "next correct piece" to the stack, and there is no additional move to
                                  # remove an incorrect piece
                                  if currentS[i+1] == 0 {
                                      topScore = i
                                      finalS = finalStack
                                      currentS = currentStack
                                  }
                                # If the stack score is greater than the highest scoring stack
                              } else if i > topScore {
                                     topScore = i
                                     finalS = finalStack
                                     currentS = currentStack
                              }
                        }
                   # If the top score is still -1 (every stack has the wrong bottom piece)
                   } else if topScore == -1 {
                       topScore = 0
                       finalS = finalStack
                       currentS = currentStack
                   }
                }
            }
        }
    }
    # Add the topScore to the final score
    finalScore = finalScore + topScore
    # Remove the state that corresponds to the topScore from the gameFinalState set
    gameFinalState = gameFinalState - finalS
    # Remove the state that correspons to the topScore from the gameCurrentState set
    gameCurrentState = gameCurrentState - currentS

    # If there is only one element left and it is the empty stack, remove the element
    if numberOfItemsIn(gameCurrentState) == 1  and Set(0) in gameCurrentState {
        gameCurrentState = gameCurrentState - Set(0)
    }
}

This assigns each specific game state a score. I start by generating every possible move from game state one. (From state one in a 4X4 playing field, this is 3 possible moves.)

Each move is scored, and then all of the top scoring moves go on to the next round, this doesn't always lead to a minimum score however, and sometimes it becomes cyclic. In order to combat this, I also take a random sample of ~50 game states from the next 3 highest scoring sets. For a 4X4 game, this works great, and runs in milliseconds. When the game increases in size, the time complexity grows exponentially.

Are there any edge-cases I'm missing that might speed this up, or perhaps some algorithm that already exists for solving this problem?

I think the approach I'm taking is decent, but the appearance of cycles has me wondering if I can translate this into a graph problem, and use something like Dijkstra's algorithm on it.

Answer 1

Yes, you can formulate this as an $s$-$t$ shortest path problem in a directed graph with a node for each state and an arc from node $i$ to node $j$ for each possible transition. The starting state is the source node $s$, but you have multiple ending states. Introduce a dummy sink node $t$, and for each ending state, introduce an arc to $t$. Now apply Dijkstra's algorithm.