```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
_________   ________________________________________________________________________________________________________________________________________
|   |       |       |       |                                           |   |           |           |   |       |       |           |               |
|   |   .___|   .___|___.   |___.___.   .___.___.   .___.___.   .   .___|   |   .___.   |___.   .___|   |   .   |   .   |   .   .___|   .___.___.   |
|   |       |           |           |           |           |   |           |       |       |               |   |   |   |   |       |           |   |
|   |   .   |   .   .___|   .   .___|   .   .   |___.   .   |___|___.___.   |   .   |   .___|___.   .___.___|___|   |   |   |___.___|   .___.___|___|
|       |   |   |       |   |       |   |   |       |   |               |   |   |   |           |               |   |                               |
|   .   |   |___|   .   |   |___.___|   |   |   .   |   |___.___.___.___|   |   |   |   .___.___|___.___.___.   |___|   .___.   .___.   .   .   .___|
|   |   |       |   |   |           |   |   |   |   |                   |   |   |   |                       |       |       |       |   |   |       |
|___|___|   .   |   |   |___.   .   |   |___|___|___|   .___.   .___.___|___|   |   |___.___.   .   .   .   |   .   |___.   |___.   |___|___|___.___|
|       |   |       |       |   |   |               |       |               |   |           |   |   |   |   |   |       |       |                   |
|___.   |   |   .   |   .___|   |   |___.___.___.   |___.___|___.___.___.   |   |___.___.   |___|   |   |___|___|___.   |   .   |___.___.   .___.   |
|   |       |   |   |       |   |               |                       |   |           |       |   |               |   |   |           |       |   |
|   |___.___|___|___|   .   |___|   .___.___.___|   .___.___.___.   .   |   |   .   .___|___.___|   |   .   .___.___|   |___|   .___.___|   .   |   |
|                   |   |       |                               |   |   |   |   |               |   |   |           |       |           |   |   |   |
|   .   .___.___.___|   |   .___|___.___.   .   .   .___.___.   |___|___|___|___|___.   .___.   |   |   |___.   .   |___.   |   .___.   |   |___|   |
|   |               |   |               |   |   |           |                       |       |   |   |       |   |       |   |       |   |       |   |
|___|   .   .   .   |   |___.___.___.   |___|___|___.___.   |   .___.   .___.___.___|   .___|   |   |   .   |   |___.   |   |___.___|   |___.   |   |
|   |   |   |   |   |               |                   |   |       |               |       |   |   |   |   |       |   |           |       |   |   |
|   |   |___|___|___|   .   .___.   |___.   .   .___.   |___|   .___|___.   .   .___|   .   |___|   |   |___|___.   |   |   .   .   |   .   |___|___|
|                   |   |       |       |   |       |       |           |   |       |   |       |   |           |   |   |   |   |   |   |           |
|   .   .___.   .   |___|   .___|   .   |   |   .   |___.   |___.___.   |___|___.   |___|___.   |___|   .___.___|___|___|___|   |   |   |   .   .   |
|   |       |   |       |       |   |   |   |   |       |           |           |           |       |                       |   |       |   |   |   |
|___|   .___|___|   .___|___.   |___|___|   |   |   .___|___.   .   |   .___.___|___.___.   |___.___|___.___.   .___.   .___|___|___.___|___|   |   |
|   |           |           |           |   |   |           |   |   |                   |                           |                           |   |
|   |___.   .   |___.   .   |   .___.   |___|   |   .___.___|___|   |___.___.   .___.___|___.___.   .   .___.   .   |   .___.   .   .___.___.   |___|
|       |   |       |   |   |       |       |   |               |           |                   |   |       |   |   |       |   |           |       |
|___.   |   |   .   |   |   |   .___|___.___|   |   .___.   .   |___.___.   |   .___.___.___.   |   |___.   |___|   |   .___|___|___.___.___|   .___|
|       |   |   |   |   |   |               |   |       |   |           |   |               |   |       |       |   |                       |       |
|___.   |___|___|___|   |___|___.   .___.   |___|___.___|___|   .___.___|___|___.   .___.___|___|___.   |   .___|___|___.   .   .   .   .___|   .   |
|                   |           |       |                   |                   |                   |   |               |   |   |   |       |   |   |
|   .   .___.___.___|___.   .___|   .___|___.   .   .   .___|   .   .   .   .___|   .___.___.   .   |___|   .   .   .   |___|___|___|   .___|   |___|
|   |                   |       |           |   |   |       |   |   |   |       |           |   |       |   |   |   |               |       |       |
|___|___.   .   .___.   |   .   |   .___.   |   |   |___.   |___|___|___|   .___|___.___.___|___|___.   |   |   |   |___.   .   .___|___.   |___.   |
|       |   |       |   |   |   |       |   |   |       |               |                           |   |   |   |       |   |           |       |   |
|___.   |   |   .___|___|   |___|___.   |   |___|___.___|___.___.___.   |___.___.   .___.___.   .___|   |___|___|   .   |___|___.___.   |___.___|   |
|   |       |           |               |                           |           |           |       |           |   |               |           |   |
|   |___.___|   .___.___|   .___.___.   |   .   .___.   .___.___.   |   .   .___|___.___.   |   .   |___.___.   |___|___.   .___.___|   .   .   |___|
|           |           |           |   |   |       |           |   |   |               |   |   |           |           |           |   |   |       |
|___.___.   |___.   .___|___.   .   |___|   |   .   |   .   .___|   |___|___.___.   .___|   |___|   .   .___|___.___.   |   .___.___|___|___|___.   |
|       |       |           |   |       |   |   |   |   |       |               |       |       |   |               |   |                       |   |
|___.   |   .   |___.___.   |___|   .   |___|___|   |   |   .   |___.___.   .___|___.   |   .   |___|   .   .   .   |___|___.   .   .   .___.   |___|
|   |       |           |       |   |           |   |   |   |           |           |   |   |       |   |   |   |           |   |   |       |       |
|   |___.___|   .___.   |___.   |___|___.___.   |   |   |___|___.___.___|   .___.   |   |   |   .   |   |   |   |   .   .___|   |   |   .   |   .___|
|           |       |                           |   |                   |       |   |   |   |   |   |   |   |   |   |       |   |   |   |   |       |
|   .   .___|   .___|   .___.___.   .___.___.   |___|___.___.___.___.___|   .   |   |___|   |   |___|___|   |___|___|   .   |   |___|   |___|   .___|
|   |       |       |           |           |                           |   |   |       |   |           |           |   |   |       |       |       |
|___|___.   |   .   |___.   .___|   .___.   |___.___.   .___.   .___.___|   |   |___.___|   |   .___.___|___.___.___|___|   |   .___|___.   |   .   |
|               |       |       |       |           |       |           |   |           |   |                           |   |           |   |   |   |
|___.___.___.___|___.   |   .___|   .   |___.___.___|___.___|   .___.___|   |   .___.___|___|   .___.   .___.   .   .   |   |___.   .   |   |___|___|
|                   |   |       |   |                       |           |   |               |       |       |   |   |   |       |   |   |           |
|___.___.___.   .   |   |   .___|   |   .___.   .___.___.   |   .   .   |   |___.   .   .   |   .___|   .   |___|___|   |___.___|   |___|___.___.___|
|               |   |   |       |   |       |           |   |   |   |   |       |   |   |   |       |   |           |           |                   |
|___.   .___.   |___|   |   .   |___|   .___|___.___.___|   |   |___|___|   .___|___|___|___|   .___|   |___.   .___|   .___.   |___.___.___.   .   |
|           |           |   |       |                   |   |           |                   |       |       |       |       |                   |   |
|___.___.___|   .   .   |   |___.   |   .   .___.   .___|___|   .   .___|   .___.___.   .___|   .___|___.   |   .   |___.   |___.___.___.___.___|___|
|               |   |   |       |   |   |       |           |   |       |           |       |           |   |   |       |                           |
|___.___.___.___|___|___|___.___|___|___|___.___|___.___.___|___|___.___|___.___.___|___.___|___.___.   |___|___|___.___|___.___.___.___.___.___.___|

```