The shortest way from A1 to B1

[harey]

On the square A1 of a regular chessboard is a regular dice, face 1 up and face 2 in front. The only allowed move is to rotate the dice by 90 degrees to an adjacent square.

Find the shortest way from A1 to B1 so that the dice ends in the same orientation (face 1 up and face 2 in front).

Inspired by https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/cube.html

[EventHorizon]

Spoiler

Separate the 6 numbers on the die into three sets consisting of a number and the number on the opposite side.  Separate the possible numbers on the top and front of the dice into these two groups.

1/6 top 2/5 front
2/5 top 3/4 front
3/4 top 1/6 front

2/5 top 1/6 front
3/4 top 2/5 front
1/6 top 3/4 front

Notice that if you move the die forward or back, you swap which sets of two numbers contain the number on the top of the die and which contain the number on the front.  This means moving forward or back results in the die being in a state from the other group.

Similarly for moving left or right.  You keep the same number on front, but change the set of numbers containing the number on the top of the die to the one not containing the original numbers on top or front.  This also results in the state of the die being in the other group than before the move.

Therefore, any move the die makes results in alternating between the two groups.

Now if the die is on a black square, one move will result on the die being on white square.  Similarly for white to black.

This means the die's orientation will be in one group on all black squares and in the other group on all white squares.

Since A1 and B1 are next to each other (and so they are colored differently), the die can never end up with the same orientation on B1 regardless of how many moves were made since being on A1.

Some unnecessary code:

Spoiler

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <fstream>

#include <queue>
#include <stack>

using namespace std;

int visit[8][8];
int back1[8][8];
int back2[8][8];

char moves[4] = {'u','d','l','r'};
int movesx[4] = {0,0,-1,1};
int movesy[4] = {1,-1,0,0};

unsigned char roll[24][4] =
{{16, 7, 9,13}, // 0 = 1t 2f
 {12,11,17, 5}, // 1 = 1t 3f
 { 8,15, 6,18}, // 2 = 1t 4f
 { 4,19,14,10}, // 3 = 1t 5f
 {20, 3,12, 8}, // 4 = 2t 1f
 {13,10, 1,21}, // 5 = 2t 3f
 { 9,14,22, 2}, // 6 = 2t 4f
 { 0,23,11,15}, // 7 = 2t 6f
 {21, 2, 4,16}, // 8 = 3t 1f
 {17, 6,20, 0}, // 9 = 3t 2f
 { 5,18, 3,23}, //10 = 3t 5f
 { 1,22,19, 7}, //11 = 3t 6f
 {22, 1,16, 4}, //12 = 4t 1f
 {18, 5, 0,20}, //13 = 4t 2f
 { 6,17,23, 3}, //14 = 4t 5f
 { 2,21, 7,19}, //15 = 4t 6f
 {23, 0, 8,12}, //16 = 5t 1f
 {14, 9,21, 1}, //17 = 5t 3f
 {10,13, 2,22}, //18 = 5t 4f
 { 3,20,15,11}, //19 = 5t 6f
 {19, 4,13, 9}, //20 = 6t 2f
 {15, 8, 5,17}, //21 = 6t 3f
 {11,12,18, 6}, //22 = 6t 4f
 { 7,16,10,14}};//23 = 6t 5f

 

int main(int argc, char *argv[])
{
    /*//transition matrix sanity checks
    for(int i = 0; i < 24; i++)
    {
        if (roll[i][0] + roll[i][1] != 23) cout << "Error in transition matrix " << i << ": 0+1!=23" << endl;
        if (roll[i][2] + roll[i^3][2] !=23) cout << "Error in transition matrix " << i << ": 2+(2^3)!=23" << endl;
        if (roll[i][3] + roll[i^3][3] !=23) cout << "Error in transition matrix " << i << ": 3+(3^3)!=23" << endl;
        for(int dir = 0; dir < 4; dir++)
            if (roll[roll[i][dir]][dir^1] != i) cout << "Error in transition matrix: dir=" << dir << ",orientation=" << i << " Roll dir and back results in different orientation." << endl;
    }
    for(int tofind = 0; tofind < 24; tofind++)
    {
        for(int dir = 0; dir < 4; dir++)
        {
            bool found = false;
            for(int i = 0; i < 24; i++)
                if (roll[i][dir] == tofind) found = true;
            if (found == false) cout << "Error in transition matrix: dir " << dir << " missing " << tofind << endl;
        }
    }
    */
    
    
    
    //initialize
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            visit[i][j]=0;
            back1[i][j]=0;
            back2[i][j]=0;
        }
    }
    visit[0][0] = 1;
    queue<int> list;
    list.push(0);

    //main loop -- breadth-first search
    while (!list.empty())
    {
        int current = list.front();
        list.pop();
    
        int curx = current & 7;
        int cury = (current>>3) & 7;
        int curr = current >> 6;
        
        //cout << curx << "    " << cury << "    " << curr << endl;
        //if (curr == 0) cout << curx << "    " << cury << "    " << curr << endl;
        
        for(int dir = 0; dir < 4; dir++)
        {
            int nextx = curx+movesx[dir];
            int nexty = cury+movesy[dir];
            int nextr = roll[curr][dir];
            
            //stay in bounds
            if ((nextx < 0) || (nextx > 7)) continue;
            if ((nexty < 0) || (nexty > 7)) continue;
            //already found that state
            if (visit[nextx][nexty]&(1<<nextr)) continue;
            
            //mark visited
            visit[nextx][nexty] |= 1<<nextr;
            if (dir&1) back1[nextx][nexty] |= 1<<nextr;
            if (dir&2) back2[nextx][nexty] |= 1<<nextr;
            //add state to list
            list.push((nextr<<6) + (nexty<<3) + nextx );
        }
        
        if (visit[1][0]&1)
        {
            cout << "Found solution." << endl;
            
            //print path
            stack<int> path;
            curx = 1;
            cury = 0;
            curr = 0;
            while(curx || cury || curr)
            {
                int dir = 0;
                if (back1[curx][cury]&(1<<curr)) dir+=1;
                if (back2[curx][cury]&(1<<curr)) dir+=2;
                path.push(dir);
                curx -= movesx[dir];
                cury -= movesy[dir];
                curr = roll[curr][dir^1];
            }
            while(!path.empty())
            {
                cout << moves[path.top()];
                path.pop();
            }
            cout << endl;
            
            return 0;
        }
    }
    cout << "No solution found." << endl;
    
    return 0;
}