Jump to content


Photo
- - - - -

The Hardest FreeCell Games


  • Please log in to reply
36 replies to this topic

#18 CraigD

CraigD

    Creating

  • Administrators
  • 8034 posts

Posted 12 December 2006 - 03:30 PM

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.

#19 CraigD

CraigD

    Creating

  • Administrators
  • 8034 posts

Posted 18 December 2006 - 09:13 AM

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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt=':)' /> 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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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(<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' /> w "Finding a solution...",! x XFRECEL(11) ;XFRECEL(11.2)
n (XFRECEL,<img src='http://scienceforums.com/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='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 likes this

#20 TheBigDog

TheBigDog

    Doing the Impossible

  • Members
  • PipPipPipPipPipPipPip
  • 4095 posts

Posted 18 December 2006 - 12:21 PM

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

(you know I mean that as a compliment)

B) B) :)

Bill

#21 Mr.Odwin

Mr.Odwin

    Curious

  • Members
  • Pip
  • 2 posts

Posted 27 March 2007 - 10:07 AM

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
  • Pyrotex likes this

#22 CraigD

CraigD

    Creating

  • Administrators
  • 8034 posts

Posted 27 March 2007 - 01:53 PM

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.

#23 Pyrotex

Pyrotex

    Slaying Bad Memes

  • Members
  • PipPipPipPipPipPipPip
  • 5702 posts

Posted 28 March 2007 - 08:23 AM

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

#24 old man

old man

    Curious

  • Members
  • Pip
  • 2 posts

Posted 10 December 2007 - 09:55 PM

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

#25 Essay

Essay

    Explaining

  • Members
  • PipPipPipPipPipPip
  • 811 posts

Posted 05 March 2008 - 03:51 AM

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:

#26 Pyrotex

Pyrotex

    Slaying Bad Memes

  • Members
  • PipPipPipPipPipPipPip
  • 5702 posts

Posted 05 March 2008 - 11:54 AM

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.

#27 Boerseun

Boerseun

    Phantom Cow of Justice

  • Members
  • PipPipPipPipPipPipPip
  • 6062 posts

Posted 06 March 2008 - 02:05 AM

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

#28 johnfp

johnfp

    Thinking

  • Members
  • PipPipPip
  • 89 posts

Posted 09 April 2008 - 08:37 AM

Try games -1 and -2 !!!

#29 Pyrotex

Pyrotex

    Slaying Bad Memes

  • Members
  • PipPipPipPipPipPipPip
  • 5702 posts

Posted 10 April 2008 - 06:19 PM

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.
:)

#30 johnfp

johnfp

    Thinking

  • Members
  • PipPipPip
  • 89 posts

Posted 11 April 2008 - 08:39 AM

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.

#31 mynah

mynah

    Understanding

  • Members
  • PipPipPipPipPip
  • 272 posts

Posted 03 July 2008 - 12:09 AM

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.

#32 Loaded4th

Loaded4th

    Curious

  • Members
  • Pip
  • 3 posts

Posted 14 March 2009 - 10:57 PM

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

#33 Essay

Essay

    Explaining

  • Members
  • PipPipPipPipPipPip
  • 811 posts

Posted 20 March 2009 - 12:47 AM

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?

#34 Loaded4th

Loaded4th

    Curious

  • Members
  • Pip
  • 3 posts

Posted 21 March 2009 - 12:49 AM

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.