Preciso de ajuda para encontrar uma boa heurística para o seguinte problema:

Você é dado umR-por-C grade e um dado de seis lados. Deixeistart eend ser duas células distintas nesta grade. Encontre um caminho destart paraend tal que a soma dos rostos do dado olhando para cima, enquanto o dado está girando ao longo do caminho, é mínima.

A orientação inicial do dado é a seguinte (o "2" está voltado para o sul):

A maneira como modelei esse problema é considerando o valor da face da matriz como o custo de uma borda em um gráfico. Os vértices do grafo são da forma(row, col, die) (isto é, uma posição na grade e o estado atual / orientação do dado). A razão pela qual um vértice não é simplesmente(row, col) é porque você pode acabar na mesma célula com múltiplas configurações / orientações do dado.

Eu usei A * para encontrar a solução para o problema; as respostas dadas estão corretas, mas não são eficientes o suficiente. Eu determinei que o problema é a heurística que estou usando. Atualmente estou usando a distância de Manhattan, que é obviamente admissível. Se eu multiplicar a heurística por uma constante, ela não será mais admissível: ela é executada muito mais rapidamente, mas nem sempre encontra a resposta correta.

Preciso de ajuda para encontrar uma heurística melhor que a distância de Manhattan.