title: A* Admissible Heuristic for die rolling on grid
body: <p>I need some help finding a good heuristic for the following problem:</p>
  
  <blockquote>
    <p>You are given an <strong><code>R</code></strong>-by-<strong><code>C</code></strong> grid and a six-sided die. Let <strong><code>start</code></strong> and 
    <strong><code>end</code></strong> be two distinct cells on this grid. Find a path from <code>start</code> to <code>end</code> such that 
    the sum of the faces of the die looking up, as the die is turning along the path, is 
    minimal.</p>
    
    <p>The starting orientation of the die is the following (the "2" is facing south):</p>
    
    <p><img src="https://i.stack.imgur.com/4gMMs.jpg" alt="enter image description here"></p>
  </blockquote>
  
  <p>The way I modeled this problem is by considering the value of the die's face as the cost of an edge in a graph. The graph's vertices are of the form <code>(row, col, die)</code> (i.e, a position in the grid and the current state/orientation of the die). The reason a vertex is not simply <code>(row, col)</code> is because you can end up on the same cell with multiple configurations/orientations of the die.</p>
  
  <p>I used A* to find the solution to the problem; the answers given are correct, but it is not efficient enough. I've determined that the problem is the heuristic I'm using. Currently I'm using Manhattan distance, which is obviously admissible. If I multiply the heuristic with a constant, it's no longer admissible: it runs much faster but it doesn't always find the right answer.</p>
  
  <p>I need some help in finding a better heuristic than Manhattan distance.</p>