Earlier quoted context omitted.
That's a very interesting. I am curious to hear what your answer was :D Here's my thoughts on what a solution would need: 1. At least one path from source to target. 2. Some quantification of hardness. No of steps in optimal path? Number of turns in optimal path? Number of paths? Some weighted combination of all three? Some preliminaries: Finding optimal path, and finding number of paths can both be down in O(N^2) us…
Well, I addressed the "neither easy nor hard part" upfront. My take was there has to be a solution and that too 1 solution. In other words, it had to be fair. Second was the degree of false paths (term I made-up). This essentially governs the branching of each false path. Higher the degree higher the branching and higher the backtracking. This would make the maze harder. So my algo was 1. To generate a valid path fro…
Here's a linear solution I came up with, before I took a look at the rest of the thread:
1. Think of the 100x100 as pixels on a black background, all set to 0, i.e. all open space.
2. Now, draw a white square border all the way round by setting all the outer pixels to 1. No one can get in.
3. Leave a pixel gap and draw another square border within and then another and so on, like Russian dolls, with a pixel passage way between them. No one can get in.
4. Now, for each square border choose 1 random pixel and open it up by setting it back to 0. Now we're guaranteed of a solution, but it's too easy.
5. Let's make it a little harder, so between each square border let's drop a single pixel of "rubble" to block each passage way at one point. Provided we don't drop it directly in front of an opening in the adjacent square borders, I believe (unless I made a mistake somewhere!) we know the maze remains solve-able, and we don't need to do any iteration or "walk through the maze" to check that.
6. So far the runtime is pretty good. Nice and linear in the number of pixels drawn. We know the maze can be solved. And it's not too easy and not too hard.
7. (optional) We can make it harder still by tentatively dropping another pixel of rubble in a random passage way, and then walking through the passage to check that we can still reach the next inner opening. This is still better runtime than solving the whole maze, and can be tuned by the difficulty factor.
The insight is simply not to attempt to explore paths at all, i.e. not to try and "solve the maze" but only to "generate the maze", unless 7 is chosen, but that's probably not essential to the challenge.