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

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, ... finalStack[i]] == [currentStack, ... 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.

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.