The cruellest RollerCoaster Tycoon park created

Re:The cruellest RollerCoaster Tycoon park created by mdf on Saturday March 11, 2017 @04:41AM (#13844928)

This got me thinking: given the same space, how does one create the hardest to solve maze? Obviously, you’d need to define hardest with some kind of objective metric. For AIs, this would probably be the amount of calculations performed, or time taken to solve. It would also depend on the algorithm used for solving the maze: for perfect mazes (mazes with only one solution) you could use tree search algorithms, whereas if you had loops, you would have to use graph search algorithms.

There’s some thinking about the same problem (although from a human point of view) in this Stack Overflow question:

http://stackoverflow.com/q/14692818/2096560

[ Parent | on HN ]

Re:The cruellest RollerCoaster Tycoon park created by adekok on Saturday March 11, 2017 @10:46AM (#13845759)

One limit is that if you've searched every square of a maze, you're guaranteed to have found the exit.

So if you want to have a harder maze than that, you must visit each cell more than once. i.e. lots of backtracking.

If you have N dead ends (i.e. leaf nodes), the node before them must be visited twice (down and back up again). The previous node can be visited at most 4 times (in, down and back for each edge, and back out again). Past that, limitations due to geometry will slow down the growth of possibilities.

[ Parent | on HN ]