Sunday, November 15, 2009

Freecell: probability of having no valid move at start

I love FreeCell crazily. When the game begins, you get 8 columns of cards. The only rule to move a card onto top of another one is that the numbers on two cards are continuous. It's possible that all of the numbers on 8 top cards are not continuous to each other so you have to move some to the free decks. How likely this is to happen?

In practice not very likely. I have played a few hundred games and it didn't happen to me.

BTW, finding a solution to a FreeCell game is NP-complete (according to Wikipedia), but generally one can finish it within a few minutes. Again it shows NP-complete problems are not that hard to solve in practice.

0 comments: