2 ms·
> But does anyone know a good metric for maze difficulty? I think there are a bunch of problem-definition details that would need to be hammered out first, ex:
by Terr_ 2y ago
> But does anyone know a good metric for maze difficulty?
I think there are a bunch of problem-definition details that would need to be hammered out first, ex:
1. Is this solving the maze with perfect knowledge of its layout--a bird's eye view from above--or does it require gradual exploration to fill out the contours?
2. If it requires exploration, how far can you see? Do you need to actually spend a move to enter a square to know whether it is a dead end, or can you tell from N squares away? Is the viewer constrained by trigonometry, where they can only uncover partial knowledge about nearby rooms and small geometric quirks can have a big effect on exploration progress? Is there a distance limit to vision?
3. If it requires exploration, is there a cost to backtracking, or--like DFS--can you simply teleport between all places you've already been without a cost?
4. Is a "difficulty" rating across mazes based on a single algorithm, or the best-possible choice for that particular maze from a set, or does it represent the average expected effort expended by a particular population of different people/algorithms?
____
- bee_rider 2y agoRight; I didn’t do any of that because I’m more curious if somebody has already done it. Generally with CS stuff I find there’s somebody who’s already poked around the maze a bit and found a neat path to explore. :)