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