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.
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.
-Gary Campbell
From: dannyjones183
Sent: Saturday, December 01, 2012 12:36 AM
To: fc-solve-discuss_at_yahoogroups.com
Subject: Pruning Examples
I'm posting this as an example of moves that should be pruned, but aren't always easy to locate. I'm using Shlomi Fish's latest solution, but I've only indirectly incorporated some of this pruning into my solver. It's on my "To Do List".
#00006240 Attempt: 1 NumFcs=4 (ShlomiFish) 56 moves
8a 8b 2h 8c 8d b3 63 1b 18 13
85 d5 6d 68 61 6h b1 5b 5h 8h
28 24 2h 54 5h 62 d2 85 36 3d
38 32 35 a5 35 57 53 42 4a 4b
45 1c 1h 1a 1h 5h 45 74 7h 85
68 6h a6 7a 7h 23
~~~~~
(a): move sequence number
(b): move in daj-extended standard notation
(c): highest-valued card being moved, a multi-card move has a (+)
(d): target card, ec = empty column, fc = freecell
(a) (b) (c) (d)
--- --- --- ---
============================== Depth 3
TD 4C 3C 3S *C 2D *S 3H freecells & foundation
8S QS 9C 9H TS TH KS **
8D 7H AS 2C 2S 3D 6S **
JH JC JS 9D AC 5H 4H **
6C 6D 8H 7S KC 5D 4S **
TC 6H 8C 5C 7D 9S QD **
4D QH KH 7C 5S ** ** **
** ** KD ** ** ** ** **
** ** QC ** ** ** ** **
** ** JD ** ** ** ** **
9 18. 4D ec
10 13. TC JD
11 85. 4D 5S
In this example, the following conditions exist:
*) the 5S is exposed at the beginning of move (9)
*) it is neither moved nor covered by another card before move (11)
This means that these moves could be pruned to:
9 15. 4D 5S
10 13. TC JD
Another example:
(a): move sequence number
(b): move in daj-extended standard notation
(c): highest-valued card being moved, a multi-card move has a (+)
(d): target card, ec = empty column, fc = freecell
(a) (b) (c) (d)
--- --- --- ---
============================== Depth 3
TD 3S 3C KH *C 7D *S 3H freecells & foundation
8S QS 9C 9H TS KD KS 8C
8D 7H AS 2C 2S QC 6S **
JH JC JS 9D AC JD 4H **
6C TH ** 7S KC TC 4S **
5H 9S ** 5C QH ** QD **
4C 8H ** 7C ** ** ** **
** ** ** 6H ** ** ** **
** ** ** 5S ** ** ** **
33 35. JS QH
___ 3h. AS *S Horne automove
34 a5. TD JS
35 35. 9C TD
36 57_ JS+ QD
In this example, the following conditions exist:
*) the QD is exposed at the beginning of move (33)
*) it is neither moved nor covered by another card before move (36)
This means that these moves could be pruned to:
33 37. JS QD
___ 3h. AS *S Horne automove
34 a7. TD JS
35 37. 9C TD
Shlomi Fish's solution is now reduced by two moves:
#00006240 Attempt: 1 NumFcs=4 (ShlomiFish) 54 moves
8a 8b 2h 8c 8d b3 63 1b{15}13
d5 6d 68 61 6h b1 5b 5h 8h
28 24 2h 54 5h 62 d2 85 36 3d
38 32{37 a7 37} 53 42 4a 4b
45 1c 1h 1a 1h 5h 45 74 7h 85
68 6h a6 7a 7h 23
~~~~~
Received on Sat Dec 01 2012 - 07:31:02 IST