Freecell Solitaire: What Are Open Slots Worth?

Today we analysed part of Freecell solitaire. In Freecell there are

• 4 reserve slots which can hold one card, and
• 8 tableau slots which can hold a stack of cards.

A stack is a set of cards of alternating colors, of increasing ordinality. E.g., a red 3 on a black 4 on a red 5 is a stack of 3 cards.

How big a stack can you move, given some open reserve and tableau slots?

• If you have no open reserves, you can move a stack of size 1. (One card only.)
• If you have one open reserve, you can move a stack of 2. (Given a red 3 on a black 4: you can move the red 3 to the open reserve, then move the black 4 to its destination, then move the red 3 onto the black 4.)
• What if you have 2 open reserves? (A stack of 3 can be moved.)
• What if you have r open reserves? (A stack of r+1 can move.)
• What if you have 1 open tableau and 0 open reserves?
• What if you have t open tableaux and r open reserves?

To analyse this, we define a function S(t,r) that says how big a stack can be moved when there are t open tableau and r open reserves. S satisfies this recurrence relation:

• S(0,r) = r+1, and
• S(t,r) = 2S(t-1,r), for t>0.

The first case where t=0 is known. In the second case I can use t-1 open tableaux and r open reserves to move S(t-1, r) cards to one of the free tableaux. Now I have t-1 open tableaux and r open reserves to move the next S(t-1, r) cards in the same stack to its final destination. Then I can move the first S(t-1, r) to form another stack.

Here's a solution to the recurrence for S:

• S(t,r) = 2^t(r+1)

Discussion: Computer scientists see a recurrence like the one shown above, and tend to think it's a reasonable way to define a function. Mathematicians don't like defining a function in terms of itself, because you might get "definitions" that read like

• g(x) = 0, if g(x)=0, and
• g(x) = 1, otherwise.

• f(x) = 0, if f(x)=1, and
• f(x) = 1, otherwise.

The fix to this is to say that a recurrence is equation that is true of the function we are talking about, and ask what functions solve that equation. In the case of S on the nonnegative integers, there is a unique solution. For f there are no solutions, and for g there are many solutions. For S defined on the real numbers, there are many solutions.