```-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Suraj N. Kurapati wrote:
> Here is my solution, which uses recursion like the Civilization II
> map generation example in Chris Pine's "Learn to Program" book.
>
> With a stack limit of:
>
>   \$ ulimit -s
>   8192
>
> the maximum square size my solution can handle is 67x67. However, it
> can handle larger squares if you increase the stack size.

Well, I discovered that this solution doesn't always find the
correct answer, so I fixed it accordingly. Now I can see why Eric
DUMINIL said a *brute force* approach is too slow. :)

Thanks for the fun quiz.

#!/usr/bin/ruby -w
# @param  . width of square
# @param  . starting row
# @param  . starting column

class Square < Array
def initialize aWidth
super(aWidth) { Array.new aWidth }
@mark = 0
@size = aWidth ** 2
end

# Walks this square, from the given position,
# while marking unmarked (nil) cells.
def walk row, col
# skip invalid positions and marked cells
return false if
row < 0 or row >= length or
col < 0 or col >= length or
self[row][col]

# mark the current cell
self[row][col] = @mark += 1

if @mark >= @size or
walk(row + 3, col    ) or # east
walk(row + 2, col - 2) or # north east
walk(row,     col - 3) or # north
walk(row - 2, col - 2) or # north west
walk(row - 3, col    ) or # west
walk(row - 2, col + 2) or # south west
walk(row,     col + 3) or # south
walk(row + 2, col + 2)    # south east

true
else
# unmark the current cell
@mark -= 1
self[row][col] = nil

false
end
end

# Pretty-prints this square.
def to_s
# pretty-print each row
fmt = '|' << "%#{length.to_s.length * 2}d " * length << '|'

lines = inject([]) do |memo, row|
memo << fmt % row
end

# add a border to top & bottom
border = '-' * lines.first.length

lines.unshift border
lines << border

lines.join("\n")
end
end

if \$0 == __FILE__
# create a square with user's parameters
width = (ARGV.shift || 5).to_i
square = Square.new(width)

# walk the square from random position
origin = Array.new(2) { (ARGV.shift || rand(width)).to_i }
square.walk(*origin)

# pretty-print the walked square
puts square.to_s
end
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)

iD8DBQFE35TumV9O7RYnKMcRAkezAKCUQQS7HsRq+MkdRsi4xYWbjXIdnQCfS6no
2e9bpIoRRP1XuXgHe275Pso=
=miH9
-----END PGP SIGNATURE-----

```