I'm sure that I've mentioned the use of red/black coloring to shorten
the variation of suits from four to two when comparing layouts. It
allows similar layouts to be considered equivalent even though they
aren't exactly equal. This way, the number of possible layouts is more
manageable.
Since there hasn't been much in the way of posts lately, I thought that
I'd revisit this topic.
One key feature in my solvers is to treat suits as just red/black when
checking for equivalent layouts in the first pass. I know that it's
imperfect, but I was won over to "the dark side" by convincing myself
that the loss in accuracy was more than amply balanced by the increase
in speed and reduced memory usage.
However, there are times when I must pay for my sins (of omission in
accuracy). One of those times recently caught me unexpectedly when I was
investigating alternate solutions for deal/game #255317. Here's my
layout after 13 moves:
#00255317 Attempt: 1 NumFcs=4 (BFS Super)
============================== initial layout
-- -- -- -- -C -D -S -H
TC KD QS 9S 3S QH AH 2S
TS 5C TD AS QD TH 4H 2C
7H 5H AC 9C 4S JD QC 2D
7D 4C 7C 9H 8C KH 4D 6C
6D 2H 6H 5S 8H 3C AD JH
7S 8D 6S 5D 3D JC 3H JS
8S KS KC 9D -- -- -- --
(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)
--- --- --- --- sort: (a)
1 6a. JC fc
2 6b. 3C fc
3 6c. KH fc
4 6d. JD fc
5 68. TH JS
6 63. QH KC
7 c6. KH ec
8 7c. 3H fc
___ 7h. AD -D Horne automove
9 a3. JC QH
10 7a. 4D fc
11 76. QC KH
12 d6. JD QC
13 7d. 4H fc
___ 7h. AH -H Horne automove
============================== current layout
4D 3C 3H 4H -C AD -S AH
TC KD QS 9S 3S KH -- 2S
TS 5C TD AS QD QC -- 2C
7H 5H AC 9C 4S JD -- 2D
7D 4C 7C 9H 8C -- -- 6C
6D 2H 6H 5S 8H -- -- JH
7S 8D 6S 5D 3D -- -- JS
8S KS KC 9D -- -- -- TH
-- -- QH -- -- -- -- --
-- -- JC -- -- -- -- --
At this point, we have "4H to ec" and "4D to ec" as two possible moves.
Perform either move and the other move is blocked from ever occurring in
my solver because the resulting layouts are considered equivalent.
My Breadth-First Search solver chose "4H to ec" and was trapped into
these moves:
14 d7. 4H ec
15 b7. 3C 4H
16 2d. KS fc
17 2b. 8D fc
___ 2h. 2H AH Horne automove
18 ch. 3H 2H
19 7c. 3C fc
20 7h. 4H 3H
21 a7. 4D ec
22 c7. 3C 4D
You'll notice that the same layout can be attained in three fewer moves
had my solver investigated "4D to ec" as well? Unfortunately, it
couldn't.
14 a7. 4D ec
15 c7. 3C 4D
16 2a. KS fc
17 2b. 8D fc
___ 2h. 2H AH Horne automove
18 ch. 3H 2H
19 dh. 4H 3H
Now, it's time for a very large Margarita !!!
Received on Thu Mar 28 2013 - 02:23:33 IST