This is my submission for Ruby Quiz #90.

My solution's best feature is that it's based on a simple search  
algorithm and that's also its worst feature. The randomized depth- 
first search I use is easy to understand, was easy to code, and  
required almost no debugging. But it has O(e**n) worst-case behavior.  
Which means it works well enough for small n, but it quickly becomes  
intolerable as n grows. When does it begin to suck? Depends on how  
patient you are. I ran out of patience at n = 7.

The search is programmed to terminate as soon as it finds one, cyclic  
solution. Of course, from any cyclic solution, you can generate n**2  
- 1 additional cyclic solutions by applying the included Grid#shift  
method for n = 1 to 35.

My solution's second best feature is that it's short. Even with a  
fair amount of commenting, it comes in at less than 200 lines.

Here are some results from running it with n =  5 and n = 6.

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
------------------------
|   1  16  19   2  15  |
|  11  22   5  12  21  |
|  18   8  25  17   7  |
|   4  13  20   3  14  |
|  10  23   6   9  24  |
------------------------
real    0m0.095s
user    0m0.053s
sys     0m0.014s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
------------------------
|   1  21   6   9  20  |
|  14  11   3  17  12  |
|   5   8  25  22   7  |
|   2  18  13  10  19  |
|  15  23   4  16  24  |
------------------------
real    0m0.048s
user    0m0.017s
sys     0m0.011s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
------------------------
|   1  13  21  18  12  |
|   6  16  24   9   4  |
|  22  19   2  14  20  |
|  25  10   5  17  11  |
|   7  15  23   8   3  |
------------------------
real    0m0.166s
user    0m0.108s
sys     0m0.014s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------
|   1  15  22  36   5  23  |
|  26   9  19  25  10  18  |
|  21  29   6  16  30  35  |
|   2  14  11  33   4  24  |
|  27   8  20  28   7  17  |
|  12  32   3  13  31  34  |
----------------------------
real    0m3.004s
user    0m2.827s
sys     0m0.034s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------
|   1   8  31  36   7  30  |
|  27  13  16  24  12  17  |
|  20  35   2   9  32   3  |
|  15  23  28  14   6  29  |
|  26  10  19  25  11  18  |
|  21  34   5  22  33   4  |
----------------------------
real    1m18.337s
user    1m12.836s
sys     0m0.567s

~/Projects/Ruby/Ruby Quiz mg: time ./quiz_90.rb
----------------------------
|   1  15  29  36  16  28  |
|   9   6  18  26   7  19  |
|  22  33  11  14  30  35  |
|   2  25   8   5  17  27  |
|  10  13  21  34  12  20  |
|  23  32   3  24  31   4  |
----------------------------
real    0m1.126s
user    0m1.027s
sys     0m0.021s

Notice the wide variation in run times. You have to be lucky to get a  
really short run. This suggests some interesting statistical questions:

1. What is the distribution of run times as a function of n?

2. What is the mean number of backtracking events over all the  
possible searches as a function of n?

3. What is the probability that a search proceeds to a solution with  
at most k backtracks as a function of n?

I don't know the answer to any of these questions, but I would like to.

<code>
#! /usr/bin/ruby -w
# Author: Morton Goldberg
#
# Date: August 15, 2006
#
# Ruby Quiz #90 -- Pen and Paper Game

# A grid is a matrix of cells.
class Grid

    def initialize(dims)
       @rows, @cols = dims
       @size = @rows * @cols
       @grid = Array.new(@rows) {|i| Array.new(@cols) {|j| Cell.new 
(i, j)}}
    end

    # Return a deep copy.
    def copy
       result = Grid.new(dimensions)
       result.grid.each_with_index do |row, i|
          row.each_with_index {|cell, j| cell.val = self[i, j].val}
       end
       result
    end

    # Shifts the values of the cells in the grid by <offset> under the
    # constraint that values are folded into the range 1..@size.
    def shift!(offset)
       @grid.each do |row|
          row.each do |cell|
             val = (cell.val + offset) % @size
             cell.val = (val == 0 ? @size : val)
          end
       end
       self
    end

    # Return the dimensions of the grid.
    def dimensions
       [@rows, @cols]
    end

    # Return the cell at positon [row, col].
    # Call as <grid-name>[row, col]
    def [](*args)
       row, col = args
       @grid[row][col]
    end

    # Assigns a cell to the positon [row, col].
    # Call as <grid-name>[row, col] = cell
    def []=(*args)
       row, col, cell = args
       @grid[row][col] = cell
    end

    # Format the grid as a bordered table.
    def to_s
       rule = '-' * (4 * @cols + 4) + "\n"
       grid_str = ""
       @grid.each do |row|
          grid_str << row.inject("|  ") do |row_str, cell|
             row_str << ("%2d  " % cell.val)
          end
          grid_str << "|\n"
       end
       "" << rule << grid_str << rule
    end

    attr_reader :rows, :cols, :size, :grid

end

# A path is an array of cells, where no two cells occupy the same  
location
# in some grid. A complete path fills the grid.
class Path < Array

    # Make a deep copy of a path.
    def copy
       result = Path.new
       each {|cell| result << cell.dup}
       result
    end

   # Sequentially number the cells in the path.
    def number!
       each_with_index {|cell, i| cell.val = i + 1}
       self
    end

    # Report whether or not a path is cyclic.
    def cyclic?
       p0, p1 = self[0], self[-1]
       delta = [(p1.row - p0.row).abs, (p1.col - p0.col).abs]
       delta == [3, 0] || delta == [0, 3] || delta == [2, 2]
    end

    # Make a grid from a path.
    # Warning: if the path isn't complete, the resulting grid wont't
    # represent a solution.
    def to_grid(size)
       result = Grid.new([size, size])
       each {|cell| result[cell.row, cell.col] = cell}
       result
    end

end

# A cell is a simple object that knows its value and its position in
# a grid. It also encodes the game's movement rule.
class Cell

    def initialize(row, col, val=0)
       @row, @col = row, col
       @val = val
    end

    # Return a list of targets -- an array containing all the cells  
in the
    # grid reachable from this cell in one step.
    def targets(grid)
       size = grid.rows
       result = []
       result << grid[@row, @col - 3] if @col - 3 >= 0    # north
       result << grid[@row + 2, @col - 2] \
          if @row + 2 < size && @col - 2 >= 0             # northeast
       result << grid[@row + 3, @col] if @row + 3 < size  # east
       result << grid[@row + 2, @col + 2] \
          if @row + 2 < size && @col + 2 < size           # southeast
       result << grid[@row, @col + 3] if @col + 3 < size  # south
       result << grid[@row - 2, @col + 2] \
          if @row - 2 >= 0 && @col + 2 < size             # southwest
       result << grid[@row - 3, @col] if @row - 3 >= 0    # west
       result << grid[@row - 2, @col - 2] \
          if @row - 2 >= 0 && @col - 2 >= 0               # northwest
       result
    end

    attr_accessor :row, :col, :val

end

# A solver uses a depth-first search to find one solution for a  
square grid # of a given size.
class Solver

    def initialize(size)
       @size = size
       @solution = nil
       @test_grid = Grid.new([@size, @size])
       cell = @test_grid[0, 0]
       targets = cell.targets(@test_grid)
       goals = targets.dup
       @backtrack_chain = [[Path.new << cell, targets, goals]]
    end

    # Return a new link for the backtrack chain if it can be extended;
    # otherwise, return nil.
    def next_link
       path, targets, goals = @backtrack_chain.last
       return nil if targets.empty? || goals.empty?
       # Here is where the randomization takes place.
       cell = targets[rand(targets.size)]
       next_path = path.dup << cell
       # Restricts target list to accessible cells not already on the  
path.
       next_targets = cell.targets(@test_grid) - path
       next_goals = goals.dup
       next_goals.delete(cell) if goals.include?(cell)
       # Make sure cell won't be picked again if backtrack occurs.
       targets.delete(cell)
       [next_path, next_targets, next_goals]
    end

    # The algorithm is a randomized depth-first search.
    def solve
       final_size = @size * @size
       loop do
          link = next_link
          if link then
             @backtrack_chain.push(link)
          else
             @solution = @backtrack_chain.pop.first
             break if @solution.size == final_size
             if @backtrack_chain.empty? then
                raise(RuntimeError, "No solution for #@size x #@size  
grid")
             end
          end
       end
       @solution.number!
    end

    attr_reader :solution

end

SIZE = 5
solver = Solver.new(SIZE)
puts solver.solve.to_grid(SIZE)
</code>

Regards, Morton