In 1980, while working at Texas Instruments, I wrote a program to draw mazes one night. My first version started out quite simple and elegant, but the mazes it printed (on our departments line printer) weren't very difficult to solve. The next night I improved the mazes produced by the program, adding tweaks here and there in the code to make the mazes harder to solve. I added long winding dead ends, corridors with loops and so forth. The mazes caught on and soon many cubicles had the three page mazes with hand drawn solutions as decoration. Marketing folks headed to a trade show saw these mazes and wanted the program to run on a system on the trade show floor so that personalized mazes could be handed out as trade show swag.
Unfortunately, version two of program wasn't very pretty with all the little hacks and tweaks, but it did make fun mazes. Six or nine months later I got a call from someone wanting help with a Pascal program (I was one of the Pascal experts in the company at the time so I would get calls like this). As they described the program on the phone, I recognized it as my maze program. They said they got it off of the distribution tape for the TI Pascal compiler (I had programmed the program in Pascal). I was mortified that someone had made the ugly program a sample program for a TI product but at least it didn't have my name on it!
If you want to create a maze on paper as a rainy day kind of activity, the process is basically the same but manual:
1. Mark a start point and an end point, and draw the solution using yellow marker. A moderately windy path will do fine. Don't overdo it, or you'll actually make it too easy.
2. Using the same yellow marker, draw branching paths off from the solution path, and make branches off the branches until the maze area is too cramped to draw more.
3. Draw walls with black marker between and around the yellow paths.
The first link is interesting because it describes some maze toponomy (types and characteristics of mazes)
The second has a lot of algorithm implementations with nice demos.
My favorite presentation ever, by Jamie Buck at RubyConf2011, is a great interactive survey of maze generation algorithms -- "Algorithm" is Not a Four-Letter Word:
That presentation was recorded by Confreaks [1] who let you download the video (and audio!) at different resolutions.
The Ruby community is really well-served by Confreaks [2] - they record and provide videos from many different Ruby conferences and have (over the years) expanded their remit to include Javascript, Scala and more.
I used to type an equivalent of this into C64s in stores. I even had a few of these printed out. It does tend to have a lot of short loops but sometimes you get an amazingly complex path for such a simple method.
Jamis Buck has a fantastic series of blog posts about maze generation[1]. It looks like he's no longer updating the blog, but all of the entries are still up. Start at the bottom and work up.
Something interesting about this type of maze is that you can use a flood-fill algorithm on the walls to find a solution. This is because there's exactly one path between the start and finish, and that path divides the the maze into two parts.
A few weeks ago I was fooling around implementing algorithms from that page and Prim's Algorithm looked really cool, so I implemented a version with randomized colors on my homepage: http://jeff.is/
One cool way to make a maze is how the old Windows OpenGL maze screensaver did it, starting with every square having full walls, starting somewhere, and making sure every room has at least one broken wall and they're all connected, traversing it. I forget how exactly it picked the end point. I used that when I wrote a Javascript game about that maze but it was hosted on nyhacker and it's gone now. Might still have it around somewhere on a hard drive though.
I don't have time to read all the links in this thread but I used to draw mazes all the time in school. My approach was to start with an "in" tube and start branching it, so long as I kept one branch open I could split and recombine all the others and know that I still had a valid maze. After I had filled up most of the page I would stop and declare the end position.
It might not be clear from my description but I kept adding paths to the maze by doubling back on what was already there and building it out so it looked like a brain.
The main point is that I kept one path open, never closing all my paths in a dead end. That way I knew there was a solution but since I did them so fast I wouldn't know the solution myself.
Mazes are certainly fun. Here's a javascript maze solver I wrote a while back, including a REST url for building your own maze. http://www.primaryobjects.com/maze
1) Each cell in the maze is a set.
2) Randomize walls. Check if wall to be removed are already in the same set. Merge the set if wall is removed.
3) Repeat until entire maze is in one set.
DFS seems a bit odd for generation. For generating a solution, it would be what I would do.
Unfortunately, version two of program wasn't very pretty with all the little hacks and tweaks, but it did make fun mazes. Six or nine months later I got a call from someone wanting help with a Pascal program (I was one of the Pascal experts in the company at the time so I would get calls like this). As they described the program on the phone, I recognized it as my maze program. They said they got it off of the distribution tape for the TI Pascal compiler (I had programmed the program in Pascal). I was mortified that someone had made the ugly program a sample program for a TI product but at least it didn't have my name on it!