share
ArqadeCan every game of Solitaire be solved?
[+15] [3] Ivo Flipse
[2010-07-07 20:54:19]
[ handheld solitaire ]
[ http://gaming.stackexchange.com/questions/348] [DELETED]

I play a lot of Solitaire games on my Android phone and love to keep an eye out for the statistics.

Given that the Solitaire version let's you restart the game endlessly, I usually play until I solve it. But I never managed to solve more than 80% of the games played (1000+).

So now I wonder, is every Solitaire game solvable?

Note: I realize this is a borderline topic. If you think it should be off-topic, go post it on Meta - Ivo Flipse
(1) I presume you mean Klondike solitaire? - McKay
"go post it on Meta" can be read as harsh :) - Juan Manuel
Excuse my non-native English directness ;-) Perhaps I should have said discuss or open a question on Meta - Ivo Flipse
(3) This almost belongs on Stack Overflow - Earlz
[+17] [2010-07-07 20:55:49] McKay [ACCEPTED]

No. Example: If all of your cards face up on the board are red, and the cards that come up every third card are also red, and none of them are aces. You lose. Do not pass go, do not collect $200.


(1) As a fact, I have come up with almost this exact setup on the computer version of Solitaire (but one card was black, just completely impossible to place anywhere). - Grace Note
Yeah, there's other variations on this. But I've played several games, where no cards ever got moved. - McKay
(2) Another example that just happened to me: All cards shown are even. - McKay
en.wikipedia.org/wiki/Klondike_%28solitaire%29#Odds_of_winning - Margaret
1
[+6] [2010-07-21 14:51:04] Jakub Šturc

There is very interesting reading at wikipedia [1] about this topic.

For a "standard" game of Klondike (of the form: Draw 3, Re-Deal Infinite, Win 52) the number of solvable games (assuming all cards are known) is between 82-91.5%.

[1] http://en.wikipedia.org/wiki/Klondike_solitaire#Odds_of_winning

(3) Then I was actually doing a great job nearing it to 80% - Ivo Flipse
2
[+2] [2010-07-07 20:58:54] Oak

Solitaire is a game that precedes its computer version, and that means that all the cards are truly shuffled, without the computer peeking in to verify the game is solvable.

And like McKay mentioned, with a random shuffle you can definitely end up with an unsolvable game.

I'm sure it is possible to design a Solitaire variant in which each game is solvable, though.


(1) Would need a LOT of calculation, basically the computer would have to play through an entire game to make sure there's a solution, unless there's some kind of algorithm I'm missing. - Arda Xi
@Arda, there are some conditions that could be easily tested - for example, a card other than a King can be played on only three other cards in the deck (the next-lowest card in its suit, or the foundation for an Ace, and the next-higher cards of the opposite color). If all three of those cards are face down below that card on a pile, the game isn't winnable. Unfortunately I think that's a small percentage, and testing for other conditions might require a ton of recursion. - Dave DuPlantis
@DaveDuPlantis True, but you will have to test for all of those conditions that exist. I'm not sure whether we even know all of them. - Arda Xi
@Arda - that's true, that's what I was thinking with respect to recursion. Without some way to demonstrate that any given position is unwinnable, you'd essentially have to play a certain series of cards until you were blocked, back up to the last decision point, and repeat ... it's an intriguing concept, but I've never seen a solitaire program do that. - Dave DuPlantis
3