```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

<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__)

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
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
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

```