Explanation of my solution
Die Agony - December 2022
Initial Brainstorming
Here is a copy of the grid from the puzzle:
My first assumption was that the die was numbered from 1 to 6. However, after the first move, landing on '5', we are already unable to move anymore.
Then I considered allowing decreases in values to reach the '-7' square. However, after a few other moves, we also get stuck.
Then I quickly realised the complexity of this puzzle. In addition to finding a path that could lead to the blue square, the main idea was that all six die values were unknown. And we had to find them.
Potential Breakthrough
Without knowing the real die values, we had to resort to verifying divisibility.
We needed to make sure that the difference of the square we would land on would be a multiple of N (where N represents the number of moves).
An elegant way to do this was to verify the congruence on N between the current value and the next value.
(I stole this idea from a fellow puzzle solver at Concordia).
For example to check if we could move from ‘-7’ to ‘2’ on move 3, we would simply verify that -7%3 == 2%3.
Depth First Search
Given that we are trying to find an optimal path from one vertex to another,
It only feels right to use Depth First Search to iterate through the squares of the grid.
I began by copying the general implementation of DFS.
Then I adjusted the constraints on when a square would be added to the stack.
After some additional system outputs and debugging, I quickly had some code running.
Roadblocks
However, there were many issues with my implementation.
First of all, I did not know whether I should allow squares to be revisited or not.
Secondly, my implementation did not consider different possible paths of the die,
it was totally unable to backtrack from a dead-end and resume from the last junction.
Finally, and most importantly, the path never managed to reach the blue square.
Persistence
I kept trying many variations of my initial program.
I began by allowing repetitions. Then I tried to implement the solution backwards.
Finally, I managed to make backtracking to a previous state work smoothly.
The outputs were promising, there seemed to be a sequence that could lead from N = 32 to N = 11.
I also kept track of die values, to make sure that they made sense.
I was also using a real die to have a visual understanding of moves in a grid.
To finally solve the puzzle, I ended up having to manually iterate the first 10 moves in my backward solution.
There weren’t that many possible paths since all six die values were already determined by this point.
Overall, it took me almost 2 complete days to solve this puzzle. It was a lot of pain and persistence.
But the joy of seeing my team’s name on the leaderboard made it quite worth it.
Resources
Here is a collection of resources that were helpful to me:
Finally, you can find the source code of my solution here.