--- In fc-solve-discuss_at_yahoogroups.com, "Gary Campbell" <gary_at_...>
wrote:
>
> I’m simply hitting “reply†on my email program.
> I’ve set it to respond in the the text type of the
> original email.
>
> If you can stand another post from me on this
> subject, both of the following are examples of
> pruning (and sorting) that are incorporated into
> my solver.
>
> The first example describes what I call an a->b->c type move. This
large class of moves can be pruned by recognizing that a card has been
moved twice and could have earlier been moved directly to its target,
therefore the 2nd move can be pruned and if this forces backup to the
original alternative move, the extra move is avoided (however, I must
note that if the a->c move is necessary to a solution, this pruning
method does force a backup). I long ago decided that a->b->c pruning is
well worth implementing.
>
Although I presented both scenarios as examples of pruning, my solver
simply blocks the b->c move and forces itself to find an alternative
move. If a->c is necessary to finding a solution, then it'll eventually
backup and choose that move when it originally chose the a->b move. I
believe this is a recap of your comment.
> The 2nd example, I believe, is also a very good example of sorting.
Here, the original move targeting the QH might have been correct. If
so, the later move targeting the QD would not have been necessary. In
any case, a->b->c pruning would have forced the original move via
backup. But, there is something else important going on here: When
moving several cards into a sequence, always sort the moves so that
those with the highest ranking head cards are done first. Sometimes
this enables a sequence that would not be possible unless you did it
this way, and it generally gets you the shortest result. A solver more
sophisticated than mine might try to actually prune all but one of the
ways that a sequence of cards could be formed from cards immediately
available. This would greatly reduce the redundant alternatives at each
step, permitting backup and retry to search through fewer possibilities.
>
My solver doesn't check for redundancy when a multi-card move is
involved. So, it'd allow the redundant move sequence. I know an easy way
to implement the blocked move, but I'm not sure that I want to add the
52 bytes to every layout generated.
My solvers use checksums to track every layout generated. If a sequence
of moves results in a layout that was previously generated, then my
general solver assumes that it arrived at a permutation of the earlier
moves, and it discards the current layout. My iterative solver doesn't
make this assumption. It maintains and checks to see if the number of
moves linked to the first checksum is greater-than the number of moves
linked to the current checksum. If so, then it updates the move count
for this checksum and continue with the current layout. This way, a
shorter solution might be found using the current layout.
Regards, Danny
Received on Sat Dec 01 2012 - 10:12:29 IST