You're trapped in a maze. There is a way out. Path junctions are all 3-way.
If you use the strategy of always taking the path going right, what will happen?
(Note: This problem is deliberarely vague.)
testing yields:
5 nodes, 1000 mazes, 10 runs per maze
runs: 10000 exits: 6531 ratio: 0.6531
10 nodes: 1000 mazes, 10 runs per maze
runs: 10000 exits: 5692 ratio: 0.5692
50 nodes: 1000 mazes, 10 runs per maze
runs: 10000 exits: 5204 ratio: 0.5204
100 nodes: 1000 mazes, 10 runs per maze
runs: 10000 exits: 519 1 ratio: 0.5191
maze construction algorithm:
1. Construct all the nodes
2. partially attach 1 node to another node
- select the nodes to be attached randomly
- select the path that links them randomly
3. repeat step 2 until all nodes (except exit) are fully attached (ie have their 3 paths linked)
maze walking:
1. start at a random node and path
2. walk until exit or number of paths is greater
than 3 * number of nodes
if anybody wants the (java) program to verify ill be happy to send it :)
possible results
