# A-maze-ing Dice

This is an entry to the 12th fortnightly challenge

"So you have escaped my labyrinth of words, and now you think you are free, do you? Well, I have news for you: Think again! Ha Ha Ha Ha"

Having just left the maze of words, your spirits sink to an all-time low, when the omnipresent voice of the mad wizard reaches you again.

"Don't worry too much. The way is clear and easily marked on this map, my friends. All you need is to go from the blue arrow to the exit-path with the green arrow. What could be easier?"

Looking at the little map, you get your hopes up. You've been through more difficult things in the past!

"Of course, there is a catch. I will also give you two dice, and three more can be found in the maze."

A set of two dice appears before you.

"These dice will bind your very steps. Be assured there is a way to the exit, but you will never, ever find it. Ha Ha ha Ha Ha!"

## Rules of this maze

Look at the full-resolution map and notice the regular grid.

• A step from one square-centre to the next is consider 'one step'.

• You start on the square where the blue arrow points to.

• You win, when you reach (exactly) the square where the grey, winded path begins.

• You are given a blue and a green die at start. Each face of a die shows a direction and a number.

• At start, pick either of the dice and align its top-face such that the arrow is parallel to the up-down-axis of the map. The axes of the die and of the map remain 'locked' to each other throughout the puzzle. (i.e. it does not matter in which direction a walking person in the maze would look.)

• You 'walk' through the labyrinth by following the instruction of the up-facing die face and then tilting the die to any side (90 degrees) to bring a new face up.

• You are not allowed to rotate the die, i.e the orientation of the top-face is purely given by the tilt. For clarification:

• You are not allowed to tilt the die back from where it just was.
(Therefore, at every step, you have 3 tilt-options available to you.)

• You always go exactly the given number of steps in the given direction. If this is not possible, then the move is forbidden.

• You are generally not allowed to switch the die you use, i.e. once you started with the blue die, you can only tilt and use that one.

• When your move ends you on a tile showing a grey die with a question mark, you are allowed to change dice. You may choose any of your dice and you may orient it as you like to start with. (But from then on, it's only tilting and using this die again.)

• When your move ends you on a tile showing a coloured die, you gain a new die of that colour to your pool. (Note, that passing such a tile does not allow you to pick it up. Also note, that you may not immediately use that new die.)

• Finally, there are a few coloured blocks on the map. You may pass them only while using the die of matching colour for your movements.

The 5 coloured die (blue & green in your possession at start.) have the following meshes:

### An example of the first three possible steps:

• User chooses blue and the 4-Arrow pointing "upward" (in the map)

• User steps 4 fields "up" on the map, as shown by the top face.

• User tilts the blue die to the right. (So that the right side comes up)

• User steps 3 fields "right" on the map, as shown by the top face.

• User tilts the blue die towards the front. (So that face facing away comes up)

• User steps 1 field "up" on the map, as shown by the top face.

• @Arth "...Also note, that you may not immediately use that new die.)" – dcfyj Jul 15 '16 at 15:46
• My only question is: when a move is forbidden does that mean I can tilt to that move but not do it or that I can't tilt to that at all? – dcfyj Jul 15 '16 at 15:48
• Another clarification question. What happens if you rotate the die and you run into a wall before finishing the number of steps? Simplest example would be if you started with the Blue die in the 3rd position of your example, then rotated so the next move was left into the wall. – Poolsharker Jul 15 '16 at 15:50
• "you are allowed to change dice". – Jiminion Jul 15 '16 at 16:38
• @DooplissForce yes, you can "keep" your die but place any face (on orientation) you want to the top. Just like when you start the maze. – BmyGuest Jul 15 '16 at 17:13

I used the rules of the puzzle to create a list of states, and a list of allowable transitions between these states. Each state consists of a unique combination of the following:

• The current position on the grid
• The current die color and orientation
• The previous die orientation
• Which dice have been collected

I estimate that there are about 1,600,000 legal (but not necessarily reachable) states. In order to avoid having to handle every single one of them I used a simple breadth-first search algorithm to explore the reachable subset of states.

I start with the 48 starting states (there are 2 dice to choose from, each die has 6 faces to start with, and each face can be oriented 4 ways). Then, for each new state I try to move the die according to its top face. If that move is allowed (doesn't cross any walls or wrong-colored barriers) then I add three new states in the new position with the three possible new orientations.

There are two special cases. If the die lands on a colored die pickup, I add that color to the list of collected dice. If the die lands on a question mark spot, I add 24 new states (one for each orientation) for each of the collected dice.

The total number of states this algorithm explores before finding a solution is just under 18,000; a much more manageable number. (In fact, the total number of reachable states is only 18,359; 12,051 of which are dead ends.) The 80-move solution it finds is as follows:

use green    go left 3    tip left     go down 1    use purple   go right 3
go up 4      tip up       go right 1   use red      go right 2   tip left
tip down     go down 1    tip left     go right 3   tip down     go down 4
go right 3   tip right    go up 4      tip left     go up 4      tip left
tip left     go left 2    use green    go down 3    tip right    go left 1
go up 2      tip right    go right 2   tip up       go left 1    tip left
tip left     go left 3    tip down     go down 3    tip down     go down 1
go right 1   tip right    go up 1      tip left     go down 1    use red
tip down     go up 3      tip down     go right 1   tip right    go left 3
go down 2    tip down     go left 4    tip up       go left 2    tip down
tip right    go up 3      tip right    go down 2    tip down     go down 3
go right 2   tip right    go up 3      tip up       go down 4    tip left
tip right    go left 1    tip down     go down 3    tip down     go down 2
go up 4      tip down     go left 2    tip left     go right 4   tip left
tip down     go up 2      tip left     go down 2    tip right    go left 1
go right 3   use blue     go down 4    tip left     go down 2    tip up
tip left     go right 1   tip down     go left 1    tip right    go right 3
go up 2      tip right    go right 1   use red      go right 2   tip left
tip up       go up 3      tip left     go down 2    tip right    go right 3
go left 4    tip down     go down 1    tip left     go up 1      tip down
tip left     go right 4   tip left     go right 2   use blue     go up 1
go down 1    tip down     go right 3   tip left     go right 3   tip left
tip up       go down 1    tip up       go right 3   tip left     go right 2
go left 1    tip right    go up 4      tip up       go right 1
tip left     go up 3      tip left     go up 3      tip left
go up 2      tip down     go right 2   tip up       go down 1
use red      go up 1      tip up       go up 2      tip down


The path it takes looks like:

(As a bonus, the complete exploration of the space can be found here.)

• Have good rest. I'm waiting for the full post... – BmyGuest Jul 17 '16 at 12:54
• I didn't check the full list, but from #8->#12->Exit looks good. Well done. – Poolsharker Jul 17 '16 at 17:13
• Are you going to add a visual solution as well? – BmyGuest Jul 18 '16 at 5:35
• Thanks for the picture. I can confirm, that this is the solution I had in mind. (The yellow die was a decoy) – BmyGuest Jul 19 '16 at 15:07

Bridging a gap in DooplissForce's Answer:

From Grey cube #4 in the path dcfyj found.
Change to Red Cube.
Go east 3.
Rotate left to go south 3.
Rotate away to go south 3.
Rotate left to go east 1.
Rotate away to go south 2.
Rotate away to go south 3.
Rotate left to go south 2.
Rotate left to go west 1 and stop on a Grey cube.

Building on what Business Cat posted.

1. Go north 4.
2. Rotate toward you to go east 3.
3. Rotate left to go north 2.
4. Rotate left to go east 1 and collect the red die.
5. Rotate towards you to go south 2.
6. Rotate right to go east 2.
7. Rotate right to go north 4.
8. Rotate towards you to go east 3.
9. Rotate left to go north 2.
10. Rotate away to go west 4.
11. Rotate left to go south 1.
12. Rotate away to go west 1.
13. Rotate left to go north 2 and stop at a gray die.

• I believe move 13 should be "...north 2..." – dcfyj Jul 15 '16 at 18:21
• @dcfyj Yep, fixed. – Poolsharker Jul 15 '16 at 18:22
• @2012rcampion You are correct, fixed. – Poolsharker Jul 17 '16 at 17:01

Building on Business Cat's and Poolsharker's path

1. Go north 4.
2. Rotate toward you to go east 3.
3. Rotate left to go north 2.
4. Rotate left to go east 1 and collect the red die.
5. Rotate towards you to go south 2.
6. Rotate right to go east 2.
7. Rotate right to go north 4.
8. Rotate towards you to go east 3.
9. Rotate right to go north 2.
10. Rotate away to go west 4.
11. Rotate left to go south 1.
12. Rotate away to go west 1.
13. Rotate left to go north 2 and stop at a gray die.
New Part:
14. Switch to the Red die.
15. Go West 3.
16. Rotate Away to go South 1.
17. Rotate Right to go West 2.
18. Rotate Right to go West 3.
19. Rotate Right to go North 3.
20. Rotate Toward to go North 3.
21. Rotate Right to go West 1.
22. Rotate Toward to go North 2 and arrive at Grey Cube #2.
23. Change to the Blue die.
24. Go East 1.
25. Rotate Right to go North 3.
26. Rotate Toward to go East 4.
27. Rotate Toward to go South 1.
28. Rotate Right to go North 3.
29. Rotate Toward to go North 1.
30. Rotate Left to go East 1.
31. Rotate Left to go North 4 and arrive at Grey Cube #3.
32. Change to the Green die.
33. Go East 2.
34. Rotate Toward to go North 1.
35. Rotate Toward to go West 4.
36. Rotate Right to go North 3.
37. Rotate Toward to go West 2.
38. Rotate Left to go South 4.
39. Rotate Toward to go East 1.
40. Rotate Left to go South 1 and pick up the purple die.
41. Rotate Left to go East 3.
42. Rotate Away to go North 4.
43. Rotate Left to go East 2.
44. Rotate Away to go South 1 and arrive at Grey cube #4.
45. Change to the Red die.
46. Go North 3.
47. Rotate Toward to go East 2.
48. Rotate Toward to go North 2.
49. Rotate Right to go East 1 and arrive at Grey cube #5.

To add on to what everyone else has, here's the grid marked up with everything I've found so far:

Edit (7/15 8pm EST): Updated the grid with Poolsharker's bridge:

X's on the diagram show where, instead of going straight from one square to another, you stop halfway through (e.g. going 2 north then 3 north). The list of moves on the right shows the turns you have to make for the cubes.
- The first list is the left branch, which goes from the start through grey cubes 1 through 5.
- The second list is the bridge, which connects the left and middle branches via grey cubes 4 and 6.
- The third list is the middle branch, which starts at grey cube 1 connects it to 6 through 8.

• See my updated answer, I found a way to bridge the gap between left and right. – Poolsharker Jul 15 '16 at 20:43
• @Poolsharker Yeah, I had found that path and was trying to use it to get the yellow, no success so far. – dcfyj Jul 15 '16 at 20:46
• Also, it might clash with the red cube direction required to reach the right side, so I was waiting for the OP to respond to my query. – dcfyj Jul 15 '16 at 20:47
• @dcfyi OP answered Doopliss's similar question already. DooplissForce yes, you can "keep" your die but place any face (on orientation) you want to the top. Just like when you start the maze. – BmyGuest 3 hours ago – Poolsharker Jul 15 '16 at 20:55
• +1 for having a graphical version. More like this is needed! – BmyGuest Jul 15 '16 at 23:16

Observation:

I'm going to use compass directions because I think it will be less ambiguous. North is up on the map (obviously).

You can collect the red die if you start with the green die.

1. Go north 4.
2. Rotate toward you to go east 3.
3. Rotate left to go north 2.
4. Rotate left to go east 1 and collect the red die.

Then,

You now have the green die with the 1 (on the right side of the mesh) pointing east.

Still working out how to move away from the red die...

• pretty sure that hits a dead end – dcfyj Jul 15 '16 at 18:00
• with poolsharker's post I'm very much so proven wrong lol – dcfyj Jul 15 '16 at 18:25

Some ideas:

There are a relatively small number of ways to get to the end. These can be represented as a series of 1 step moves: up, down, left, or right.

These move sequences could be represented by a set of labelled numbers. Based on these sequences, you can compare original die settings, then check to see which ones can support a successful sequence. (For some reason, this reminds me of the moving wood block puzzles.)

All that being said, I'm not sure I could solve this, but could probably write a python program that could solve it. The puzzle has a relatively small number of state variables, so start a simulation and finish if and when you are at the end point.