Sliding Dice in a Dish

Question

We have 3 dice in a square dish. The dish is 8 units wide and tall and each die is 3 units wide and tall. The dice are facing up each with a different number on their top face.

111..222
111..222
111..222
........
........
333.....
333.....
333.....

Then we play a game. At each step we can slide any 1 die in any cardinal direction until it meets either another die or a boundary. We are not allowed to stop sliding it before it hits an obstacle, we must go all the way.

For example from the position above the following are valid next moves:

111222..  111.....
111222..  111.....
111222..  111.....
........  ........
........  ........
333.....  333..222
333.....  333..222
333.....  333..222

but these are not:

111.222.  111.....
111.222.  111.....
111.222.  111.....
........  .....222
........  .....222
333.....  333..222
333.....  333.....
333.....  333.....

The goal of the game is to choose a potential position and see if you can get to it from the starting position.

For example, if our goal is:

........
........
..111222
..111222
..111222
..333...
..333...
..333...

We can do these moves:

111..222  111.....  111.....  ........  .....222  ...222..  ........  ........  ........
111..222  111.....  111.....  ........  .....222  ...222..  ........  ........  ........
111..222  111.....  111.....  111.....  111..222  111222..  111222..  111..222  ..111222
........  ........  ........  111.....  111.....  111.....  111222..  111..222  ..111222
........  ........  ........  111.....  111.....  111.....  111222..  111..222  ..111222
333.....  333..222  ..333222  ..333222  ..333...  ..333...  ..333...  ..333...  ..333...
333.....  333..222  ..333222  ..333222  ..333...  ..333...  ..333...  ..333...  ..333...
333.....  333..222  ..333222  ..333222  ..333...  ..333...  ..333...  ..333...  ..333...

Not every game is winnable though, for example:

222..111
222..111
222..111
........
........
333.....
333.....
333.....

Task

You will take as input a board, and you should output whether that board can be reached from the above starting position using these moves.

This is code-golf answers will be scored in bytes with fewer bytes being better.

IO

You can take input as an 2D array containing 4 distinct symbols representing the 3 dice and the background. You can also take it as a list of a specified corner (e.g. upper left corner) of each of the dice.

You should give output as 1 of two distinct values with both corresponding to either true and false.

Answer 1

PHP, 157 123 111 89 bytes

function f($b){$o=$c=9;foreach($b as$p){$o*=$p%3-1;$c^=$p>2;$c*=2;}return$o&&$c%46%14<5;}

Try it online!

Some deductions

I've first noted that, on each axes, if we consider the shorter distance of a dice from a wall, it can never be \$1\$.

Each movement aims towards a wall or a dice:

• hitting a wall we reset the dice shorter distance to \$0\$.
• hitting a dice we set the dice shortest distance to either \$1\$ or \$2\$.
  • \$2\$ iff the dice we hit has distance \$0\$ from the wall
  • \$1\$ iff the dice we hit has distance \$1\$ from the wall

Hence why, since in the starting configuration there are no dices at distance \$1\$ from a wall, they can never pop up.

Putting momentarily aside the dices labeling, we want to know if any configuration having no dice at distance \$1\$ from a wall is reachable. Note that if one particular configuration is reachable so do all its rotations and reflections since the starting one can be easily rotated (or reflected).
Now I don't have yet any simple argument so I've checked them all.
Unlabeled, net of symmetries, there are 21 configurations and I've grouped them in this way:

• 1 dice with shortest distances from the walls \$\{2,2\}\$ (there can't be more than one)

• 3 dices with shortest distances from the walls \$\{0,0\}\$ (the starting configuration)

• 2 dices with shortest distances from the walls \$\{0,0\}\$

• 1 dice with shortest distances from the walls \$\{0,0\}\$

• 0 dices with shortest distances from the walls \$\{0,0\}\$

And here's an Hamiltonian cycle through all of them! _{thin air}

So as wished... Yes:

\$A)\$ Assuming the correct dice labeling, any configuration having no dice at distance \$1\$ from a wall is reachable.

Speaking of dices labeling... The board is small enough to keep the dices from permutating one another, they can only rotate like a nano version of the 15 puzzle.
Furthermore from every configuration we can always scatter the dices to their nearest corner and using these as dices clips we can say:

\$B)\$ The "clockwise order" is always retained.

Former approach digression

Check for \$A)\$ is quite straightforward, but check for \$B)\$ can be fancy.

My former approach (≥ 111 bytes answers) was to calculate the two vectors connecting respectively dices 1->2 and 2->3 using their nearest corners as points.
For example in the starting position these vectors would be (0,0)->(1,0), (1,0)->(1,1), read as binary numbers 0010, 1011 = 2, 11

(0,0)________(1,0)  
    |     <  |      Out of 12 possible vectors only 4 violate the clockwise order
    |v       |      they form the numbers 1, 7, 8, 14
    |      ^ |      all satisfying v%7<2
    |__>_____|
(0,1)        (1,1)

Fun fact: former code was blundered, it put together correctly only the first vector.
Good news I was already thinking of a way to collapse this operation into a single check instead of two.

How

There are 24 sets (4 choose 3) of corners, 12 in clockwise order, 12 in counterclockwise order.
Combining them into one single binary number (instead of analyzing two vectors) give us the opportunity to execute a single check.
Inspired by this answer I wrote a C program to brute-force the decision problem out of these numbers.

 corners  c |   (9*32^c)*2  | c%46 | c%14 |  <5           Examples
------------+---------------+------+------+-------
 000110   6 |      588      |  36  |   8  |   no        
 000111   7 |      590      |  38  |  10  |   no        3 ________ 2
 001001   9 |      594      |  42  |   0  |  yes         |        |
 001011  11 |      598      |   0  |   0  |  yes         | 011000 |
 001101  13 |      602      |   4  |   4  |  yes         |        |
 001110  14 |      604      |   6  |   6  |   no         |________|
 010010  18 |      612      |  14  |   0  |  yes        1
 010011  19 |      614      |  16  |   2  |  yes        
 011000  24 |      624      |  26  |  12  |   no        
 011011  27 |      630      |  32  |   4  |  yes          ________ 1
 011100  28 |      632      |  34  |   6  |   no         |        | 
 011110  30 |      636      |  38  |  10  |   no         | 101101 | 
 100001  33 |      514      |   8  |   8  |   no         |        | 
 100011  35 |      518      |  12  |  12  |   no         |________|
 100100  36 |      520      |  14  |   0  |  yes        3          2
 100111  39 |      526      |  20  |   6  |   no        
 101100  44 |      536      |  30  |   2  |  yes        
 101101  45 |      538      |  32  |   4  |  yes        3 ________ 
 110001  49 |      546      |  40  |  12  |   no         |        | 
 110010  50 |      548      |  42  |   0  |  yes         | 011100 | 
 110100  52 |      552      |   0  |   0  |  yes         |        | 
 110110  54 |      556      |   4  |   4  |  yes         |________|
 111000  56 |      560      |   8  |   8  |   no        1          2
 111001  57 |      562      |  10  |  10  |   no

Answer 2

Python 3, 209 bytes

B=[[0,0,5,0,0,5]];exec("B+=[b[:D]+[d*min([-5*~d/2]+[b[x]*d-3 for x in((D+2)%6,(D-2)%6)if d*b[x]>d*b[D]and-3<b[D+1-D%2*2]-b[x+1-D%2*2]<3])]+b[D+1:]for D in range(6)for d in(-1,1)for b in B];"*12)
B.__contains__

Takes a list of six numbers, where the 1st and 2nd numbers are the x and y coordinates (0-indexed) of the upper left corner of the first dice, etc.

Explanation

This is extremely inefficient as B will theoretically be a list of length 9.7e12

The brute force code

def overlap(corner1, corner2):
    return -3 < corner1 - corner2 < 3

def move(board, direction, dice):
    other_dice_pos = [board[i] for i in [0, 1, 2] if i != dice]
    dice_x, dice_y = board[dice]
    new_board = board.copy()
    if direction in "EW":
        if direction == "E":
            new_pos = 5
            for (x, y) in other_dice_pos:
                if overlap(y, dice_y) and x > dice_x:
                    new_pos = min(new_pos, x - 3)
        else:
            new_pos = 0
            for (x, y) in other_dice_pos:
                if overlap(y, dice_y) and x < dice_x:
                    new_pos = max(new_pos, x + 3)
        new_board[dice] = (new_pos, dice_y)
    else:
        if direction == "S":
            new_pos = 5
            for (x, y) in other_dice_pos:
                if overlap(x, dice_x) and y > dice_y:
                    new_pos = min(new_pos, y - 3)
        else:
            new_pos = 0
            for (x, y) in other_dice_pos:
                if overlap(x, dice_x) and y < dice_y:
                    new_pos = max(new_pos, y + 3)
        new_board[dice] = (dice_x, new_pos)
    return new_board

initial_board = [(0, 0), (5, 0), (0, 5)]
possible_boards = [initial_board]
previous_length = 0
iteration = 0

while len(possible_boards) > previous_length:
    previous_length = len(possible_boards)
    new_boards = []
    for board in possible_boards:
        for dice in (0, 1, 2):
            for direction in "ENSW":
                new_board = move(board, direction, dice)
                if new_board not in possible_boards:
                    new_boards.append(new_board)
    possible_boards += new_boards
    iteration += 1

print(iteration)

shows that every reachable board is at most 12 steps away. In the code, we use six numbers to represent each board state and each move changes exactly one of them. To unify the four cases in the move function, we encoded the moves slightly differently.

D represents the index of the changing number and d is -1 if the move is towards the top or the left and is 1 otherwise.

Then (D+2)%6 and (D-2)%6 are the indices of the coordinates in the moving direction for the stationary dice. moves from the index. Adding 1-D%2*2 shifts to the coordinates for the stationary direction. We also use the fact that max(a,b,c)=-min(-a,-b,-c) and a>b iff -a<-b. (The implementation has been checked to agree with move function up to a difference in encoding the move for all possible board positions)

The rest of the code is just simply generating all board states reachable in 12 steps and checking if the given one is one of those.

Answer 3

Jelly, 75 65 bytes

ÄṪ€µŒcạ/€<3¬aÆi%7Ȧ
⁴Dp`ṖÆịW,þ@⁹¦ı*Ɱ4¤¹WŒḊ?€ŒpÄÇ¿Ṫ€$€ʋⱮ3$€ẎẎQƲƬẎQċ

Try it online!

A pair of links that takes a list of three complex numbers as its argument (indicating upper left position of the dice, with the top left of the grid being (1+1i)) and returns 1 for valid final positions and 0 for invalid positions. Brute force is used to find all possible reachable positions and then the list of positions is checked. The first 7 bytes of the main link are spent constructing the initial position - removing this would allow this pair of links to be supplied with two arguments, an initial and final position, and would determine if you can reach one from the other.