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.