Sunday, May 17, 2009

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) = 2t(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.

No comments:

Post a Comment

About Me

I'm research faculty at MIT, and Chief Architect at Tokutek.