[Jay-qu]

I am interested to know how it is certain that every game is solvable, could it be proved mathematically?

[CraigD]

Originally Posted by Jay-qu

I am interested to know how it is certain that every game is solvable, could it be proved mathematically?

It could be proven exhaustively – that is, permute all possible move sequences to find the shortest solution for any given board (game #). Such a program doesn’t seem to challenging, however, computationally, there are far too many possible games for an exhaustive proof.

A question I have is how starting boards are generated from game #s. There are far fewer game #s than possible boards: 32,000 or 1,000,000, depending on version, vs 52!/4 = 20,164,543,792,735,969,642,915,159,214,100,941,743 ,822,376,360,220,819,456,000,000,000,000. Does anyone know this algorithm - or if it is an algorithm, vs. a table?

[C1ay]

Originally Posted by Jay-qu

I am interested to know how it is certain that every game is solvable, could it be proved mathematically?

Dave Ring formed the Internet Freecell Project in the 1990's to answer this question. Human solvers worked collaboratively to show that all of the original 32,000 games were solvable. Game 11,982 which was never solved by any of them. His project wrapped up in 1995. The current iteration has 1,000,000 games of which 8 have been found to be unsolvable. There are actually 52!/8! possible games but many are not dealt because of similarity to other deals. Freecell Pro has 8 billion+ deals along with several other features Freecellers might like....

[TheBigDog]

I remember the claim that the original 32000 games were all solvable. And I guessed that they were generated backward to make sure that this was a true statement.

I spent 2 hours on 11982 last night after reading this thread for the first time. Nothing like the combination of "impossible" and "free cell" to qualify as a full fledged challenge.

Bill

[CraigD]

Originally Posted by CraigD

There are far fewer game #s than possible boards: 32,000 or 1,000,000, depending on version, vs 52!/4 = 20,164,543,792,735,969,642,915,159,214,100,941,743 ,822,376,360,220,819,456,000,000,000,000.

In stating the number of possible starting freecel boards as 52!/4, I’m accounting only for the interchangability of the 2 red and 2 black card suites. I’ve failed to account for the interchangability of the 8 columns of cards

Originally Posted by C1ay

There are actually 52!/8! possible games but many are not dealt because of similarity to other deals.

52!/8! =2000450773088885877273329287113188665061743686529 843200000000000 =~ 2.0e63, or 52!/(8!4) = 50011269327222146931833232177829716626543592163246 0800000000000 =~ 5.0e62, which accounts for the the interchangeable suites, is the number given by most sources. However, I don’t think it’s correct, either.

The initial board has 4 columns of 7 cards, and 4 of 6. Only columns with like numbers of cards can be significantly exchanged. So the number I calculate is 52!/(4!4!4) = 35007888529055502852283262524480801638580514514272 256000000000000 =~ 3.5e64

I wonder which of these big numbers – 52!/(8!4) or 52!/(4!4!4) – is correct?

[CraigD]

Preparing to try a few of the questions in this thread, I wrote a text based MUMPS implementation of the Freecell game. 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.

In the spirit of showing source code, even if, as it appears, I’m the only person on this site who uses MUMPS, here it is:

n (XFRECEL,B) f  s F="" x XFRECEL(2) r "Move card: ",R q:R=""  s F=$tr($e(R,1,3),"uns","UNS"),T=$e(R,4,6) x:T=""&$d(B(1,F)) XFRECEL(2) r:T=""&F " onto: ",T w ! x XFRECEL($s(F="U":4,F="N":5.1,F?1"N":5,F="S":6,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-1\8+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,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,F) s $e(F)="" i F?1.68n d S^HPM(.A,"80658175170943878571660636856403766975289505440883277823999999999999",F) i A]"" s B=F 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 F="n" f I=1:1:68 s F=F_$r(10) s:$e(F)="0" $e(F)="" ;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 (eg: 307) followed by a target card or place ;XFRECEL(7,4)
 (eg: 208, 1, f, or h) to move a card; U to undo last move; S to list move ;XFRECEL(7,5)
 history; Nothing (Enter) to quit. ;XFRECEL(7,6)

Its only improvements on the usual Windows implementation are unlimited undos, a move record, and the aforementioned ability to start with any possible board. It’s only bells and whistles are self-documention (I can rarely remember how to use little apps like this just a couple of days after I’ve written them), and a feature to location a card of interest on demand with a “*”.

[TheBigDog]

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. The fact that a very small number of those games may be unbeatable could be because of a flaw in the logic of that program that creates situations where there is no symetry between unplay and play.

Bill

[CraigD]

Originally Posted by TheBigDog

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]

Originally Posted by 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,B) 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-1\8+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)



Bill