On Wed, 26 Jun 2002, Adrian Ettlinger wrote:
> Hi Shlomi and Bill R.
>
> Sorry, I just don't go along with you guys at all. Each position,
> whether intermediate or not, is an entity unto itself, and is either
> solvable or unsolvable. If a solver algorithm cares how the position was
> arrived at, then it isn't properly designed.
>
I can assure you my solving algorithm is very well designed, and yet it
may proclaim a derived position as non-solvable.
Here is a short explanation:
Let's suppose the initial position is A and there's an intermediate
position B. Now, let's suppose that the only way to solve B is through C.
However, C is found in the path to B and was already visited and marked as
such. Now, if the solver recurses into C, he will go around in circles:
A -> C -> B -> C -> B -> C -> B ...
That's a very Bad Thing<tm>. That's why it would eventually recurse out of
B.
Regards,
Shlomi Fish
> Let me state it in a nontechnical, logical way:
>
> For any original position, there is a tree of all possible moves. The
> interstices of this tree each represent a position. What any solver does is
> to pare down the full gross tree into its essentials. One essential task of
> any practical solver is to eliminate all the branches of the tree which
> repeat a position that has occurred somewhere on the path back to the
> original position. So that the pared tree will contain each possible
> position only once. Some paths lead to a solution, some paths lead to an
> impossible position. The impossible positions are recognized only when all
> possible paths further along have not led to a solution. Whether the scan
> is depth-first or breadth-first, or whatever, the solver follows a process
> where it works its way through the tree, and when any path leads to a blind
> alley, it returns to a position for which it has not yet fully developed the
> tree, and departs from there with a previous untried move.
>
> Best regards, ----------------Adrian
>
>
>
>
> To unsubscribe from this group, send an email to:
> fc-solve-discuss-unsubscribe_at_yahoogroups.com
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_iglu.org.il
He who re-invents the wheel, understands much better how a wheel works.
Received on Wed Jun 26 2002 - 19:27:15 IDT