Your 75 moves match mine for deal #57148. The deal isn't particularly
difficult to solve, but what's interesting is that there doesn't seem to
be any shortcuts. PatSolve finds a solution in 80 moves. I usually do
better than a five move difference because my BFS search extends to a
greater depth.
Your computer and/or your algorithm must be a lot faster than mine
because my solutions all seem to take from 2+ minutes to 4- minutes.
Below is my atomic-move solution for deal #80488. What I failed to
mention in my original message is that the solution is only difficult
for human solvers because the sequence of moves are contrary to what we
might try. Michael Keller is an acknowledged human solver, and so his
opinion on the difficulty of this deal is significant. When I tried to
solve it myself, I went down in flames!
#080488 Attempt: 1 NumFcs=4 (BFS Solver) 42 moves
5d 56 46 5c 5b 5a d5 25 b5 1d
7b 72 a2 8a 82 12 82 48 a8 78
38 7a 75 17 17 dh 15 31 47 37
c7 6d 61 41 4c 41 31 34 64 6h
65 2c
You are right about the Lore of Large Numbers hindering a complete
transversal of all possible solution paths. I believe that FreeCell is
classified in with the Traveling Salesman class of problems. As such,
it's unrealistic to examine every possible solution path. I use two
CRC32 values to filter redundancies. Even so, I still had to limit the
number of possible moves at each level to 20,000 prioritized unique
choices. My original solver used 500,000 unique choices at each level,
ran forever, and did an exhaustive search. My current solver produces
the same results most of the time, and so I'm guessing that my
prioritization logic is reasonably effective. I have no idea if any
analysis could prove one possible solution path to be better than
another. I've learned to accept that my solver seems to do a really good
job of finding a shortest-path solution, but I'll never know for sure
how often it misses and only comes "close".
Yes, there are a few "special rules" that one should adhere to if you
want to generate a universally acceptable solution. I incorporated them
into my solver because I wanted to use FcPro to "play out" a solution
from my solver. Here's a list of the special rules that I recall.
1) Meta-moves allow more than one card to be moved from a column at a
time. FcPro allows supermove meta sequences, but MS FreeCell limits them
to using at most one available empty column. If you generate atomic-move
solutions, then you need to do special testing whenever you move a card
from one column to another -- to make sure that your move won't be
misinterpreted as a meta-move. If a free cell is available, then you may
need to use it and make two moves. If a free cell isn't available, but
an empty column exists and it's not your target column, then you may be
forced to invalidate the move.
2) Auto-moves occur after a move is made ... and should not be included
(or counted) in your solver's output. However, if your first move is to
move an Ace to the foundation, then that move is not considered to be an
auto-move and must be included in your output and count.
3) Aces and Twos are exceptions to the requirement that an auto-move
only occurs for a card when both cards of a singularly lesser value and
oppositely colored suits are already on the foundation. Thus, the Two of
Diamonds will automatically play on top of the Ace of Diamonds in the
foundation -- whether or not any other Aces are present. (I know of
another valid exception to the auto-move rule, but it's not used by
other solvers and so I don't implement it in my solver.)
Danny A. Jones
WKRfresno_at_aol.com wrote:
> Using single-card moves only:
> for 57148 I get a solution at 75 moves, unsolvable at 74.
> for 80488 60 moves in 52 seconds after 31 million times through the
> main loop
> and 3.15 million stored positions.
> I may have a little time to try the other deals later.
> However, my shortest solutions are not yet certain. The only way that
> I know
> of to be sure is to allow all legal moves. But that isn't practical
> for most
> deals as the tables grow very quickly. One may be able to show/prove
> that the
> disallowed moves are not needed, but I don't know how to do that
> except with
> statistics. Here's one possible disallowed move: I remember reading
> that the
> Woods solver won't move a single card from the top of a column to an
> empty
> column. That restriction will make most deals go faster, but it's
> possible that
> there is some odd deal lurking in the shadows that can be solved in
> fewer moves
> without the ban.
> Bill Raymond
Received on Tue Sep 30 2003 - 16:18:14 IDT