Danny: I know we talked about recording layouts and preventing their recurrence (at a lower or higher step number) some years ago, but it’s worth being clear about exactly how the layout is recorded. If every aspect of the layout is recorded, longer search times occur, and equivalent layouts are considered different. Thus, it is worth ignoring certain differences in layouts. For example, I find that my solver runs almost twice as fast (but gets a very occasional false negative) if I simply record red vs. black in card sequences instead of all 4 suits. Another difference that doesn’t produce false negatives, if ignored, is the order of cards in free cells and the order of the columns. However, I do think that layouts have to be recorded to prevent search beyond a repeated position leading to vastly larger searches in many cases. -Gary
From: dannyjones183
Sent: Saturday, December 01, 2012 10:12 AM
To: fc-solve-discuss_at_yahoogroups.com
Subject: Re: Pruning Examples
--- 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 - 11:24:53 IST