Clifford Heath wrote:
 >...
> Note that you don't use a circular search, so especially
> with large mazes, your random choice is going to take
> longer and longer to find a valid wall. You should choose
> a starting position, then choose an order in which to
> check the two walls, check them both, and if that fails,
> don't choose a new random starting position but step to
> the very next cell and check the walls again (same or
> different random order is ok). Otherwise there's a real
> possibility of *very* long runtimes. For example, to break
> the last wall in a 20x20x20 maze, your random algorithm
> has to loop until it finds one of 167200 candidate walls
> out of a field that might be as small as three walls.
>... 
> Clifford.

Excellent point!  Here's my revised version that should not have this problem.
#!/usr/bin/env ruby

$debug = nil
#
# The algorithm is extracted from:
# <http://www.rubygarden.org/ruby?OneLiners>
#
class Array
   def shuffle!
     each_index {|j|
       i = rand(size-j);
       self[j], self[j+i] = self[j+i], self[j]
     }
   end
end

class Maze
   TOP  = 1
   LEFT = 2
   def initialize(w,h)
     @w = w
     @h = h
     @size = @w*@h
     @maze = Array.new(@size)
     @wall = Array.new(@size, TOP|LEFT)
     @w.times do |i|
       @h.times do |j|
	putMaze(i,j,j*@w+i)
       end
     end
     @order = @maze.dup

     # First, break exactly one top wall
     clearWall(rand(@w),0,TOP)
     # and define the exit column at the bottom...
     @exit = rand(@w)

     # Define the order in which cells and their walls get checked...
     @order.shuffle!

     # Now, randomly break the walls...
     breakWalls
   end

   def getMaze(x,y)
     @maze[y*@w+x]
   end

   def putMaze(x,y,val)
     @maze[y*@w+x] = val
   end

   def getWall(x,y,which)
     (@wall[y*@w+x] & which == 0 ? false : true)
   end

   def clearWall(x,y,which)
     @wall[y*@w+x] = @wall[y*@w+x] & (~which)
   end

   def breakWalls
     breakCount = @size-1
     i = 0
     while breakCount > 0
       val = @order[i% / size]
       y = val/@w
       x = val-@w*y
       puts "i=#{i}, val=#{val}, breakCount=#{breakCount}, calling: breakCell(#{x},#{y})..." if $debug
       breakCount -= breakCell(x,y)
       i += 1
     end
   end

   def breakCell(x,y)
     wall = 1 + rand(2)
     count = breakWall(x,y,wall)
     # Better mazes (longer runs) result if both walls are not checked at the same time.
     # wall = (TOP+LEFT)-wall
     # count += breakWall(x,y,wall)
     return count
   end

   def breakWall(x,y,wall)
     # Don't break LEFT wall for x==0
     return 0 if (x==0 && wall==LEFT)
     # Don't break TOP wall for y==0
     return 0 if (y==0 && wall==TOP)
     x2 = wall==LEFT ? x-1 : x
     y2 = wall==TOP  ? y-1 : y
     return 0 if getMaze(x,y)==getMaze(x2,y2)
     # Found a valid wall to break!!!
     clearWall(x,y,wall)
     # Now, change all numbers in the maze from the higher number to the lower number
     from = getMaze(x,y)
     to = getMaze(x2,y2)
     changePath(from,to)
     return 1
   end

   def changePath(n1,n2)
     higher = (n1 > n2 ? n1 : n2)
     lower  = (n1 < n2 ? n1 : n2)
     @w.times do |w|
       @h.times do |h|
	putMaze(w,h,lower) if getMaze(w,h)==higher
       end
     end
   end

   def to_s
     @w.times do |w|
       print getWall(w,0,TOP) ? "____" : "_   "
     end
     print "\n"
     @h.times do |h|
       @w.times do |w|
	print getWall(w,h,LEFT) ? "|" : " "
	$debug ? printf("%3d", getMaze(w,h)) : (print "   ")
       end
       puts "|"
       if h+1 == @h
	# last row...
	@w.times do |w|
	  print getWall(w,h,LEFT) ? "|" : "."
	  print @exit == w ? "   " : "___"
	end
       else
	@w.times do |w|
	  print getWall(w,h,LEFT) ? "|" : "."
	  print getWall(w,h+1,TOP) ? "___" : "   "
	end
       end
       puts "|"
     end
   end
end

if __FILE__ == $0
   maze = Maze.new(37,28)
   puts maze
end

C:\src>gmlmaze2.rb
_________   ________________________________________________________________________________________________________________________________________
|   |       |       |       |                                           |   |           |           |   |       |       |           |               |
|   |   .___|   .___|___.   |___.___.   .___.___.   .___.___.   .   .___|   |   .___.   |___.   .___|   |   .   |   .   |   .   .___|   .___.___.   |
|   |       |           |           |           |           |   |           |       |       |               |   |   |   |   |       |           |   |
|   |   .   |   .   .___|   .   .___|   .   .   |___.   .   |___|___.___.   |   .   |   .___|___.   .___.___|___|   |   |   |___.___|   .___.___|___|
|       |   |   |       |   |       |   |   |       |   |               |   |   |   |           |               |   |                               |
|   .   |   |___|   .   |   |___.___|   |   |   .   |   |___.___.___.___|   |   |   |   .___.___|___.___.___.   |___|   .___.   .___.   .   .   .___|
|   |   |       |   |   |           |   |   |   |   |                   |   |   |   |                       |       |       |       |   |   |       |
|___|___|   .   |   |   |___.   .   |   |___|___|___|   .___.   .___.___|___|   |   |___.___.   .   .   .   |   .   |___.   |___.   |___|___|___.___|
|       |   |       |       |   |   |               |       |               |   |           |   |   |   |   |   |       |       |                   |
|___.   |   |   .   |   .___|   |   |___.___.___.   |___.___|___.___.___.   |   |___.___.   |___|   |   |___|___|___.   |   .   |___.___.   .___.   |
|   |       |   |   |       |   |               |                       |   |           |       |   |               |   |   |           |       |   |
|   |___.___|___|___|   .   |___|   .___.___.___|   .___.___.___.   .   |   |   .   .___|___.___|   |   .   .___.___|   |___|   .___.___|   .   |   |
|                   |   |       |                               |   |   |   |   |               |   |   |           |       |           |   |   |   |
|   .   .___.___.___|   |   .___|___.___.   .   .   .___.___.   |___|___|___|___|___.   .___.   |   |   |___.   .   |___.   |   .___.   |   |___|   |
|   |               |   |               |   |   |           |                       |       |   |   |       |   |       |   |       |   |       |   |
|___|   .   .   .   |   |___.___.___.   |___|___|___.___.   |   .___.   .___.___.___|   .___|   |   |   .   |   |___.   |   |___.___|   |___.   |   |
|   |   |   |   |   |               |                   |   |       |               |       |   |   |   |   |       |   |           |       |   |   |
|   |   |___|___|___|   .   .___.   |___.   .   .___.   |___|   .___|___.   .   .___|   .   |___|   |   |___|___.   |   |   .   .   |   .   |___|___|
|                   |   |       |       |   |       |       |           |   |       |   |       |   |           |   |   |   |   |   |   |           |
|   .   .___.   .   |___|   .___|   .   |   |   .   |___.   |___.___.   |___|___.   |___|___.   |___|   .___.___|___|___|___|   |   |   |   .   .   |
|   |       |   |       |       |   |   |   |   |       |           |           |           |       |                       |   |       |   |   |   |
|___|   .___|___|   .___|___.   |___|___|   |   |   .___|___.   .   |   .___.___|___.___.   |___.___|___.___.   .___.   .___|___|___.___|___|   |   |
|   |           |           |           |   |   |           |   |   |                   |                           |                           |   |
|   |___.   .   |___.   .   |   .___.   |___|   |   .___.___|___|   |___.___.   .___.___|___.___.   .   .___.   .   |   .___.   .   .___.___.   |___|
|       |   |       |   |   |       |       |   |               |           |                   |   |       |   |   |       |   |           |       |
|___.   |   |   .   |   |   |   .___|___.___|   |   .___.   .   |___.___.   |   .___.___.___.   |   |___.   |___|   |   .___|___|___.___.___|   .___|
|       |   |   |   |   |   |               |   |       |   |           |   |               |   |       |       |   |                       |       |
|___.   |___|___|___|   |___|___.   .___.   |___|___.___|___|   .___.___|___|___.   .___.___|___|___.   |   .___|___|___.   .   .   .   .___|   .   |
|                   |           |       |                   |                   |                   |   |               |   |   |   |       |   |   |
|   .   .___.___.___|___.   .___|   .___|___.   .   .   .___|   .   .   .   .___|   .___.___.   .   |___|   .   .   .   |___|___|___|   .___|   |___|
|   |                   |       |           |   |   |       |   |   |   |       |           |   |       |   |   |   |               |       |       |
|___|___.   .   .___.   |   .   |   .___.   |   |   |___.   |___|___|___|   .___|___.___.___|___|___.   |   |   |   |___.   .   .___|___.   |___.   |
|       |   |       |   |   |   |       |   |   |       |               |                           |   |   |   |       |   |           |       |   |
|___.   |   |   .___|___|   |___|___.   |   |___|___.___|___.___.___.   |___.___.   .___.___.   .___|   |___|___|   .   |___|___.___.   |___.___|   |
|   |       |           |               |                           |           |           |       |           |   |               |           |   |
|   |___.___|   .___.___|   .___.___.   |   .   .___.   .___.___.   |   .   .___|___.___.   |   .   |___.___.   |___|___.   .___.___|   .   .   |___|
|           |           |           |   |   |       |           |   |   |               |   |   |           |           |           |   |   |       |
|___.___.   |___.   .___|___.   .   |___|   |   .   |   .   .___|   |___|___.___.   .___|   |___|   .   .___|___.___.   |   .___.___|___|___|___.   |
|       |       |           |   |       |   |   |   |   |       |               |       |       |   |               |   |                       |   |
|___.   |   .   |___.___.   |___|   .   |___|___|   |   |   .   |___.___.   .___|___.   |   .   |___|   .   .   .   |___|___.   .   .   .___.   |___|
|   |       |           |       |   |           |   |   |   |           |           |   |   |       |   |   |   |           |   |   |       |       |
|   |___.___|   .___.   |___.   |___|___.___.   |   |   |___|___.___.___|   .___.   |   |   |   .   |   |   |   |   .   .___|   |   |   .   |   .___|
|           |       |                           |   |                   |       |   |   |   |   |   |   |   |   |   |       |   |   |   |   |       |
|   .   .___|   .___|   .___.___.   .___.___.   |___|___.___.___.___.___|   .   |   |___|   |   |___|___|   |___|___|   .   |   |___|   |___|   .___|
|   |       |       |           |           |                           |   |   |       |   |           |           |   |   |       |       |       |
|___|___.   |   .   |___.   .___|   .___.   |___.___.   .___.   .___.___|   |   |___.___|   |   .___.___|___.___.___|___|   |   .___|___.   |   .   |
|               |       |       |       |           |       |           |   |           |   |                           |   |           |   |   |   |
|___.___.___.___|___.   |   .___|   .   |___.___.___|___.___|   .___.___|   |   .___.___|___|   .___.   .___.   .   .   |   |___.   .   |   |___|___|
|                   |   |       |   |                       |           |   |               |       |       |   |   |   |       |   |   |           |
|___.___.___.   .   |   |   .___|   |   .___.   .___.___.   |   .   .   |   |___.   .   .   |   .___|   .   |___|___|   |___.___|   |___|___.___.___|
|               |   |   |       |   |       |           |   |   |   |   |       |   |   |   |       |   |           |           |                   |
|___.   .___.   |___|   |   .   |___|   .___|___.___.___|   |   |___|___|   .___|___|___|___|   .___|   |___.   .___|   .___.   |___.___.___.   .   |
|           |           |   |       |                   |   |           |                   |       |       |       |       |                   |   |
|___.___.___|   .   .   |   |___.   |   .   .___.   .___|___|   .   .___|   .___.___.   .___|   .___|___.   |   .   |___.   |___.___.___.___.___|___|
|               |   |   |       |   |   |       |           |   |       |           |       |           |   |   |       |                           |
|___.___.___.___|___|___|___.___|___|___|___.___|___.___.___|___|___.___|___.___.___|___.___|___.___.   |___|___|___.___|___.___.___.___.___.___.___|