I've been trying to solve the following problem using adjacency matrix to find the shortest path between the entry and the exit of this labyrinth. The trick on this is that you can't exit a node using the same colour you've entered it so every node ends being 3, one for each colour, and you get an assymetric adjacency matrix and with software solve the directed graph using dijsktra. The problem I have is that I've spent a lot of hours trying to solve it but I can't get the adjacency matrix right and can't find any info on this problem on the internet. Every time I re-do the adjacency matrix the algorithm can't find the shortest path so I'm starting to wonder if there's no possible path between the two points. I'm posting it here for two reasons:
- This problem was posted on Scientific American magazine so maybe someone here has seen this maze before and knows the answer.
- Is there any easier way to find the adjacency matrix or solve it to avoid working with a 61x61 matrix? (Maybe some software where I can manually draw the graph and then solve it or something similar?)
I've been using matlab to solve it for now. I'll try to upload the .m file containing the matrix I've been working with if someone could be interested to check it. Any info will be really appreciated. Thanks
A solution is HRTHAOWBENK. I found it in a few minutes by hand, going from the end to the top and trying to reach the bottom.