The Hardest FreeCell Games

[CraigD]

From your last statement, I am more convinced that the boards in the windows version were originally generated by dealing them out backward from the winning position.

This draws an interesting and (for me) unexpected distinction about FreeCell – unlike other solitaire games, like Klondike, it’s not an ordinary card game for which a popular computer simulation exists, but a computer puzzle game that uses cards. If you tried to play 8x4 FreeCell by dealing playing cards, you’d be frustrated, and it would be an unpopular game.

[CraigD]

While I’m a Freecell newb/slouch, winning about 50% on the windows version, and while the text based version may be causing me to play worse than normal, the impression I get from playing several purely random starting boards is that the majority of possible freecell starting boards either can’t be won, or are very hard. After a dozen games, I haven’t won one yet.

I finally found the time I needed to add a solver to my Freecell implementation, and my initial impression doesn’t appear supported. Despite my poor win record, the first 6 randomly generated boards the solver has tried had solutions. So perhaps Freecell is a usually winnable true card solitaire game, just a very difficult one unless one uses special “cheat” card arrangements.

 

The current solver version finds only one solution, not necessarily and almost certainly not the shortest one. So far, its shortest is 1369 moves, its longest a silly 283259. On my clunky old Windows laptop, solutions have taken from 14 seconds to over an hour, and I fear that a failure might take an impractically long time. Due to these very lengthy solutions, I’ve had to move most of the program’s data to (very efficiently buffered) disk storage.

 

The MUMPS code:

n (XFRECEL,:) s T=1 f  s:T]"" F="" x XFRECEL(2) r "Move card: ",R,! q:R=""  s F=$tr($e(R,1,3),"unsf","UNSF"),T=$e(R,4,6) x XFRECEL($s(F="U":4,F="N":5.1,F?1"N".e:5,F="S":6,F="F":11.2,F:3,1:7)) ;XFRECEL:Freecell game
n (XFRECEL,B) x XFRECEL(1,1),XFRECEL(1,2),XFRECEL(1,3),XFRECEL(1,4) ;XFRECEL(1): setup game B() from B
n (D) s D="" f I=101:1:113,201:1:213,301:1:313,401:1:413 s D=D_","_I ;XFRECEL(1,1)
n (M,B,C) s C=1,A=B,M=1 f I=2:1:52 d D^HPM(.A,.R,A,I) s C=R+1_","_C ;XFRECEL(1,2)
n (M,B,C,D,E) s $e(D)="",E="" f I=1:1:52 s R=$p(C,",",I),$p(E,",",I)=$p(D,",",R),$p(D,",",R,R+1)=$p(D,",",R+1) ;XFRECEL(1,3)
n (B,E) s A=B k B s B=A,B(2)=0 f I=1:1:52 s K=$p(E,",",I),Y=I-18+1,X=I-1#8+1,B(0,1,X,Y)=K,B(1,K)="1,"_X_","_Y ;XFRECEL(1,4)
n (XFRECEL,B,F) s F=$g(F) w "Board: ",$g(B,"not defined"),! i $d(B) x XFRECEL(2,1),XFRECEL(2,2),XFRECEL(2,3) w ! ;XFRECEL(2): display board B
f X=1:1:4,0,5:1:8 s Y=$o(B(0,0,X,""),-1),K=$s(Y]"":B(0,0,X,Y),'X:"",X<5:"f",1:"h") w $j($s(K="":K,K=F:"*",1:"")_K,4) ;XFRECEL(2,1)
w !," " f X=1:1:8 w $j(X,4) ;XFRECEL(2,2)
s E=1 f Y=1:1 q:'E  f X=1:1:8 s E=$d(B(0,1,X,Y)) i E w !,"  " f X=1:1:8 s K=$g(B(0,1,X,Y)) w $j($s(K="":K,K=F:"*",1:"")_K,4) ;XFRECEL(2,3)
n (XFRECEL,B,F,T) x XFRECEL(3,1) i  x XFRECEL(3,2) i  x XFRECEL(3,3) i  x XFRECEL(3,4) ;XFRECEL(3): move board B by move F,T
i F]"" s A=$g(B(1,F)) i A]"" s FA=+A,FX=$p(A,",",2),FY=$p(A,",",3) i '$o(B(0,FA,FX,FY)) ;XFRECEL(3,1)
i T]"" x XFRECEL(3,2,1) e  x XFRECEL(3,2,2) e  x XFRECEL(3,2,3) e  x XFRECEL(3,2,4) ;XFRECEL(3,2)
i $tr(T,"f","F")="F" f TX=1:1:4 i '$d(B(0,0,TX)) s TA=0,TY=0,T="" q  ;XFRECEL(3,2,1): free cell
i $tr(T,"h","H")="H" s TX=$e(F)+4,TY=$o(B(0,0,TX,""),-1),T=$s(TY:B(0,0,TX,TY),1:$e(F)_"00") i T+1=F s TA=0 q  ;XFRECEL(3,2,2): home cell
i T?1n,T>0,T<9 s TA=1,TX=T,TY=0,T=$e(F)#2+1 i '$d(B(0,1,TX)) ;XFRECEL(3,2,3): empty column
s A=$g(B(1,T)) i A]"" s TA=+A,TX=$p(A,",",2),TY=$p(A,",",3) i $s(TA:'$o(B(1,TX,TY+1)),1:TX>4) ;XFRECEL(3,2,4): onto card
x XFRECEL(3,3,1) e  x XFRECEL(3,3,2) e  x XFRECEL(3,3,3) ;XFRECEL(3,3): valid move
i 'TA,TX<5,T="" ;XFRECEL(3,3,1): free cell
i 'TA,TX>4,T+1=F ;XFRECEL(3,3,2): home cell
i $e(F)-$e(T)#2,$e(F,2,3)+1=+$e(T,2,3)!'$e(T,2,3) ;XFRECEL(3,3,3): on column
k B(0,FA,FX,FY) s TY=TY+1,B(0,TA,TX,TY)=F,B(1,F)=TA_","_TX_","_TY,B(2)=B(2)+1,B(2,B(2))=FA_","_FX_","_FY_","_B(1,F)_","_F_$s($e(T,2,3):T,TA:TX,TX<5:"f",1:"h") ;XFRECEL(3,4): make move
n (XFRECEL,B) i B(2) s A=B(2,B(2)) k B(2,B(2)) s B(2)=B(2)-1,(F,B(0,$p(A,","),$p(A,",",2),$p(A,",",3)))=B(0,$p(A,",",4),$p(A,",",5),$p(A,",",6)),B(1,F)=$p(A,",",1,3) k B(0,$p(A,",",4),$p(A,",",5),$p(A,",",6)) ;XFRECEL(4): undo last move
n (XFRECEL,B,R) s $e(R)="" i R?1.68n d S^HPM(.A,"80658175170943878571660636856403766975289505440883277823999999999999",R) i A]"" s B=R x XFRECEL(1) i 1 ;XFRECEL(5)
n (XFRECEL,B) f  x XFRECEL(5.1,1),XFRECEL(5) i  q ;XFRECEL(5.1):random board
s R=0 f I=1:1:68 s:R="0" R="" s R=R_$r(10) ;XFRECEL(5.1,1)
n (XFRECEL,B) x XFRECEL(6,1) w ! ;XFRECEL(6): show history
f I=1:1:$g(B(2)) w I,".",$p(B(2,I),",",7)," " ;XFRECEL(6,1)
n (XFRECEL,B) f I=1:1:$o(XFRECEL(7,""),-1) s J=$g(XFRECEL(7,I)) w $P(J,";",1,$l(J,";")-1),! ;XFRECEL(7): documentation
Plays the standard 8x4 Freecell solitaire card game. ;XFRECEL(7,1)
Enter: N for a new random board; N followed by a number from 0 to ;XFRECEL(7,2)
80658175170943878571660636856403766975289505440883277823999999999999 for a; ;XFRECEL(7,3)
specific board; a card ID to locate that card; a card ID (eg: 307) followed ;XFRECEL(7,4)
by a target card or place (eg: 208, 1, f, or h) to move a card; U to undo ;XFRECEL(7,5)
last move; S to list move history; F to find a solution, ;XFRECEL(7,6)
Nothing (Enter) to quit. ;XFRECEL(7,7)
n (XFRECEL,B,C) x XFRECEL(8,1),XFRECEL(8,1,1) s C=D x XFRECEL(8,2) f  s D=$o(D("")) q:D=""  k D(D) s C=C_","_$p(D," ") ;XFRECEL(8): set C=BoardID
f X=1:1:4 s A=$g(B(0,0,X,1)) i A s A(A)="" ;XFRECEL(8,1)
s D="" f  s A=$o(A("")) q:'A  k A(A) s D=D_$c($p("64,77,96,109",",",$e(A))+$e(A,2,3)) ;XFRECEL(8,1,1)
f X=1:1:8 x XFRECEL(8,2,1) s D(D_" "_X)="" ;XFRECEL(8,2)
s D="" f Y=1:1:$o(B(0,1,X,""),-1) s A=B(0,1,X,Y),D=D_$c($p("64,77,96,109",",",$e(A))+$e(A,2,3)) ;XFRECEL(8,2,1)
n (XFRECEL,B,M) k M f FA=1,0 s FX="" f  s FX=$o(B(0,FA,FX)) q:'FX  s FY=$o(B(0,FA,FX,""),-1) i FY s F=B(0,FA,FX,FY) x:FX<5&'FA XFRECEL(9,2),XFRECEL(9,4),XFRECEL(9,3) x:FX>4&'FA XFRECEL(9,4) x:FA XFRECEL(9,2),XFRECEL(9,4),XFRECEL(9,3),XFRECEL(9,1) ;XFRECEL(9): find available moves M(n)=R for board B
n I,J s I=TY n TY s TY=I x XFRECEL(3,4),XFRECEL(8) s J=FA_","_FX_","_FY_","_B(1,F)_","_F_$s($e(T,2,3):T,TA:TX,TX<5:"f",1:"h") x XFRECEL(4) s:'$d(^FRECELB(3,C)) M=$g(M)+1,M(M)=J ;XFRECEL(9,0): set M() if FA...TY a non-repeating move
s (TA,TY)=0 f TX=1:1:4 i '$d(B(0,0,TX)) s T="" x XFRECEL(9,0) q  ;XFRECEL(9,1): move to free cells
s TA=0,TX=$e(F)+4,TY=$o(B(0,0,TX,""),-1),T=$s(TY:B(0,0,TX,TY),1:$e(F)_"00") i T+1=F x XFRECEL(9,0) ;XFRECEL(9,2): move to home cell
s TA=1 f TX=1:1:8 i TX-FX!'FA s TY=$o(B(0,1,TX,""),-1) i 'TY s T="" x XFRECEL(9,0) ;XFRECEL(9,3): move to empty column
s TA=1 f TX=1:1:8 i TX-FX!'FA s TY=$o(B(0,1,TX,""),-1) i TY s T=B(0,1,TX,TY) i $e(T)-$e(F)#2,$e(T,2,3)-1=+$e(F,2,3) x XFRECEL(9,0) ;XFRECEL(9,4): move onto card in column
n (XFRECEL,B) s T=1 f  s:T]"" F="" x XFRECEL(2),XFRECEL(9),XFRECEL(10,1) r !,"Move: ",R,! q:R=""  s:$d(M(R)) R=$p(M(R),",",7) s F=$tr($e(R,1,3),"uns","UNS"),T=$e(R,4,6) x XFRECEL($s(F="U":4,F="N":5.1,F?1"N":5,F="S":6,F:3,1:7)) ;XFRECEL(10): Possible move driven interactive
f R=1:1:$g(M) w R,".",$p(M(R),",",7)," " ;XFRECEL(10,1)
n (XFRECEL,B) x XFRECEL(1) k ^FRECELB(3) s B(4)=1 f  x XFRECEL(9) s (I,B(4,B(4)))=$o(M($g(B(4,B(4))))) x XFRECEL(11,'I) q:'B(4)  i '$d(B(0,1)),$o(B(0,0,""))>4 q  ;XFRECEL(11): find a solution
s T=$p(M(I),",",7),F=$e(T,1,3),$e(T,1,3)="",B(4)=B(4)+1 x XFRECEL(3),XFRECEL(8) s ^FRECELB(3,C)="" ;XFRECEL(11,0)
K B(B(4)) S B(4)=B(4)-1 x XFRECEL(8),XFRECEL(4) ;XFRECEL(11,1)
n (XFRECEL,B) s B(4)=$g(B(4),1) f  x XFRECEL(9) s (I,B(4,B(4)))=$o(M($g(B(4,B(4))))) x XFRECEL(11,'I) q:'$d(B(0,1))  x XFRECEL(6),XFRECEL(2) r R ;XFRECEL(11.1): find next solution
n (XFRECEL,B) w "Finding a solution...",! x XFRECEL(11) ;XFRECEL(11.2)
n (XFRECEL,B) f  x XFRECEL(5.1) w "Board: ",B,!,"(",$h,") finding a solution..." x XFRECEL(11) w "(",$h,") done in ",B(4)," moves",! ;XFRECEL(11.3)

[TheBigDog]

All Hail CraigD!!! King of the Programming Geeks!!!

 

(you know I mean that as a compliment)

 

B) B) :)

 

Bill

[Mr.Odwin]

Hi Pyrotex.

 

It took me five attempts, but I cracked free cell Game 31918.

 

Here is a quick walkthrough.

 

If there are any errors, please let me know.

 

FC/31918

 

Cards:

Hearts Ace - AH

Hearts King - HK

Hearts Queen - HQ

Hearts Jack - HJ

Hearts 10 - H10

Hearts 9 -H9

Hearts 8 - H8

Hearts 7 - H7

Hearts 6 - H6

Hearts 5 - H5

Hearts 4 - H4

Hearts 3 - H3

Hearts 2 - H2

 

Clubs

 

Club Ace - CA

Club King - CK

Club Queen - CQ

Club Jack -CJ

Club 10 - C10

Club 9 - C9

Club 8 - C8

Club 7 - C7

Club 6 - C6

Club 5 - C5

Club 4 - C4

Club 3 - C3

Club 2 - C2

 

Diamonds

 

Diamond Ace - DA

Diamond King - DK

Diamond Queen - DQ

Diamond Jack - DJ

Diamond 10 - D10

Diamond 9 - D9

Diamond 8 - D8

Diamond 7 - D7

Diamond 6 - D6

Diamond 5 - D5

Diamond 4 - D4

Diamond 3 - D3

Diamond 2 - D2

 

Spades

 

Spade Ace - SA

Spade King - SK

Spade Queen -SQ

Spade Jack - SJ

Spade 10 - S10

Spade 9 - S9

Spade 8 - S8

Spade 7 - S7

Spade 6 - S6

Spade 5 - S5

Spade 4 - S4

Spade 3 - S3

Spade 2 - S2

 

There are four free cells and four sort Cells. The free cells are on the Left and the sort cells on the right.

Free cells - FC

Sort Cells - SC

There are 8 columns. They will be only be used when the columns are free. They will be numbered columns 1 - 8 from left to right. For example, Column seven will appear as FC7 (Free column seven)

 

 

Game.

 

HA - SC

HQ - SK

CJ - QH

S8 - H9

D7 - S8

H9 - S10

SJ - FC

S10 - DJ

H7 - FC

S7 - FC

C4 - FC

H3 - SC

H4 - SC

DQ - CK

SJ - DQ

C10 - FC3

SQ - HK

H9 - C10

DJ - SQ

H10 - FC6

HQ - FC8

H10 - CJ

SK - FC6

C3 - SC

C4 - SC

H10 - SJ

HQ - SK

S6 - D7

C9 - FC8

C5 - SC

D3 - SC

C9 - FC

D6 - FC8

D10 - CJ

C9 - D10

S7 - FC1

D6 - S7

HK - FC8

S5 - D6

CQ - FC

D8 - C9

C6 - SC

C7 - SC

D9 - S10

D8 - C9

CQ - FC4

HJ - CQ

C8 - SC

DQ - FC4

CK - FC5

H6 - FC

DK - FC

- game

[CraigD]

It took me five attempts, but I cracked free cell Game 31918.

Congratulation, Mr.Odwin (and welcome to hypography!) :eek_big:

 

The XFRECEL program in post #19 found a solution to Microsoft Freecell 5.1 Game 31918 (which it enumerates as board 54523812916130883389265753019259858351953670373095166620965479570541) consisting of 8893 moves, and requiring about 11 minutes on my old-ish PC.

 

Not nearly as satisfying as Mr.Odwin’s solution, showing again that a stupid computer program is no match for a smart human.

[Pyrotex]

Congratulations, Mr.Odwin!!! Thank you!!!

Now I am working on game 30466. It took me 17 (or 19 -- I lost count) tries before I succeeded. Now I cannot replicate the solution. [sigh]

 

Well done!

Pyro

[old man]

How about 31302? The game you talked about (31918) was relatively easy, I thought, by comparison.

[Essay]

Cool!

What's happening these days?

Get those toughies solved?

 

I haven't played for years, but eventually did make it thu the first 1000 without any losses (except twice when I fell asleep playing).

 

Any new tough ones? I might be intrigued.

:rolleyes:

[Pyrotex]

Not really. I don't play FreeCell that much anymore.

And when I do--and hit a hard game, I just quit and go on to a new one.

My days of taking FreeCell seriously are pretty much over.

Pyro.

[Boerseun]

Glad to see you're on the wagon, Pyro! Hold fast!

[johnfp]

Try games -1 and -2 !!!

[Pyrotex]

Try games -1 and -2 !!!

WHOA!!

DUDE!!

 

I always wondered if there were impossible games of FreeCell.

Now I know. :eek:

Those are so impossible, they're impossible by inspection.

Impossible squared.

 

thanks for bringing them to my attention.

:)

[johnfp]

LOL, no problem. if you want to be a big shot go into the registry and search for freecell, then just put the hex number in the number of games you won. 99 99 99 00 works well. The open the game and check your stats. You have to have won at least one game for the reg entry to show up though.

[mynah]

Tell him to try 11982 then. AFAIK it is regarded as unsolvable. OTOH, I know for a fact that 617 is solvable but it did take me 3 tries.....

It is said that all games except one (probably that one) have been solved.

[Loaded4th]

Just completed [Windows] game 18000 having completed each game up to that number.

[Essay]

Just completed [Windows] game 18000 having completed each game up to that number.

Wow, that's 18 times better than I did (1-1000). It can take a while, but there is always a way, eh?

 

I found 2-3 very hard games in that sample. Do you find about the same to be true?

 

~ :)

 

p.s. oops, I didn't see that post about 11982. I'll have to look....

 

p.p.s. I used to keep track of unusual games, but don't know where that is now.

Do you? Does 11982 ring a bell?

[Loaded4th]

Essay;

 

I've been playing Freecell since the release of Windows for Workgroups in 1992 with the 32-bit extension to Windows. I still use the same game (actually called The Microsoft 32,000), because the original version creates a file called entpack.ini along with the score. I keep a backup of this file without any losses, plus one (1). Thus when I launch Freecell and look at the statistics, the number of the next game to play is displayed! Over 17 years that's an average of 2.9 games per day.

 

All of the 32,000 Microsoft deals except for number 11982 are solvable. When Microsoft released Windows XP in 2001 they introduced a new version of FreeCell that extends the number of available deals up to 1 million. The first 32,000 are the same as in earlier versions of MS FreeCell. Eight of the one million deals are apparently impossible.

 

While some deals are harder than others, the level of difficulty is somewhat relative to the general strategy one plays the game. Also, the fewer the range of steps to solve any game, the harder the game will be.

 

My general strategy is to aim for alternating colors for Ace placement and to try and make each column from King down as long as possible.