Como encontrar o número mínimo de movimentos para mover um item para uma posição em uma pilha?

Dado um conjunto de pilhas NXP com N sendo o número de pilhas e P como a capacidade de pilhas, como posso calcular o número mínimo de trocas necessárias para mover de algum nó no local A para algum local arbitrário B? Estou criando um jogo, e o objetivo final é classificar todas as pilhas para que elas tenham a mesma cor.

# 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']
         ]

Se eu quiser inserir um "B" de stacks[1][1]tal forma stacks[1] = ["-", "B", "Y", "Y"]. Como posso determinar o número mínimo de movimentos necessários para fazer isso?

Eu estive analisando várias abordagens, tentei algoritmos genéticos que geram todos os movimentos possíveis de um estado, os pontuam e depois seguem os melhores caminhos de pontuação, também tentei executar o algoritmo de Djikstra para encontrar o problema . Parece frustrantemente simples, mas não consigo descobrir uma maneira de fazê-lo funcionar em nada além de tempo exponencial. Há um algoritmo que está faltando que é aplicável aqui?

Editar

Escrevi esta função para calcular o número mínimo de movimentos necessários: stacks: Lista de caracteres que representam as peças da pilha, stacks [0] [0] é o topo da pilha [0] stack_ind: O índice do pilha em que a peça será adicionada a needs_piece: a peça que deve ser adicionada à pilha needs_index: o índice em que a peça deve ser localizada

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")

Editar: Casos de teste em pilhas:

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

A implementação real do código não é a parte difícil, é determinar como implementar um algoritmo que resolve o problema com o qual estou lutando.

De acordo com a solicitação de @ YonIif, criei uma essência para o problema.

Quando executado, gera uma matriz aleatória das pilhas e escolhe uma peça aleatória que precisa ser inserida em uma pilha aleatória em um local aleatório.

A execução imprime algo desse formato no 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']

Atualização de status

Estou muito determinado a resolver esse problema de alguma forma .

Lembre-se de que existem maneiras de minimizar o número de casos, como os que @Hans Olsson mencionou nos comentários. Minha abordagem mais recente para esse problema foi desenvolver um conjunto de regras semelhantes às mencionadas e empregá-las em um algoritmo geracional.

Regras como:

Nunca inverta um movimento. Vá de 1-> 0 e 0-> 1 (não faz sentido)

Nunca mova uma peça duas vezes seguidas. Nunca mude de 0 -> 1 e depois 1 -> 3

Dado algum movimento das pilhas [X] para as pilhas [Y], depois um número de movimentos, então uma mudança das pilhas [Y] para as pilhas [Z], se as pilhas [Z] estiverem no mesmo estado em que estavam quando o movimento das pilhas [X] para as pilhas [Y], um movimento poderia ter sido eliminado movendo-se das pilhas [X] diretamente para as pilhas [Z]

Atualmente, estou abordando esse problema com uma tentativa de criar regras suficientes, para minimizar o número de movimentos "válidos", o suficiente para que uma resposta possa ser calculada usando um algoritmo geracional. Se alguém puder pensar em regras adicionais, eu estaria interessado em ouvi-las nos comentários.

Atualizar

Graças à resposta de @RootTwo, tive um grande avanço, que descreverei aqui.

Para o avanço

Defina a altura da meta como a profundidade em que a peça da meta deve ser colocada na pilha de destino.

Sempre que alguma peça do gol é colocada no índice <= stack_height - altura do gol, sempre haverá um caminho mais curto para a vitória através do método clear_path ().

Let S represent some solid Piece.

IE

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

Dada uma pilha como essa stack[0] = R, o jogo é ganho.

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

Como é sabido que sempre há pelo menos espaços em branco stack_height disponíveis, o pior caso possível seria:

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

Como sabemos que o gol não pode estar no destino do gol ou o jogo é vencido. Nesse caso, o número mínimo de movimentos necessários seriam os movimentos:

(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

Dada uma pilha como essa stack[1] = R, o jogo é ganho.

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

Sabemos que há pelo menos três espaços em branco disponíveis, portanto, o pior caso possível seria:

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

Nesse caso, o número mínimo de movimentos seriam os movimentos:

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

Isso será válido para todos os casos.

Assim, o problema foi reduzido a um problema de encontrar o número mínimo de movimentos necessários para colocar a peça do gol na altura do gol ou acima dele.

Isso divide o problema em uma série de subproblemas:

1. Quando a pilha de destino tem sua peça acessível! = Peça da meta, determinando se existe um local válido para essa peça ou se a peça deve permanecer lá enquanto outra peça é trocada.

2. Quando a pilha de destino tem sua peça acessível == peça da meta, determinando se ela pode ser removida e colocada na altura desejada da meta ou se a peça deve permanecer enquanto outra é trocada.

3. Quando os dois casos acima exigirem que outra peça seja trocada, determine quais peças serão trocadas para aumentar para possibilitar que a peça atinja a altura da meta.

A pilha de destino sempre deve ter seus casos avaliados primeiro.

IE

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

Goal = stacks[0][1] = G

Verificar a pilha de metas primeiro leva a:

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

Ignorando a pilha de objetivos:

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

Eu vim com duas opções, mas nenhuma delas é capaz de resolver o caso 2 em tempo hábil. A primeira opção é usar A * com uma medida de distância de cadeia como h (n), a segunda opção é IDA *. Eu testei muitas medidas de similaridade de strings, usei smith-waterman na minha abordagem. Alterei sua notação para tratar o problema mais rapidamente. Eu adicionei números ao final de cada dígito para verificar se uma peça foi movida duas vezes.

Aqui estão os casos em que testei:

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']
]

Aqui está o código A *:

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')

Aqui está o código IDA *:

#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

Uso:

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)

Nos comentários que você disse, existem N pilhas com capacidade P e sempre há P espaços vazios. Se for esse o caso, parece que esse algoritmo funcionará na elsecláusula do seu código (ou seja, quando num_removals + min_to_unlock > num_free_spaces):

1. Encontre a peça desejada mais próxima do topo de uma pilha.
2. Mova todas as peças de cima da peça desejada de forma que exista uma pilha (não a pilha de destino) que tenha um espaço vazio na parte superior. Se necessário, mova as peças da pilha de destino ou de outra pilha. Se o único espaço aberto for o topo da pilha de destino, mova uma peça para lá para abrir o topo de outra pilha. Isso sempre é possível, porque existem P espaços abertos e, no máximo, peças P-1 para mover acima da peça desejada.
3. Mova a peça desejada para o local vazio no topo de uma pilha.
4. Mova as peças da pilha de destino até que o destino esteja aberto.
5. Mova a peça desejada para o destino.

Embora eu não tenha encontrado tempo para provar isso matematicamente, decidi postar isso de qualquer maneira; espero que ajude. A abordagem é definir um parâmetro p que diminua com bons movimentos e atinja zero exatamente quando o jogo terminar. No programa, apenas considera boas jogadas ou jogadas neutras (que deixam p inalterado) e esquece jogadas ruins (que aumentam p).

Então, o que é p? Para cada coluna, defina p como o número de blocos que ainda precisam ser removidos antes que todas as cores nessa coluna sejam da cor desejada. Então, suponha que queremos que os blocos vermelhos terminem na coluna mais à esquerda (voltarei a isso mais tarde) e suponha que exista um bloco vermelho na parte inferior, depois um amarelo em cima disso, mais um bloco em cima de isso e, em seguida, um espaço vazio. Então p = 2 para esta coluna (dois blocos a serem removidos antes que todos estejam vermelhos). Calcule p para todas as colunas. Para a coluna que deve acabar vazia, p é igual ao número de blocos que está nela (todos eles devem ir). P para o estado atual é a soma de todos os p para todas as colunas.

Quando p = 0, todas as colunas têm a mesma cor e uma coluna está vazia, então o jogo terminou.

Ao escolher movimentos que diminuem p (ou pelo menos não aumentam p), estamos nos movendo na direção certa, esta é, na minha opinião, a diferença crucial com os algoritmos de caminho mais curto: Dijkstra não fazia ideia se estava se movendo na direção certa a cada vértice que ele estava investigando.

Então, como determinamos onde cada cor deve terminar? Basicamente, determinando p para todas as possibilidades. Por exemplo, comece com vermelho / amarelo / verde / vazio, calcule p, depois vá para vermelho / amarelo / vazio / verde, calcule p, etc. Tome a posição inicial com o menor p. Isso leva n! cálculos. Para n = 8, isso é 40320, o que é factível. A má notícia é que você terá que examinar todas as posições iniciais com o menor p. A boa notícia é que você pode esquecer o resto.

Existem duas incertezas matemáticas aqui. Um: é possível que exista um caminho mais curto que use uma jogada ruim? Parece improvável, não encontrei um contra-exemplo, mas também não encontrei uma prova. Segundo: é possível que, ao iniciar com uma posição inicial não ótima (ou seja, o p mais baixo), haja um caminho mais curto do que com todas as posições iniciais ideais. Novamente: sem contra-exemplo, mas também sem provas.

Algumas sugestões de implementação. Manter o controle de p durante a execução de cada coluna não é difícil, mas é claro que deve ser feito. Outro parâmetro que deve ser mantido para cada coluna é o número de vagas em aberto. Se 0, essas colunas momentaneamente não podem aceitar nenhum bloco, portanto podem ser deixadas de fora do loop. Quando p = 0 para uma coluna, ela não é elegível para um pop. Para cada pop possível, examine se há uma boa jogada, ou seja, uma que diminua o total de p. Se houver vários, examine todos. Se não houver, considere todos os movimentos neutros.

Tudo isso deve reduzir bastante o tempo de computação.