The answer, Taren, is "all of the above". I will make some comments,
and you should know who they're coming from. I put in a lot of time in
development of the basic solver for FcPro, but I didn't write the original
one, which was by Don Woods, and all my work was building on and modifying
his. I'm not a professional programmer, and when I started I was ignorant
of most of the terminology which is second nature to guys like Shlomi and
Bill Raymond. So I'll ask the pros here. Are Taren's two methods what you
guys would call "depth-first search" vs. "breadth-first search"?
"All of the above" is not meant tongue-in-cheek. Which of any methods
along many different axes will work fastest depends, often very sharply, on
the deal. If you want your solver to be able to handle any deal in a
reasonably fast time, you have to design it so it will cycle through
different methods searching for a fast one. What I did with the Don Woods
solver involved a number of types of variations, but was crude compared to
what Shlomi does in his, or what Tom Holroyd does in Patsolve. To give you
an idea, the basic FcPro solver tries variations in (1) Permutations in
column order (2) Sequence in which various types of moves are tried, and (3)
Method of hash tables employed. There are also variations in the sequence
with which it tries different variations, and the time it spends on each in
the cycle. Despite all these variations, the most sophisticated solver yet
designed, when tested over a range of a million or more deals, will be found
to bog down and give an "Intractable" result on a few. The basic FcPro
solver, BTW, uses only depth-first search. I did not have the ambition to
dig directly into the guts of the basic search
orithm. ----------------Adrian Ettlinger
Received on Mon Nov 24 2003 - 04:12:17 IST