Shortest Path by rolling a dice

Question

I have a difficult problem to solve (at least that's how I see it). I have a die (faces 1 to 6) with different values (others than [1-6]), and a board (n-by-m). I have a starting position and a finish position. I can move from a square to another by rolling the die. By doing this I have to add the top face to the sum/cost.

Now I have to calculate how to get from the start position to the end position with a minimum sum/cost. I have tried almost everything but I can't find the correct algorithm.

I tried Dijkstra but it's useless because in the right path there are some intermediate nodes that I can reach with a better sum from another path (that proves to be incorrect in the end). How should I change my algorithm?

algorithm overview:
dijkstra : PriorityQueue
if(I can get to a node with a smaller sum)
,remove it from the queue,
I change its cost and its die position
,add it to queue.

This is the code :

public void updateSums() {

    PriorityQueue<Pair> q = new PriorityQueue<>(1, new PairComparator());

    Help h = new Help();

    q.add(new Pair(startLine, startColumn, sums[startLine][startColumn]));

    while (!q.isEmpty()) {

        Pair current = q.poll();

        ArrayList<Pair> neigh = h.getNeighbours(current, table, lines, columns);

        table[current.line][current.column].visit(); //table ->matrix with Nodes

        for (Pair a : neigh) {

            int alt = sums[current.line][current.column] + table[current.line][current.column].die.roll(a.direction);

            if (sums[a.line][a.column] > alt) {

                q.remove(new Pair(a.line, a.column, sums[a.line][a.column]));

                sums[a.line][a.column] = alt; //sums -> matrix with costs

                table[a.line][a.column].die.setDie(table[current.line][current.column].die, a.direction);

                q.add(new Pair(a.line, a.column, sums[a.line][a.column]));
            } 

        }
    }

}

Answer 1

You need to also consider the position of the die in your Dijkstra states.

I.e. you cannot just have sums[lines][column], you'll have to do something such as sums[lines][column][die_config], where die_config is some way you create to convert the die position into an integer.

For example, if you have a die that looks like this initially:

^1 <4 v2 >9 f5 b7 (^ = top face, < = left... down, right, front and back)

int initial_die[6] = {1,4,2,9,5,7}

You can convert it to an integer by simply considering the index of the face (from 0 to 5) that is pointing up and the one that is to the left. This means your die has less than 36 (see bottom note) possible rotation positions, which you can encode through something such as (0-based) (up*6 + left). By this I mean each face would have a value from 0 through 5 that you decide, regardless of their cost-associated value, so following the example above we would encode the initially top face as being the index 0, the left face as being the index 1, and so on.

So the die with config value 30 means that left = 30%6 (=0) the face that was initially pointing up (initial_die[0]), is currently pointing to the left, and up = (30 - left)/6 (=5) the face that is currently pointing up, is the one that was initially pointing to the back of the die (initial_die[5]). So this means the die currently has the cost 1 on its left face, and the cost 7 on its top face, and you can derive the rest of the die's faces from this information, since you know the initial disposition. (Basically this tells us the die rolled once to its left, followed by once towards its front, in comparison to the initial state)

With this additional information, your Dijkstra will be able to find the correct answer you seek, by considering the cheapest cost that reaches the final node, as you could have multiple with different final die positions.

Note: It doesn't actually have 36 possible positions, because some are impossible, for example two initially opposite sides won't be able to become adjacent on Up/Left. There are in fact only 24 valid positions, but the simple encoding I used above will actually use indexes up to ~34 depending on how you encode your die.