How to find the minimum number of moves to move an item into a position in a stack?

Question

Given a set of NXP stacks with N being the number of stacks, and P being the stacks capacity, how can I calculate the minimum number of swaps needed to move from some node in location A to some arbitrary location B? I'm designing a game, and the end goal is to sort all of the stacks so that they are all the same color.

# Let "-" represent blank spaces, and assume the stacks are
stacks = [
           ['R', 'R', 'R', 'R'], 
           ['Y', 'Y', 'Y', 'Y'], 
           ['G', 'G', 'G', 'G'], 
           ['-', '-', '-', 'B'], 
           ['-', 'B', 'B', 'B']
         ]

If I want to insert a "B" at stacks[1][1] such that stacks[1] = ["-", "B", "Y", "Y"]. How can I determine the minimum number of moves required to do so?

I've been looking at multiple approaches, I've tried genetic algorithms that generate all possible moves from a state, score them, and then continue down the best scoring paths, I've also attempted to run Djikstra's algorithm for pathfinding on the problem. It seems frustratingly simple, yet I can't figure out a way to get it to run in anything other than exponential time. Is there an algorithm I'm missing that is applicable here?

Edit

I've written this function to calculate the minimum number of moves required: stacks: List of List of Characters representing the pieces in the stack, stacks[0][0] is the top of stack[0] stack_ind: The index of the stack that the piece will be added to needs_piece: The piece that should be added to the stack needs_index: The index where the piece should be located

def calculate_min_moves(stacks, stack_ind, needs_piece, needs_index):
    # Minimum moves needed to empty the stack that will receive the piece so that it can hold the piece
    num_removals = 0
    for s in stacks[stack_ind][:needs_index+1]:
        if item != "-":
            num_removals += 1

    min_to_unlock = 1000
    unlock_from = -1
    for i, stack in enumerate(stacks):
        if i != stack_ind:
            for k, piece in enumerate(stack):
                if piece == needs_piece:
                    if k < min_to_unlock:
                        min_to_unlock = k
                        unlock_from = i

    num_free_spaces = 0
    free_space_map = {}

    for i, stack in enumerate(stacks):
        if i != stack_ind and i != unlock_from:
            c = stack.count("-")
            num_free_spaces += c
            free_space_map[i] = c

    if num_removals + min_to_unlock <= num_free_spaces:
        print("No shuffling needed, there's enough free space to move all the extra nodes out of the way")
    else:
        # HERE
        print("case 2, things need shuffled")

Edit: Test Cases on stacks:

stacks = [
           ['R', 'R', 'R', 'R'], 
           ['Y', 'Y', 'Y', 'Y'], 
           ['G', 'G', 'G', 'G'], 
           ['-', '-', '-', 'B'], 
           ['-', 'B', 'B', 'B']
         ]

Case 1: stacks[4][1] should be 'G'
Move 'B' from stacks[4][1] to stacks[3][2]
Move 'G' from stacks[2][0] to stacks[4][1]
num_removals = 0 # 'G' is directly accessible as the top of stack 2
min_to_unlock = 1 # stack 4 has 1 piece that needs removed
free_spaces = 3 # stack 3 has free spaces and no pieces need moved to or from it
moves = [[4, 3], [2, 4]]
min_moves = 2
# This is easy to calculate
Case 2: stacks[0][3] should be 'B'
Move 'B' from stacks[3][3] to stack[4][0]
Move 'R' from stacks[0][0] to stacks[3][3]
Move 'R' from stacks[0][1] to stacks[3][2]
Move 'R' from stacks[0][2] to stacks[3][1]
Move 'R' from stacks[0][3] to stacks[3][0]
Move 'B' from stacks[4][0] to stacks[0][3]
num_removals = 0 # 'B' is directly accessible 
min_to_unlock = 4 # stack 0 has 4 pieces that need removed
free_spaces = 3 # If stack 3 and 4 were switched this would be 1
moves = [[3, 4], [0, 3], [0, 3], [0, 3], [0, 3], [4, 0]]
min_moves = 6
#This is hard to calculate

The actual code implementation isn't the part that is difficult, it's determining an how to implement an algorithm that solves the problem that I'm struggling with.

As per @YonIif's request I've created a gist for the problem.

When it runs, it generates a random array of the stacks, and chooses a random piece that needs to be inserted into a random stack at a random location.

Running it prints something of this format to the console.

All Stacks: [['-', '-', 'O', 'Y'], ['-', 'P', 'P', 'O'], ['-', 'P', 'O', 'Y'], ['Y', 'Y', 'O', 'P']]
Stack 0 is currently ['-', '-', 'O', 'Y']
Stack 0 should be ['-', '-', '-', 'P']

Status update

I'm very determined to solve this problem somehow.

Keep in mind that there are way's to minimize the number of cases, such as the ones @Hans Olsson mentioned in the comments. My most recent approach to this problem, has been to develop a set of rules similar to those mentioned, and employ them in a generational algorithm.

Rules such as:

Don't ever reverse a move. Go from 1->0 then 0->1 (Makes no sense)

Don't ever move a piece twice in a row. Never Move from 0 -> 1 then 1 -> 3

Given some move from stacks[X] to stacks[Y], then some number of moves, then a move from stacks[Y] to stacks[Z], if stacks[Z] is in the same state as it was when the move from stacks[X] to stacks[Y] occurred, a move could've been eliminated by moving from stacks[X] directly to stacks[Z]

Currently, I am approaching this problem with an attempt to create enough rules, that it minimizes the number of "valid" moves, enough so that an answer can be calculated using a generational algorithm. If anyone can think of additional rules, I'd be interested in hearing them in the comments.

Update

Thanks to the answer by @RootTwo I've had a bit of a breakthrough, which I will outline here.

Onto the breakthrough

Define the goal height as the depth the goal piece must be placed in the destination stack.

Whenever some goal piece is placed at index <= stack_height - goal height, there will always be a shortest path to victory via the clear_path() method.

Let S represent some solid Piece.

I.E.

Stacks = [ [R, R, G], [G, G, R], [-, -, -] ]
Goal = Stacks[0][2] = R
Goal Height = 2.
Stack Height - Goal Height = 0

Given some stack such that stack[0] = R, the game is won.

                       GOAL
[ [ (S | -), (S | -), (S | -) ], [R, S, S], [(S | - ), (S | -), (S | -)] ]

Since it is known that their are always at least stack_height blank spaces available, the worst possible case would be:

 [ [ S, S, !Goal ], [R, S, S], [-, -, -]

Since we know the goal piece cannot be in the goal destination or the game is won. In which case the minimum number of moves required would be the moves:

(0, 2), (0, 2), (0, 2), (1, 0)

Stacks = [ [R, G, G], [-, R, R], [-, -, G] ]
Goal = Stack[0][1] = R
Stack Height - Goal Height = 1

Given some stack such that stack[1] = R, the game is won.

              GOAL
[ [ (S | -), (S | -), S], [ (S | -), R, S], [(S | -), (S | -), (S | -)]

We know there are at least 3 blank spaces available, so the worst possible case would be:

[ [ S, !Goal, S], [S, R, S], [ -, -, - ]

In this case the minimum number of moves would be the moves:

(1, 2), (0, 2), (0, 2), (1, 0)

This will hold for all cases.

Thus, the problem has been reduced to a problem of finding the minimum number of moves required to place the goal piece at or above at the goal height.

This splits the problem into a series of sub-problems:

1. When the destination stack has its accessible piece != goal piece, determining if there is a valid location for that piece, or if the piece should stay there while another piece is swapped.

2. When the destination stack has its accessible piece == goal piece, determining if it can be removed and placed at the required goal height, or if the piece should stay while another is swapped.

3. When the above two cases require another piece to be swapped, determining which pieces to swap in order to increase to make it possible for the goal piece to reach the goal height.

The destination stack should always have its cases evaluated first.

I.E.

stacks = [ [-, R, G], [-, R, G], [-, R, G] ]

Goal = stacks[0][1] = G

Checking the Goal Stack first leads to:

(0, 1), (0, 2), (1, 0), (2, 0) = 4 Moves

Ignoring the Goal Stack:

(1, 0), (1, 2), (0, 1), (0, 1), (2, 0) = 5 Moves

Answer 1

I came up with two options, but none of them are able to solve case 2 in a timely manner. The first option is using A* with a string distance measure as your h(n), second option is IDA*. I tested many string similarity measures, i used smith-waterman on my approach. I have changed your notation to treat the problem faster. I have added numbers to the end of each digit to check if a piece was moved twice.

Here are the cases I have tested on:

start = [
 ['R1', 'R2', 'R3', 'R4'], 
 ['Y1', 'Y2', 'Y3', 'Y4'], 
 ['G1', 'G2', 'G3', 'G4'], 
 ['B1'], 
 ['B2', 'B3', 'B4']
]

case_easy = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G'], 
 ['B', 'B'], 
 ['B', 'B', 'G']
]


case_medium = [
 ['R', 'R', 'R', 'R'], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G', 'G'], 
 ['B'],
 ['B', 'B', 'G', 'Y']
]

case_medium2 = [
 ['R', 'R', 'R' ], 
 ['Y', 'Y', 'Y', 'B'], 
 ['G', 'G' ], 
 ['B', 'R', 'G'],
 ['B', 'B', 'G', 'Y']
]

case_hard = [
 ['B'], 
 ['Y', 'Y', 'Y', 'Y'], 
 ['G', 'G', 'G', 'G'], 
 ['R','R','R', 'R'], 
 ['B','B', 'B']
]

Here's the A* code:

from copy import deepcopy
from heapq import *
import time, sys
import textdistance
import os

def a_star(b, goal, h):
    print("A*")
    start_time = time.time()
    heap = [(-1, b)]
    bib = {}
    bib[b.stringify()] = b

    while len(heap) > 0:
        node = heappop(heap)[1]
        if node == goal:
            print("Number of explored states: {}".format(len(bib)))
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            return rebuild_path(node)

        valid_moves = node.get_valid_moves()
        children = node.get_children(valid_moves)
        for m in children:
          key = m.stringify()
          if key not in bib.keys():
            h_n = h(key, goal.stringify())
            heappush(heap, (m.g + h_n, m)) 
            bib[key] = m

    elapsed_time = time.time() - start_time
    print("Execution time {}".format(elapsed_time))
    print('No Solution')

Here's the IDA* Code:

#shows the moves done to solve the puzzle
def rebuild_path(state):
    path = []
    while state.parent != None:
        path.insert(0, state)
        state = state.parent
    path.insert(0, state)
    print("Number of steps to solve: {}".format(len(path) - 1))
    print('Solution')

def ida_star(root, goal, h):
    print("IDA*")
    start_time = time.time()
    bound = h(root.stringify(), goal.stringify())
    path = [root]
    solved = False
    while not solved:
        t = search(path, 0, bound, goal, h)
        if type(t) == Board:
            solved = True
            elapsed_time = time.time() - start_time
            print("Execution time {}".format(elapsed_time))
            rebuild_path(t)
            return t
        bound = t

def search(path, g, bound, goal, h):

    node = path[-1]
    time.sleep(0.005)
    f = g + h(node.stringify(), goal.stringify())

    if f > bound: return f
    if node == goal:
        return node

    min_cost = float('inf')
    heap = []
    valid_moves = node.get_valid_moves()
    children = node.get_children(valid_moves)
    for m in children:
      if m not in path:
        heappush(heap, (m.g + h(m.stringify(), goal.stringify()), m)) 

    while len(heap) > 0:
        path.append(heappop(heap)[1])
        t = search(path, g + 1, bound, goal, h)
        if type(t) == Board: return t
        elif t < min_cost: min_cost = t
        path.pop()
    return min_cost

class Board:
  def __init__(self, board, parent=None, g=0, last_moved_piece=''):
    self.board = board
    self.capacity = len(board[0])
    self.g = g
    self.parent = parent
    self.piece = last_moved_piece

  def __lt__(self, b):
    return self.g < b.g

  def __call__(self):
    return self.stringify()

  def __eq__(self, b):
    if self is None or b is None: return False
    return self.stringify() == b.stringify()

  def __repr__(self):
    return '\n'.join([' '.join([j[0] for j in i]) for i in self.board])+'\n\n'

  def stringify(self):
    b=''
    for i in self.board:
      a = ''.join([j[0] for j in i])
      b += a + '-' * (self.capacity-len(a))

    return b

  def get_valid_moves(self):
    pos = []
    for i in range(len(self.board)):
      if len(self.board[i]) < self.capacity:
        pos.append(i)
    return pos

  def get_children(self, moves):
    children = []
    for i in range(len(self.board)):
      for j in moves:
        if i != j and self.board[i][-1] != self.piece:
          a = deepcopy(self.board)
          piece = a[i].pop()
          a[j].append(piece)
          children.append(Board(a, self, self.g+1, piece))
    return children

Usage:

initial = Board(start)
final1 = Board(case_easy)
final2 = Board(case_medium)
final2a = Board(case_medium2)
final3 = Board(case_hard)

x = textdistance.gotoh.distance

a_star(initial, final1, x)
a_star(initial, final2, x)
a_star(initial, final2a, x)

ida_star(initial, final1, x)
ida_star(initial, final2, x)
ida_star(initial, final2a, x)