I am posting this because I think there may be some interest in  
seeing a deterministic solution to the quiz problem. This time I  
include grid.rb because it's a little different from the version  
given in the quiz description. My change reorders the @pts array. I  
wanted an ordering that was easier for me to visualize. Actually,  
this solution would work with the original grid.rb, but some of the  
method names (bottm, right_side, left_side, top) in path.rb would be  
rendered misleading.

<code>
#! /usr/bin/env ruby -w
#  d_tsp.rb
#  DTSP -- Deterministic solution to Traveling Salesman Problem
#
#  Created by Morton Goldberg on September 23, 2007.

ROOT_DIR = File.dirname(__FILE__)
$LOAD_PATH << File.join(ROOT_DIR, "lib")

require "grid"
require "path"

DEFAULT_N = 5
grid_n = ARGV.shift.to_i
grid_n = DEFAULT_N if grid_n < 2
grid = Grid.new(grid_n)
puts "#{grid_n} x #{grid_n} grid"
puts Path.new(grid)
</code>

<code>
#  lib/path.rb
#  DTSP -- Deterministic solution to Traveling Salesman Problem
#
#  Created by Morton Goldberg on September 23, 2007
#
# Minimal path traversing a grid of points starting from and  
returning to
# the origin.

require "enumerator"

class Path
    attr_reader :pts, :grid
    def initialize(grid)
       @grid = grid
       @order = grid.n**2
       @pts = []
       bottom
       right_side
       top
       left_side
    end
    def length
       len = 0.0
       @pts.each_cons(2) { |p1, p2| len += dist(p1, p2) }
       len
    end
    def inspect
       "#<#{self.class} #{grid.n} points -- length=#{length}, " \
       "pts=#{@pts.inspect}>"
    end
    def to_s
       iter = @pts.enum_for(:each_slice, 5)
       "length: %.2f excess: %.2f\%\n" % [length, excess] +
       iter.collect do |row|
          row.collect { |pt| pt.inspect }.join('  ')
       end.join("\n")
    end
private
    def bottom
       @pts.concat(grid.pts.first(grid.n))
    end
    def right_side
       1.step(grid.n - 3, 2) { |i| right_u_turn(i) }
    end
    def right_u_turn(i)
       k = 1 + i * grid.n
       @pts.concat(grid.pts[k, grid.n - 1].reverse)
       k += grid.n
       @pts.concat(grid.pts[k, grid.n - 1])
    end
    def top
       if grid.n & 1 == 0
          # For even n, the top is just a run back to the left side.
          @pts.concat(grid.pts.last(grid.n).reverse)
       else
          # For odd n, the run from the right side back to the left side
          # must be corrugated.
          top_2 = grid.pts.last(2 * grid.n - 1)
          upr_top = top_2.last(grid.n).reverse
          low_top = top_2.first(grid.n - 1).reverse
          @pts << low_top.shift << upr_top.shift << low_top.shift
          @pts << upr_top.shift << upr_top.shift
          ((grid.n - 3) / 2).times do
             @pts << low_top.shift << low_top.shift
             @pts << upr_top.shift << upr_top.shift
          end
       end
    end
    def left_side
       (grid.n - 2).downto(1) { |i| @pts << grid.pts[i * grid.n] }
       @pts << grid.pts.first
    end
    # Relative difference between length and minimum length expressed as
    # percentage.
    def excess
       100.0 * (length / grid.min - 1.0)
    end
    # Square of the distance between points p1 and p2.
    def dist_sq(p1, p2)
       x1, y1 = p1
       x2, y2 = p2
       dx, dy = x2 - x1, y2 - y1
       dx * dx + dy * dy
    end
    # Distance between points p1 and p2.
    def dist(p1, p2)
       Math.sqrt(dist_sq(p1, p2))
    end
end
</code>

<code>
#  lib/grid.rb
#  DTSP -- Deterministic solution to Traveling Salesman Problem
#
#  Created by Morton Goldberg on September 23, 2007

# Square grid (order n**2, where n is an integer > 1). Grid points are
# spaced on the unit lattice with (0, 0) at the lower left corner and
# (n-1, n-1) at the upper right.

class Grid
    attr_reader :n, :pts, :min
    def initialize(n)
       raise ArgumentError unless Integer === n && n > 1
       @n = n
       @pts = []
       n.times do |i|
          y = i.to_f
          n.times { |j| @pts << [j.to_f, y] }
       end
       # @min is length of shortest tour traversing the grid.
       @min = n * n
       @min += Math::sqrt(2.0) - 1 if @n & 1 == 1
    end
end
</code>

Regards, Morton