×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

How Windows FreeCell Gave Rise To Online Crowdsourcing

samzenpus posted about 2 years ago | from the mastering-the-game dept.

Math 93

TPIRman writes "In 1994, a physics doctoral student named Dave Ring assembled more than 100 math and puzzle enthusiasts on Usenet for what became one of the earliest online 'crowdsourcing' projects. Their goal: to determine if every hand in Windows' FreeCell solitaire game was in fact winnable, as the program's help file implied. Their efforts soon focused in on one incredibly stubborn hand: #11,982. They couldn't beat it, but in the process of trying, they proved the viability of an idea that would later be refined with crowdsourcing models like Amazon's Mechanical Turk."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

93 comments

Finally! (4, Funny)

Anonymous Coward | about 2 years ago | (#39658113)

I can figure out how to solve Free Cell...

(scrambles back to Spider Solitaire)

Re:Finally! (2)

Drinking Bleach (975757) | about 2 years ago | (#39658523)

Spider even on two suits is fairly difficult, on four suits it's way harder than Freecell usually is :)

Re:Finally! (3, Interesting)

digitalhermit (113459) | about 2 years ago | (#39659167)

I played about 5,000 hands of Spider Solitaire at 4 suits.. My win percentage is about 8% but I can go for many games at a time without a win and then get 2 wins in a row..and once 4 wins in a row.

Re:Finally! (0)

Anonymous Coward | about 2 years ago | (#39669085)

Spider may be harder to win, but nobody expects to win all hands of it. In free cell the objective is to never lose.

Re:Finally! (1)

unixisc (2429386) | about 2 years ago | (#39670319)

Usually, when I play Freecell, I make it tougher for myself by using a self-imposed rule that the cards released have to be in the sequence of SHCD, HCDS, CDSH or DSHC. That makes it more challenging and interesting. Of course, in the Freecells from Vista on, one can undo and put the card exactly in the slot one wants, so this is no longer a challenge there. As for the above game 11982, it would seem to me that anytime someone buried all the aces right at the bottom, such a game would be impossible to win.

Re:Finally! (0)

Anonymous Coward | about 2 years ago | (#39658897)

I can figure it out too: Ctrl-Shift-F10

I tried to crowdsource minesweeper (4, Funny)

Anonymous Coward | about 2 years ago | (#39658135)

In real life, with real mines. Terrible results. While we did find most of the mines, it turns out that people are terrible at safely locating them. Lots of dead bodies, limbs, etc, everywhere.

Re:I tried to crowdsource minesweeper (1)

ScaledLizard (1430209) | about 2 years ago | (#39672143)

In real life, with real mines. Terrible results. While we did find most of the mines, it turns out that people are terrible at safely locating them. Lots of dead bodies, limbs, etc, everywhere.

Please mod this anything you want, but not funny.

Missing from article (4, Interesting)

uigrad_2000 (398500) | about 2 years ago | (#39658205)

It doesn't look like he ever proved that the hand in question was not solvable. It only claims that by having many human players try to solve it and several different AI approaches, that it was never solved.

The article ends by implying that this was a victory, because the outcome of all 32,000 hands is now known. But, as far as I can tell, one hand is still undecided!

No mathematical proof (2)

Petersko (564140) | about 2 years ago | (#39658253)

The only way to "prove" it would be to identify a definitive proving mechanism, and nobody has done so. No computer simulations have been able to solve it, nor have any participants. That's going to be as good as it gets.

Re:No mathematical proof (1)

Anonymous Coward | about 2 years ago | (#39658389)

... if you exhaust the space of all legal moves and none are winnable you have proven the hand unsolvable

Re:No mathematical proof (1)

Hillgiant (916436) | about 2 years ago | (#39659817)

You have demonstrated it is unsolvable, you have not proven anything.

Re:No mathematical proof (2, Informative)

Anonymous Coward | about 2 years ago | (#39659923)

http://en.wikipedia.org/wiki/Proof_by_exhaustion

Re:No mathematical proof (1)

uigrad_2000 (398500) | about 2 years ago | (#39665907)

The great-grandparent of this post said that you have "proven the hand unsolvable", when he probably meant to say "proven the hand unwinnable."

So, the post you replied to was correct. If something is "demonstrated to be unsolveable", then nothing has been proven. I'm not sure if it's relevant, however, unless we are all extremely concerned about the proof-reading ability of the great-grandparent.

how is that not a proof? (1)

Chirs (87576) | about 2 years ago | (#39660099)

Isn't this just a case of "proof by exhaustion"? We divide up the problem into the space of all legal moves given the initial starting point, then show that none of them lead to the desired state.

According to Wikipedia this is how the four colour theorem was proved.

Re:No mathematical proof (5, Informative)

Anonymous Coward | about 2 years ago | (#39660667)

Here's a program that does it.

http://kurage.nimh.nih.gov/tomh/public_html/archives/patsolve-3.0.tgz

The program generates a list of axioms, followed by a list of transformations chosen from a finite set.

After a finite number of steps, the proof reaches a conclusion that that game (and that's the only one
out of the original 32000) is unsolvable. This is a real, valid mathematical proof. It's just very long
and hard to read. But it is of finite size, and follows all the normal rules of mathematical proof.

You're welcome to try to come up with a shorter proof.

Re:No mathematical proof (3, Informative)

uigrad_2000 (398500) | about 2 years ago | (#39666037)

The article seemed to imply that it was proved unwinnable, but never absolutely stated it..

I found something a little better: http://www.solitairelaboratory.com/fcfaq.html [solitairelaboratory.com]

11982 has now eluded solution by probably thousands of human solvers, and at least eight independent computer programs I am aware of (most of which are designed to search exhaustively for a solution), and I am confident in calling it impossible.

I really wish the FAQ had been linked from the slashdot summary, it's far more interesting, and better written than the gaemological.com article.

As I understand the quote above, there is at least 5 different programs (ie. more than half of "at least eight") that have solved hand 11982, and all arrived at the same solution: #11982 is not winnable. This has persuaded the FAQ's author to call [winning the hand] impossible.

Re:No mathematical proof (1)

Dr. Tom (23206) | about 2 years ago | (#39667199)

The logic here is that a given solver "might have a bug" and therefore not provide a correct answer.
Just throwing 5 or 8 different programs at it therefore might be suspect.

However. Freecell is really a very simple game. A computer program is very much like a mathematical proof, ask any programmer who has also written proofs. All of the solvers use optimizations to keep the search size down, but each of these optimizations is really a theorem stating that certain segments of the game tree do not have to be searched. A stronger statement would be that just one program found a given game unsolvable, and that program uses only prunes (theorems) that have been proved to be correct. I happen to know that even with only very simple prunes that are quite trivial to show to be correct, game 11982 is not solvable. The proofs I used to arrive at this conclusion have been checked by others, too. I'm not sure anybody has published a formal document anywhere, but you are welcome to look at the code.

Of course, you can win if you cheat. :-)

(Even a "mathematical" proof might be shown to be wrong, in a way that even many experts might have missed. This doesn't really apply here, though, because the game tree for 11982 is actually quite small.)

Easy to create unsolvable free cell board (0)

Anonymous Coward | about 2 years ago | (#39667235)

I wrote a program to solve free cell boards back in 1999 using a weighted tree structure. It would search the entire tree space if no solution could be found. I don't remember if that particular MS game was one of the unsolvable ones, but it is trivial to generate an unsolvable free cell board.

Just start by laying aces in the first row, then continue with kings, queens, jacks, tens, in descending order until you run out of cards. That is one example of many provably unsolvable free cell boards and proves the Microsoft help text to be wrong for free cell in general. You don't need Windows to play free cell.

By the way, the only programming challenge was memory, not speed. Every game can be completely searched quite quickly by a modern computer, but with my implementation, some took over a gig of memory.

After I wrote the program, I lost interest in solving them myself, though...

Re:Easy to create unsolvable free cell board (1)

Malvineous (1459757) | about 2 years ago | (#39672099)

...but it is trivial to generate an unsolvable free cell board. Just start by laying aces in the first row, then continue with kings, queens, jacks, tens, in descending order until you run out of cards. That is one example of many provably unsolvable free cell boards and proves the Microsoft help text to be wrong for free cell in general. You don't need Windows to play free cell.

No, but the help text only referred to the Windows version, not Freecell in general. Their point was that the algorithm that they use to generate games only produces solvable ones.

I'm not sure if it still works in recent Windows versions, but with XP and earlier there was an easter egg where you could request game -1 or -2 and it would present a neatly ordered and unsolvable game, just as you describe. I guess this was to prove that an unsolvable Freecell is easy to create, which makes their algorithm all the more special as it only produces solvable games. I am curious how they achieve this.

Re:Easy to create unsolvable free cell board (0)

Anonymous Coward | about 2 years ago | (#39672911)

I am curious how they achieve this.

The 'simple' way would be to start at the winning position, then randomly select moves until you end up at a starting position. With a few tricks thrown in to stop your algorithm stuck in loops and direct it to the evenly stacked columns.

Re:No mathematical proof (1)

Shifty0x88 (1732980) | about 2 years ago | (#39664777)

You have demonstrated it is unsolvable, you have not proven anything.

All you need is ONE hand to not be solvable, and their entire argument is invalid.

"Their goal: to determine if every hand in Windows' FreeCell solitaire game was in fact winnable, as the program's help file implied."


So any one non-winnable hand, means that every hand in FreeCell is NOT winnable.

(Proof By) Counterexample [wikipedia.org]

Re:No mathematical proof (1)

Dr. Tom (23206) | about 2 years ago | (#39666991)

No, you can provably search the entire game tree. It has been done for all 32000 of the "original MS" games, and many more. Most of them are quite small and easily handled on even a modest computer.

Re:Missing from article (1)

krakelohm (830589) | about 2 years ago | (#39658279)

At what point would you call the hand unsolvable and consider the experiment finished?

Re:Missing from article (1)

SJHillman (1966756) | about 2 years ago | (#39658427)

I would assume there's only a finite number of possible moves. I don't know how far they've gotten into it before getting stuck, but I would assume it's well before there's any open cells (other than the four up top), so I would imagine there's only a few hundred - or thousand at most - possibilities.

Re:Missing from article (1)

AdrianKemp (1988748) | about 2 years ago | (#39659375)

No because it's a branching game, one move now opens and closes other possible moves.

There's no doubt that a computer can solve it, and on modern hardware it probably wouldn't even be measured in years... but it's not a quick solution.

Re:Missing from article (0)

Anonymous Coward | about 2 years ago | (#39661461)

It takes seconds on modern hardware. I'm totally serious, I've done it.
Seconds.

Re:Missing from article (1)

Dr. Tom (23206) | about 2 years ago | (#39666643)

Unsolvable games are rather easy to prove. They usually have very small game trees (i.e., you get "stuck" pretty quickly). Many games have extremely large trees, and for those, you need to search a long time to find the solution. All of the original 32000 games have rather small trees, though, and it doesn't take very long to solve them all. But there are some pathological cases (some have been designed by hand) that can cause a given solver to get lost in the weeds. A different solver, or even the same one with a small change in search order, might solve it quickly. These sorts of programs just search the tree in some order. There probably exist some "very high level" theorems that you could use to prune these extremely large trees, and those would make the solvers even faster than they are.

Even Sudoku is a "hard" game in general, although in practice it is mostly trivial for computers; solvers exist that take literally milliseconds to solve a given board.

Re:Missing from article (1)

uigrad_2000 (398500) | about 2 years ago | (#39665547)

My point (in the top post of this thread) was that the article is vague, which is very bad form for mathematical subject matter.

If you have to assume that they went "so far that...", then you've proved the point. The article is vague.

I really want to tell my friends that one of the 32,000 is cannot be won, and the article certainly seems to imply this, but from the article, it's just not clear if that is true.

The hypothetical question above ("At what point ... consider the experiment finished?") has a very simple answer. Once you give up and stop researching the problem, you can consider the experiment finished. The bigger question (What is required for the experiment to be successful) was implied, but not asked.

Re:Missing from article (1)

cohensh (1358679) | about 2 years ago | (#39659117)

About the same time you assume P != NP since no one has been able to solve an NP-complete problem in P.

Re:Missing from article (0)

Anonymous Coward | about 2 years ago | (#39661929)

FreeCell is not np-anything. It's a finite tree that can be exhaustively searched.

Re:Missing from article (1)

cohensh (1358679) | about 2 years ago | (#39662615)

My point wasn't that freecell is np anything, it's that people thing np != p because no one's been able to solve an np-complete problem in p, not because there's a formal proof.

Re:Missing from article (1)

Dr. Tom (23206) | about 2 years ago | (#39666659)

The tree might be finite, but still have more than 10^10000 nodes, in this case, you will never find the solution (especially if it is unique).

Re:Missing from article (1)

Stuarticus (1205322) | about 2 years ago | (#39671637)

I have a solution to this question that is quite elegant, however it is too long to fit in this comment.

Re:Missing from article (1)

Joce640k (829181) | about 2 years ago | (#39658331)

It would be easy to write a program to brute force it...which would be a proof even if there's no fancy theory telling you why.

Here is the game in question. (0)

Anonymous Coward | about 2 years ago | (#39661135)

AH 3D KD JC 6C JD KC
AS 3H 6H 5D 2C 7D 8D
4H QS 5S 5C TH 8H 2S
AC QC 4D 8C QH 9C 3S
2D 8S 9H 9D 6D 2H
6S 7H JH TD TC QD
TS AD 9S KH 4S 4C
JS KS 3C 7C 7S 5H

The program has been written. See http://fc-solve.shlomifish.org/

Re:Missing from article (1)

uigrad_2000 (398500) | about 2 years ago | (#39665653)

It would be easy to write a program to brute force it...which would be a proof even if there's no fancy theory telling you why.

Um, writing a program to "brute force it" is always easy. The notion of "brute force" is that you don't worry about optimizations, because the problem you are solving can be solved in the given time, even without reducing the problem space. Therefore, the writing of a brute force method is always "easy".

Unfortunately, if the problem space is already reduced by identifying equivalent states, or by other elimination factors, and it still takes too long, then the solution is never to "brute-force it". That would mean to throw away all your optimizations, and run an inefficient search. I'm not sure why you are suggesting that they do that.

Re:Missing from article (1)

Dr. Tom (23206) | about 2 years ago | (#39666835)

Most of the existing solvers make use of theorems about certain move sequences to prune the tree. For example, it is trivial to get into a loop of repeated moves, and in this sense game trees can be "infinite". But those are obvious optimizations.
What would be interesting is to find theorems concerning more complicated positions that allow you to prune huge branches.
This is the only way to attack some problems. You probably won't find a "theorem" that applies to the starting position, but I'm sure there are many positions where you can apply some reasoning, rather than simply trying all possible combinations. For example, don't move the same card twice in a row, don't move card A and then card B and then card A again, if the moves are not related, and in general don't make a move that brings a position back to one that you've been in before. And so on.
Some of these theorems might be very complex, and there might even be some set of them that always make the game tree "small". That's the kind of thing you really want, if you want to "prove" that you can or can't solve a game.

That said, most Freecell games have small game trees and are easily solved.

Email me if you want some harder ones.

early distributed computing (1)

goombah99 (560566) | about 2 years ago | (#39658447)

The first large distributed computing project was zilla [wikipedia.org] . it predated this. It ran on the Next Computers. It is still baked into all OSX computers (it's in your sharing preferences.). Check out my sig.

Re:early distributed computing (5, Interesting)

eulernet (1132389) | about 2 years ago | (#39658843)

No, the first large distributed project is the Cunnigham project:
http://books.google.com/books?id=udr3tHHwBl0C&lpg=PA375&ots=s4GNA3LkQo&pg=PA375 [google.com]
that started in 1949 on the ENIAC !

And this project is still ongoing.

In fact, this search started with human efforts, so it was already heavily crowd-sourced since a least 3 centuries.
The culmination of the manual effort came in 1903, when Frank Nelson Cole showed that:
193,707,721 × 761,838,257,287 = 2^67 - 1
It took 3 years of Sundays to discover.
http://www.rutherfordjournal.org/article030105.html [rutherfordjournal.org]

Re:early distributed computing (1)

fatphil (181876) | about 2 years ago | (#39660271)

Damn - I would have modded this up if it wasn't for the fact that I've already posted a highly redundant post saying a fraction of the same thing!

Re:Missing from article (2)

Baloroth (2370816) | about 2 years ago | (#39658663)

It has, according to Wikipedia, been tested using exhaustive-solution solvers, which does prove it is impossible. So not undecided, no, but not proven by them (they were correct, though, so they deserve recognition for that.)

Re:Missing from article (1)

Anonymous Coward | about 2 years ago | (#39660423)

It has been shown to be unsolvable by exhaustive search. It's easy these days.
I wrote a program to exhaustively search the game tree myself.

http://members.tripod.com/professor_tom/archives/patsolve-3.0.tgz

This does constitute a mathematical proof. It is deterministic, finite, and easily checked to be correct. It's just really long, if you wrote it out on paper.

Re:Missing from article (0)

miknix (1047580) | about 2 years ago | (#39662257)

In other news, how Steve Ballmer gave rise to the dancing monkeys throwing chairs .

Not solved != proof (2, Insightful)

roothog (635998) | about 2 years ago | (#39658241)

FTFA:

So when that final push on No. 11,982—an effort aided by humans and even a handful of game-solving programs—met with failure, Ring celebrated. Is every hand in FreeCell winnable? No. Thirty-one thousand nine hundred ninety-nine hands are winnable. And one isn’t. He proved that.

No he didn't. Unless the exploration of the game space was exhaustive, there's no proof. A bunch of people playing the game and failing to solve it isn't a proof.

Re:Not solved != proof (5, Informative)

tigre (178245) | about 2 years ago | (#39658341)

Unless the exploration of the game space was exhaustive, there's no proof.

Wikipedia claims that exhaustive search has been performed, assuming that the same hand numbering is used:
http://en.wikipedia.org/wiki/FreeCell#Impossible_games [wikipedia.org]

Re:Not solved != proof (1)

canajin56 (660655) | about 2 years ago | (#39660529)

Actually you don't need to assume the same numbering scheme, as the citation for "believed unsolvable" actually says it's been exhaustively tested by machine and proved unsolvable.

Re:Not solved != proof (4, Funny)

Anonymous Coward | about 2 years ago | (#39658391)

Based on my own results, I'd have to say that thirty-one thousand, nine hundred, and ninety-nine hands are not winnable, and one is.

As a corollary result, I seem to have proven that I really suck at FreeCell.

Re:Not solved != proof (0)

Anonymous Coward | about 2 years ago | (#39659577)

huh? you can do proofs without exhaustive searches using logic. in fact, they are usually preferred.

Re:Not solved != proof (0)

Anonymous Coward | about 2 years ago | (#39660453)

It has been exhaustively searched. This constitutes a rigorous mathematical proof. The game tree for FreeCell isn't very big.

Re:Not solved != proof (1)

Impy the Impiuos Imp (442658) | about 2 years ago | (#39663887)

'Tis true. Finding a solution proves the hand is winnable. Not finding one does not prove the opposite, unless you examine every possibility.

In a case like this, it suggests that, but does not prove it. Even if the hand can be won, why this particular one is so stubborn is of interest all by itself.

Re:Not solved != proof (1)

Dr. Tom (23206) | about 2 years ago | (#39666911)

Unsolvable deals often have very small game trees. You get stuck very quickly, and there are no more moves. So showing something to be unsolvable is usually rather easy. It's easy to search the ENTIRE game tree. That's a proof. A bunch of people trying for a long time might not search every possible position, but in this case, the computer can do it, provably.

If the solver takes days and days and days and still hasn't found a solution either way, then you have no proof of anything. Even if "most" unsolvable games have small trees, there could be some that are large. We don't know, and searching all 52! deals hasn't been done yet. :-)

(Yes, I know, there aren't really that many, due to symmetry.)

GNU & GPL (0)

Anonymous Coward | about 2 years ago | (#39658379)

I would be hard pressed to say that Freecell gave rise to this notion when GNU & Linux were more popular and earlier examples of crowdsourcing.

Re:GNU & GPL (1)

icebraining (1313345) | about 2 years ago | (#39659115)

GNU and Linux were in fact collaborative projects, but not with "crowds" - in fact, they have very small groups of highly knowledgeable experts. There are big differences in terms of the necessary mechanisms for coordination, trust, etc.

"Like a virtual coffee shop" (0)

Anonymous Coward | about 2 years ago | (#39658541)

I like it when one needs an analogy to explain what is an newsgroup in 2012: "Newsgroups were a place where professional students could converge from across the globe, like a virtual coffee shop, each one catering to particular topics like politics or juggling or Tori Amos."

Concept so hard one needs a virtual coffee shop analogy, as if none is used internet. Hint: there is a easier analogy, it's called forum.

Re:"Like a virtual coffee shop" (1)

tompaulco (629533) | about 2 years ago | (#39665197)

I'm familiar with newsgroups, can someone give me an analogy to explain what is a coffee shop?

Re:"Like a virtual coffee shop" (0)

Anonymous Coward | about 2 years ago | (#39695925)

Coffee shop - where pretentious people go to hang out and look cool while drinking coffee.

Did they try all of them? (1)

coldfarnorth (799174) | about 2 years ago | (#39658551)

Don't forget hands -1 and -2.

Re:Did they try all of them? (0)

Anonymous Coward | about 2 years ago | (#39658627)

I just played -3, it was pretty easy.

Re:Did they try all of them? (1)

Dr. Tom (23206) | about 2 years ago | (#39666459)

Those are both solvable. If this is they. The exact implementation for the deal generator might not work the same way for negative numbers. This assumes they are 64 bits.

9D 9C KC 9H 2S 8H 6H
QD TH 4D 7S 2H 6D 3S
8D QC 3C AD TC 8S TS
AH QS AS KH 7C QH 5C
5S 3H 9S 6C JD 6S
JS 4C AC JH 3D 8C
7D 2C 2D JC 5D 5H
7H 4H 4S KD KS TD
---
#-2: A winner.
99 moves.

TC 8S 8C 6C 5H 5C 9C
2S TD 6D 8D 9H 9S 6S
JS TH 3S JD 4H QC 3D
5S QS KD AH AS JH 4S
4D 4C 7D JC 2D AD
6H KH TS 7H QD QH
3H 2C KC 2H 5D 9D
7C KS 8H 3C AC 7S
---
#-1: A winner.
78 moves.

By the way, Freecell may be NP-hard ... If a game is UNSOLVABLE it is probably EASY to show, because typically, unsolvable games have VERY SMALL game trees. But this one, below, is an example of a game that has an ENORMOUS game tree, and in general it is very hard to predict the size of the tree. A program that does brute force search WILL solve even NP-hard problems, if you wait long enough. But long enough could be well over the lifetime of the universe (by many, many orders of magnitude).

AS AC KS KC 4S 4C QS
AD AH KD KH 4D 4H QD
7S 7C 2S 2C 6S 6C QC
7D 7H 2D 2H 6D 6H QH
5S 5C JS JC 8S 8C
5D 5H JD JH 8D 8H
3S 3C 9S 9C TS TC
3D 3H 9D 9H TD TH

A human might be able to solve that game anyway, if they get lucky. It's certainly not easy for my program.
This game was artificially constructed, obviously. It may not be solvable, I don't know. Maybe Shlomi's program can do it.

There was a similar effort in the UK (4, Informative)

digitig (1056110) | about 2 years ago | (#39658921)

This was also done at about the same time in the UK, by a group of people on Cix (a CoSy conferencing system), with the same conclusion, except we found two more unsolvable ones that I suspect the American team didn't look at: -1 and -2. For what it's worth, I invented the notation we used to document solutions, and one of the team produced a solver that exhaustively checked the game space for 11 982 and indeed found it impossible. So give or take formal proof of the solver's correctness, it is proven that not all games are solvable.

Re:There was a similar effort in the UK (1)

Kalriath (849904) | about 2 years ago | (#39665581)

-1 and -2 are not part of the actual gamespace - they will never be selected by Free Cell except by use of the "Select Game Number" function, and are designed specifically to be unsolvable.

They could have just asked my mom. (2)

Zatar (131299) | about 2 years ago | (#39658931)

My mom did this during the 80s by herself. She had a (very) little list of which deals she couldn't solve. I wonder how many other people have done the same.

She still goes through 20 deals every day but with the new version she knows she'll never finish.

Re:They could have just asked my mom. (1)

KingAlanI (1270538) | about 2 years ago | (#39727323)

Yeah my dad started counting up and giving each one a difficulty rating. not sure how far he got with it.

Did it ever get solved? (1)

pwnyxpress (2597273) | about 2 years ago | (#39658987)

Cause if it didn't, this is going to drive me nuts until i find the answer or write a program to solve it for me. (God knows I have a hard enough time solving the easy ones)

Re:Did it ever get solved? (0)

Anonymous Coward | about 2 years ago | (#39660575)

A program to exhaustively search it is here:

http://kurage.nimh.nih.gov/tomh/public_html/archives/patsolve-3.0.tgz
or
http://members.tripod.com/professor_tom/archives/patsolve-3.0.tgz

Just the one unsolvable game.

Personally I prefer Seahaven Towers. There are many more unsolvable ones, and that's why I wrote the program. FreeCell is a simpler subset. There are some Seahaven games with extremely large game trees which are still unknown.

Re:Did it ever get solved? (0)

Anonymous Coward | about 2 years ago | (#39660877)

see http://fc-solve.shlomifish.org/ for a program that proves this game unsolvable

stone soup (2)

JackPepper (1603563) | about 2 years ago | (#39659035)

In ye olde England, Stone Soup was the first 'crowd sourcing' project. Whenever I read these 'first' summaries all I think is the shoulders of giants, this one experiment.

I think it's solvable. (0)

rickb928 (945187) | about 2 years ago | (#39659163)

Just because I have a Freecell game that permits undo, and I have yet to lose a game. Yes, cheating with undo. But I'm over 1,000 games and still no losses.

If I can get the deck for this Microsoft Freecell game, I'll get it into my flavor and go to work. The longest game I won took me well over 40 hours, but I got it.

Though, I admit, since there are a finite set of moves, it is *possible* that this is unsolvable. But I'll try. What the heck, all I lose is time spend watching Pawn Stars.

Re:I think it's solvable. (0)

Anonymous Coward | about 2 years ago | (#39660045)

Did you read tfa? They've exhausted the entire set of moves available. They are all not solutions. Thus it isn't solvable.

Re:I think it's solvable. (1)

canajin56 (660655) | about 2 years ago | (#39660681)

TFA says that out of 32,000 games that the original FreeCell can deal (it can't deal all 52! hands), all have been one by humans except ONE, and exhaustive testing shows that that last game has been exhaustively shown with 100% certainty to be unsolvable. Out of 100 million games with a less constrained dealer, only 1282 have not been solved by a human or machine. So using one of these unconstrained versions of FreeCell, you can probably assume that the odds of getting an unwinnable game are something like 0.00001%, so essentially you can always win a random game.

Re:I think it's solvable. (1)

Sancho (17056) | about 2 years ago | (#39661073)

Were those 100 million perfectly random, or was a random deck generator created which has good odds of creating a winnable game? It's pretty easy to generate basic unwinnable subsets of the lower board, and then all permutations with that subset will be unwinnable. There are more subtle unwinnable games, too.

Of course, 52! is a huge space. It would be interesting to see a formal analysis of the game.

Re:I think it's solvable. (1)

Turken (139591) | about 2 years ago | (#39662051)

Nice record. The kicker is when you have a streak like that going, and then some family member using your computer decides to try a game or three and loses for you.

After that happened to me a couple times, I realized how easy it was to just go into the system registry and "fix" their mistake, but at that point the game lost its challenge because I also realized that I lacked the willpower to keep from "fixing" my own errors as well.

Project Gutenberg (1)

ABadDog (28370) | about 2 years ago | (#39660439)

You kids need to get off my lawn....

Even if the Cunningham project doesn't meet some arbitrary criteria for the first internet crowdsourced project, there's always Project Gutenberg, started in 1971.

FreeCell on TV - The Office (0)

Anonymous Coward | about 2 years ago | (#39660531)

There is an early episode of "the office (US)" that shows the secretary playing FreeCell. I was able to get the number and her screen was a few moves in (not very good moves). It was then possible to finish and win the game.

linux versions are missing a key feature (2)

doom (14564) | about 2 years ago | (#39661919)

Just thought I'd mention that the linux versions of freecell are all missing a key feature that the Windows version had: it told you the numeric seed used to generate the hand, and let you type it in again later if you wanted to play the same hand.

The linux versions I've seen will let you restart the game from the beginning, but don't let you save it, and sharing the game with someone else isn't as easy as just sending a number.

Re:linux versions are missing a key feature (0)

Anonymous Coward | about 2 years ago | (#39669153)

You didn't look at KPatience? It does exactly that.

Can 5 free cells solve all FreeCell puzzles? (1)

bingbing (1148913) | about 2 years ago | (#39668021)

Can 5 free cells solve all FreeCell puzzles, just like 4 colors covers all maps?

Re:Can 5 free cells solve all FreeCell puzzles? (1)

Dr. Tom (23206) | about 2 years ago | (#39679723)

11982 can be solved with 5 free cells. I don't know about "all" of them. There are too many to check all. Certainly most.
That's the kind of thing you'd need a more sophisticated proof for, since brute-force is still too slow.
(patsolve can run with any number.)
Another interesting question is which games can be solved with NO free cells. #164, #892, #1012, #1081, and #1150
are the first 5 that can be. There are only 207 in the first 100,000 games (using MS numbering).

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...