First, before I get to my main solution, I would like to show that, as Mort=
on pointed out, yes, it is very possible to have a quick, exact solution. H=
ere's one that does so for N >=3D 3 (N=3D2 and N=3D1 nevertheless draw corr=
ectly; a call to uniq would make them work).=0A=0Arequire 'RMagick'=0Arequi=
re 'enumerator'=0A=0A<definitions of Grid and draw_itin removed - see main =
solution below>=0A=0An =3D ARGV[0].to_i=0A=0Aitin =3D ([0]*n).zip((0...n).t=
o_a)=0A=0A1.step(n-3, 2) do |x|=0A  itin +=3D ([x]*(n-1)).zip((1...n).to_a.=
reverse)=0A  itin +=3D ([x+1]*(n-1)).zip((1...n).to_a)=0Aend=0A=0Aif n%2=3D=
=3D0=0A  itin +=3D ([n-1]*(n-1)).zip((0...n).to_a.reverse)=0Aelse=0A  (n-1)=
..step(2, -2) do |y|=0A    itin +=3D [[n-2,y],[n-1,y],[n-1,y-1],[n-2,y-1]]=
=0A  end=0Aend=0A=0Aitin +=3D (0...n).to_a.reverse.zip([0]*n)=0A=0A$grid =
=3D Grid.new(n) #Because draw_itin asks for it=0Adraw_itin(itin, "#{n}x#{n}=
tour2.jpg")=0A=0A=0AHowever, not being one to run from a fun problem, my ma=
in solution does implement a genetic algorithm. While I did use the reverse=
_segment and adjacent_segment_swap recombinators described in the quiz, I a=
lso used a good variety of other asexual (i.e.: one parent) and sexual (i.e=
..: two parents) recombinators.=0A=0AUnfortunately, and as might be expected=
, my solution has a wide variety in speed. I've seen the time to evolve a 6=
x6 tour range from under 500 generations to tens of thousands of generation=
s. At first I wondered whether the two sexual recombinators and element_swa=
p were reducing variability too much, but commenting them out of the RECOMB=
INATORS array didn't seem to help;=0A=0AAnyway, here's the code:=0A=0Arequi=
re 'enumerator'=0Arequire 'RMagick'=0A=0ADESIRED_FITNESS =3D 1.05=0AGENERAT=
ION_SIZE =3D 30=0A=0A=0A# Square grid (order n**2, where n is an integer > =
1). Grid points are=0A# spaced on the unit lattice with (0, 0) at the lower=
 left corner and=0A# (n-1, n-1) at the upper right.=0A=0Aclass Grid=0A  att=
r_reader :n, :pts, :min=0A  def initialize(n)=0A    raise ArgumentError unl=
ess Integer =3D=3D=3D n && n > 1=0A    @n =3D n=0A    @pts =3D []=0A    n.t=
imes do |i|=0A      x =3D i.to_f=0A      n.times { |j| @pts << [x, j.to_f] =
}=0A    end=0A    # @min is length of any shortest tour traversing the grid=
..=0A    @min =3D n * n=0A    @min +=3D Math::sqrt(2.0) - 1 if @n & 1 =3D=3D=
 1=0A  end=0Aend=0A=0Aclass Array=0A  def conses(size)=0A    conses =3D []=
=0A    each_cons(size) do |cns|=0A      conses << cns=0A    end=0A    conse=
s=0A  end=0Aend=0A=0Adef rand_sorted_nums(n, max)=0A  ([nil]*n).map{rand(ma=
x)}.sort=0Aend=0A=0A###Asexual recombinators=0A=0A##The 'exchange' recombin=
ator mentioned in the quiz description.=0A##Splits itinerary into four segm=
ents based on three points and swaps the middles=0Adef adjacent_segment_swa=
p(itin)=0A  i1,i2,i3 =3D rand_sorted_nums(3, itin.length)=0A  itin[0...i1] =
+ itin[i2..i3] + itin[i1...i2] + itin[(i3+1)..-1]=0Aend=0A=0A##Like adjacen=
t_segment_swap, but splits into 5 segments and swaps 2 and 4=0Adef nonadjac=
ent_segment_swap(itin)=0A  i1,i2,i3,i4 =3D rand_sorted_nums(4, itin.length)=
=0A  i1,i2,i3,i4 =3D rand_sorted_nums(4, itin.length) until i2 !=3D i3=0A  =
itin[0...i1] + itin[i3..i4] + itin[(i2+1)...i3] + itin[i1..i2] +=0A      it=
in[(i4+1)..-1]=0Aend=0A=0A##The reverse recombinator mentioned in the quiz =
description=0A##Splits itinerary into three segments based on two points;=
=0A##reverses the nodes in the middle=0Adef reverse_segment(itin)=0A  i1,i2=
 =3D rand_sorted_nums(2, itin.length)=0A  itin[0...i1] + itin[i1..i2].rever=
se + itin[(i2+1)..-1]=0Aend=0A=0A##Simply swaps a random two nodes=0Adef el=
ement_swap(itin)=0A  i1, i2 =3D rand_sorted_nums(2, itin.length)=0A  itin_c=
hld =3D itin.dup=0A  itin_chld[i1], itin_chld[i2] =3D itin_chld[i2], itin_c=
hld[i1]=0A  itin_chld=0Aend=0A=0A##Splits into three segments based on two =
points.=0A##Every adjacent pair in the middle segment is swapped. E.g.: [a,=
b,c,d,e] -> [b,a,d,c,e]=0Adef adjacent_el_swap(itin)=0A  i1,i2 =3D rand_sor=
ted_nums(2, itin.length)=0A  itin_chld =3D itin[0...i1]=0A  itin[i1..i2].ea=
ch_slice(2) do |a,b|=0A    itin_chld +=3D [b,a].compact=0A  end=0A  itin_ch=
ld + itin[(i2+1)..-1]=0Aend=0A=0A###Sexual recombinators=0A=0A##Described i=
n Wikipedia's article on crossovers in genetic algorithms=0A##Splits female=
 into three segments based on two points. Reorders middle according=0A##to =
the order of the nodes in the male=0Adef partner_guided_reorder(itinf, itin=
m)=0A  i1,i2 =3D rand_sorted_nums(2, itinf.length)=0A  itinf[0...i1] +=0A  =
  itinf[i1..i2].sort_by{|el| itinm.index(el)} +=0A      itinf[(i2+1)..-1]=
=0Aend=0A=0A##Identifies segments of the male itinerary (genes) that are ma=
ximally fit.=0A##Reorders the corresponding nodes in the female to match=0A=
def fit_gene_exchange(itinf, itinm)=0A  gene_length =3D rand(Math.sqrt($gri=
d.n).floor) + 1=0A  return itinf if 2..($grid.pts.length) =3D=3D=3D gene_le=
ngth=0A  genes =3D []=0A  itinm.each_cons(gene_length) do |cns|=0A    genes=
 << cns=0A  end=0A  genes.map! {|gene| [total_driving_distance(gene), gene]=
}=0A  genes.sort!=0A  =0A  itin_chld =3D itinf.dup=0A  genes.each do |(dist=
, gene)|=0A    break if dist > gene_length=0A    break if rand(10) =3D=3D 0=
=0A    =0A    gene[1..-1].each do |node|=0A      itin_chld.slice!(itin_chld=
..index(node))=0A    end=0A    p [gene_length, gene]=0A    itin_chld[itin_ch=
ld.index(gene.first)] =3D gene=0A  end=0A  itin_chld=0Aend=0A=0ARECOMBINATO=
RS =3D [:adjacent_segment_swap,=0A                            :nonadjacent_=
segment_swap,=0A                            :reverse_segment,=0A           =
                 :element_swap,=0A                            :adjacent_el_=
swap,=0A                            :partner_guided_reorder,=0A            =
                :fit_gene_exchange,=0A            ].map{|sym| method(sym)}=
=0A=0A###End of genetic recombinators=0A=0Adef total_driving_distance(itin)=
=0A  itin.conses(2).inject(0) {|dist, ((x1,y1),(x2,y2))|=0A    dist+Math.sq=
rt(((y2-y1)**2)+((x2-x1)**2))}=0Aend=0A  =0Adef fitness(itin)=0A  total_dri=
ving_distance(itin + [itin.first]) #Must return to starting point=0Aend=0A=
=0Adef next_generation(parents, target_size)=0A  (parents * (target_size / =
parents.length + 1))[0..target_size].map do |par|=0A    recom =3D RECOMBINA=
TORS[rand(RECOMBINATORS.size)]=0A    if recom.arity =3D=3D 1=0A      recom.=
call(par)=0A    else=0A      recom.call(par,parents[rand(parents.size)])=0A=
    end=0A  end=0Aend=0A=0Adef  genetic_search(initial_population)=0A  pop =
=3D initial_population=0A  until fitness(pop.first) <=3D $grid.min * DESIRE=
D_FITNESS=0A    pop =3D next_generation(pop, GENERATION_SIZE * 3).=0A      =
sort_by{|itin| fitness(itin)}[0...GENERATION_SIZE]=0A  end=0A  pop.first=0A=
end=0A=0A=0ASPACING =3D 50=0ABORDER =3D 20=0Adef draw_itin(itin, filename)=
=0A  dim =3D ($grid.n-1)*SPACING + BORDER * 2=0A  canvas =3D Magick::Image.=
new(dim, dim)=0A  gc =3D Magick::Draw.new=0A  gc.stroke('black')=0A  gc.str=
oke_width(1)=0A  =0A  $grid.pts.each do |(x,y)|=0A    gc.circle(*[x,y,x+3.0=
/SPACING, y].map{|c|c*SPACING+BORDER})=0A  end=0A  (itin+[itin.first]).each=
_cons(2) do |((x1,y1),(x2,y2))|=0A    gc.line(*[x1,y1,x2,y2].map{|c|c*SPACI=
NG+BORDER})=0A  end=0A  gc.draw(canvas)=0A  canvas.write(filename)=0Aend=0A=
=0An =3D ARGV[0].to_i=0A$grid =3D Grid.new(n)=0Ainit_pop =3D next_generatio=
n([$grid.pts] * GENERATION_SIZE,=0A    GENERATION_SIZE)=0Adraw_itin(genetic=
_search(init_pop), "#{n}x#{n}tour.jpg")=0A=0A=0A=0A       =0A______________=
______________________________________________________________________=0ALo=
oking for a deal? Find great prices on flights and hotels with Yahoo! FareC=
hase.=0Ahttp://farechase.yahoo.com/