Thank you for the quiz,
I took great pleasure in this quiz, and I'll even share some of themore stupid ideas I followed while solving this. After last weeksdesaster, I don't have any more carma to loose ;)
First all the solutions can be seen on this page:
http://ruby.brian-schroeder.de/quiz/mazes/
It may load a little bit slow, because there are live demos of thealgorithms on this page.
Following there is a description of the algorithms. For the ruby code,please visit the page linked above.
= Stupid Solution (Take out edges)
   1. Create a full maze, where each node is connected to all neighbors   2. Randomly remove connections from the maze, until no moreconnections can be removed without breaking the graph in two cliques.         1. Randomly choose an edge {n,n'}         2. Remove the edge {n,n'}         3. Check if there exists another path between n and n'               1. yes => iterate further               2. no => add the edge again and try another edge
I implemented this method and it takes really long to calculate themazes. (On my laptop it takes 90sec for a 30x30 maze)
A maze calculated with this algorithm:ooooo        ooo o  o   ooo   ooooo  o o        ooooooo                                            Took: 0.110028028488159s
= Divide and conquer
One more approach would be a divide and conquer approach
    * Generate a small maze    * For each node in the maze substitute another maze and connect ata random edge node.
This creates a valid maze, but will not create every possible validmaze. In fact the mazes created by this method are a bit boring.
But this approach is quite fast. It takes 0.7sec for a 30x30 maze onmy laptop, when using teh intelligent solution as a base case
A maze calculated with this algorithm:ooo                                       ooo  oooooooo                 oo  o   o                                 oo  o    o                    oo  o   ooo                                   oo   o    o        oo oooo                                       oooo  ooo    o              o oo  ooooo ooo                               o o    o    ooo       o oo  oooooooooooooo                             o ooooooo    oo ooo       o     ooooooo ooo  ooooooooo                    ooo           oo                  o                      ooooooooooo                o  o                     o  ooooooooooooooooo      ooooooooo             oooo                  ooo  o              ooooooooo                   o o                       o ooo                                      oo                    ooooo                                                                                                                                                                                                                                                            Took: 0.590821027755737s
= Intelligent approach
After some considerations I saw that we are searching a spanning treehere. Minimal Spanning trees can be calculated in +O(n log n)+ socalculation of a random spanning tree is possible in at most +O(n logn)+.
Here is the algorithm
    * Pick a random startingnode n0    * Initialize a set of already added nodes to included = {n0}    * Initialize a set of queued edges q = {{n,n'}  edges | n = n0}    * while edges /= {}          o remove a random edge {n,n'} from q, where n  included, n' included          o add n'.edges to q          o add n' to inlcuded          o add {n, n'} to the graph
and the ruby version
start_node = self[rand(@width),rand(@height)]included = Set[start_node]edges = start_node.edges.dupwhile edge = edges.pop_random  next if included.include?edge[0] and included.include?edge[1]  edges.concat(edge[included.include?(edge[0]) ? 1 : 0].edges)  included << edge[0] << edge[1]  edge.active = trueend
This algorithm creates a nice 30x30 maze in 0.5sec
A maze calculated with this algorithm:ooooooo                                     oooooooooo               o   o                                          o         o              o      o                                    o         o              o      ooooo                                   o       o             o           o                               ooooooo       o           o            ooo                       ooooo            o           o           o                           ooo                     o           o          ooo                           o               o       o               ooooo                          o              o       o                    ooooooo                  o               o       o                       ooooooooooooo          o                   o    o                                   o       ooooo                      o   o                                  oooooooooooo                        oo                                 ooo                                                                                               Took: 0.243410110473633s
= Long path maze
It is possible to create a maze with a very long path by a simplevariation of the spanning tree algorithm. We just implement the set ofqueued edges q as a queue and add the shuffled edges of each addednode to this queue. This results in a randomized depth first searchand a very long path with a few sidepaths.
A maze calculated with this algorithm:o  ooo  ooooooo                                      oooooooooo oooo         o o ooooooooooo                               o      ooo            o  oooooooooooo                                   o     o          o        o                                           o         o          o     oooooo                                 ooooooo  ooo            o ooooooo  ooooo           ooooo                      o ooooo     oo      o ooo  ooo   o           o ooo                   o oooo o o o       ooooooooo   oooooooooo   o   o                   ooooooo ooo o  o    ooooooooooooooooooo o   o  o                ooooooooooooooo o o o     o oo     oooooooo o  o   o                ooooooooo oo  ooo o o  o o      o oo    ooooo o o   oooooo                    ooo oo  oooo ooo    o  ooo  oooo oooooooooooooo       ooooo    ooooooooo   oo ooooooo oo  o    ooooooooo   ooooooooooooo ooooooo o    o         oooo oooo o  o    oooooo  o        oo   ooo  ooo       o     o       oo   oo oo oo     ooooooooooo         ooo    ooooooo          ooooooooo         Took: 0.481090068817139s
= Find longest path
I implemented one algorithm to find the two nodes with maximumdistance in the graph. This is done by first calculating the distanceof every node to every other node in the tree.
Anyhow, here is the algorithm:
    * Initialize a n x n distance matrix +d+ with 0 on the diagonal, 1if two nodes are directly adjacent or infinity otherwise.    * Initialize a queue q = {n1,...,nn} with all the nodes.    * Until the queue is empty pop one element n_i.          o For nj  {n1, ..., n_n}                + Set the distance ni, nj to min{d[ni, nj], d[ni, n']+ d[n', nj] | n'  {n1,...,nn}}                + If the distance has changed and ni is not in thequeue add ni to the queue                + If the distance has changed and nj is not in thequeue add nj to the queue
This iteratively relaxes the distances using the triangle-equationd(ni, nj) 顢 d(ni, n') + d(n', nj)
After having all the distances I simply search the maximum and havethe start and end node.The time complexity is as follows:
    * The longest distance in a maze is n    * => Each node can be relaxed at most n times    * Only relaxed nodes are added to the queue    * => Each node is added at most n times to the queue    * Relaxation of a node takes at most n steps    * => Total time complexity is O(n³)
A path found with this algorithm      ooo    oooooooooooo  oooooooo   o o o     oooooooTook 0.543197870254517s
= Find path with maximum distance - second try
The above algorithm is quite slow, so I reimplemented another fasteralgorithm. Here I use more knowledge about the graph to speed up thesearch.
I search from each leaf the distance to each other leaf. A longestpath will always start and end in a leave. As most nodes are notleafes this takes down complexity a lot. Secondly, I know that fromleaf end there is only one non-cylic path to each other leaf, so asimple depth first search will find all distances in O(n) time. (Eachnode is visited only once). That means I can come away with a total ofO(n²) time. And indeed for a 10x10 maze this algorithm finishes inunder 1 second, while the above needs nearly 30 seconds.
A path found with this algorithm                   ooooo      o o   ooooooooooooooooooo oo o   oo   o                ooo       oo    o              oooo    ooo            ooooo o    o      ooooooooooooooooooo                                 Took 0.311852216720581s
best regards,
Brian
-- http://ruby.brian-schroeder.de/
multilingual _non rails_ ruby based vocabulary trainer:http://www.vocabulaire.org/ | http://www.gloser.org/ | http://www.vokabeln.net/