25

When I have free time in small durations, I often play Free Cell on my phone. The app that I use permits unlimited undos, and because of this I currently have a run of 603 wins, with 655 total wins and 10 total losses.

As is demonstrated by those statistics, my 10 losses occurred during my first 52 games. Prior to using this app, I had only played Free Cell very rarely.

As my statistics approach a 1% loss rate, I have to wonder: Given an unlimited ability to undo your moves, is there any initial deal of Free Cell that is impossible to solve?

A proof one way or another would be ideal (although I admit that I doubt I'd be able to comprehend such a proof), although an authoritative source would be a good alternative.

Improve this question
2

1 Answer 1

Reset to default
39

It's not hard to prove that an unsolvable start exists. Just imagine a start where the only possible first moves would be moving cards to the extra cells. In some versions, -1 and -2 are examples of this though the only way to play them is to choose that seed. enter image description here

If you only count setups which can exist in normal play, seed 11982 in the Windows version is an example of this: enter image description here

Of the original 32000 games in Freecell, 11982 is the only one for which no legitimate solution was found. Since then, several computers and players have failed to find a solution- to the point where every possible combination of moves has been tried and has failed.

Improve this answer
6
  • 3
    As far as I've read, the 32,000 "deals" in the original Windows version are accidentally those produced when the MS C Compiler's random number generator is seeded with the values 1-32,000. In other words, they don't have any special status as such, and 32,000 is of course an infinitesimal fraction of the number of possible ways of shuffling a deck of cards (and a small fraction of the number of possible shuffles that even a modest random number generator could produce).
    – Neil Coffey
    Apr 19, 2014 at 3:27
  • 4
    Definitely accidental. The aforementioned random number generator has 15 bits of entropy, which means 2^15 possible orderings. That's 32,768.
    – ikegami
    Apr 19, 2014 at 6:18
  • @ikegami: It has more bits of state, but it only hands out the higher-order bits (because low-order bits are crappy with LCGs).
    – Joey
    Apr 27, 2014 at 19:54
  • 2
    Do you have a source for all the 32000 games being solvable except for game 11982? There is a new question on the site where the user is asking if a different game is unsolvable.
    – Thunderforge
    Jul 16, 2016 at 1:21
  • @Thunderforge I did at the time. It was the record of a group that between them tested and solved every other game. No idea if it's still around.
    – Comic Sans Strikephim
    Jul 16, 2016 at 12:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .