Newsgroups: rec.puzzles
From: haoyuep@aol.com (Dan Hoey)
Date: 2000/07/10
Subject: Re: Mikero's brainwrenching grid puzzle #4 (June 29, 2000)

dan...@benzedrine.cx (Daniel Hartmeier) wrote:
> >  Score : 157
[...]

> As I already know, my program won't find solutions with loops.
> But it finds other solutions pretty fast, which means you might
> use it to find local optima to use as pruning limits, etc.

My program is guaranteed to find all solutions, and confirms that the
score of 157 is optimal.  This is achieved by three variants of Daniel
Hartmeier's solution,

jqrklmtsuvwponghaZY{XQR,RQX,RXQ}fedcWVOHA
  BIPJCKDEFMLSTUbiNG

and two variants of another solution

jqrklmtsuvwpongZahibUNGTSLMFEDKJCQXYRfedc
  WVO{PIBAH,HABIP}

(and their reverses, of course).  I list only the first visit to each
vertex.

My program starts at each vertex in turn and does a depth-first search
for a minimum-cost path.  It prunes the search by using the minimum
spanning tree cost of the unvisited nodes as a lower bound for
completing the path.  The procedure of adding a new vertex and
recomputing the spanning tree was performed about 109,000,000 times.

Mikero mentoned that he designed the puzzle to be difficult for
a program to solve.  But what made my approach feasible is the
closeness of the minimum path cost to the minimum spanning tree
cost (157 and 129, respectively).  The gap could be made much
larger--nearly a 3:2 ratio, if I recall correctly--and would make
it much harder to solve.

Dan Hoey       haoyuep@aol.com        Posted and e-mailed