Are games of solitaire always beatable?

[genericusrnme]

I was just playing some solitaire (the card game version) and realized that I come across the situation where the game becomes unbeatable quite a lot. This got me onto thinking about if we knew where every card was, would we be able to beat every game with a certain set of moves? Now, I tried conjouring up a counter example but after a few failed attempts I gave up and decided to turn to something a little more 'mathy'. The thing is though, I've never done this kind of thing before and I really have no idea where I would start off (or I'd even be able to.. I've got that 'mathematical maturity' the books always talk about and I know my way about set theory etc but idk if that's enough).
So my questions are as follows
1) Has this been done before? If so, links?
2) If no one knows of it being done before, could anyone point me in the right direction as to how to get started?

Thanks in advance!

 

[Office_Shredder]

Solitaire actually refers to a collection of card games that you play on your own. I assume that you are referring to the game titled Solitaire that comes with windows computers (and other OSs?). I think this game is called Klondike but don't quote me on it

Assuming that you have it deal 3 cards every time from the deck, then as long as all 7 face up cards to start are red, and the cards that get flipped over each time you deal 3 from the deck are red (you need 8 such cards) you can't do any moves at the start of the game

 

[mathman]

I use the Windows Solitaire with options: turn over one card at a time, continue turning over the pack as many times as you want, backtrack as far as you want to try different choices. This is the Windows 7 version.

It keeps statistics on how many time I win - it is running about 75%. When I don't win it means that there is no path to a solution.

 

[genericusrnme]

Solitaire actually refers to a collection of card games that you play on your own. I assume that you are referring to the game titled Solitaire that comes with windows computers (and other OSs?). I think this game is called Klondike but don't quote me on it

Assuming that you have it deal 3 cards every time from the deck, then as long as all 7 face up cards to start are red, and the cards that get flipped over each time you deal 3 from the deck are red (you need 8 such cards) you can't do any moves at the start of the game

I'm talking about the one where you just deal 1 card at a time, that's the way I learned to play it with irl cards.
I was aware that the 3 card version would have hiccups like this but I'm not too sure about the 1 card version, most of the situations I've tried to come up with can be resolved

I use the Windows Solitaire with options: turn over one card at a time, continue turning over the pack as many times as you want, backtrack as far as you want to try different choices. This is the Windows 7 version.

It keeps statistics on how many time I win - it is running about 75%. When I don't win it means that there is no path to a solution.

Are you sure it doesn't just mean that there is no path to a solution given the state the game is currently in rather than there is no path from the initial state to a solution?
Unless you tried every possible combination of moves, from the initial state, how can you be certain that you just went down a set of incorrect paths and that there isn't some other correct path?

Actually..
Whilst writing this I just came up with a counder example of my own;

In the initial state there are 24 cards in the stacks, take all four 6's and three 4's and put them at the bottom of all the stacks then put all the other cards with value <6 behind them, so there should be no cards of value <7 available to deal and since 4's can't go on top of 6's and because a higher value card can't go on a lower valued card there are no possible moves!

Thanks for the input guys!
I was secretly hoping that this wouldn't be true though and that I'd get to invent some fun little 'solitare' structure. Oh well (*subtle invitation to suggest either books or problems that are somewhat similar to this that I could have a go at*)

edit;
Another question that came to mind was, if there is at least one move is it always possible to win but I quickly came up with a counter example for that and then for two moves so another few questions came to mind, is there a minimum number of possible moves required such that if there are that many unique moves then the game is beatable or what are the necessary and sufficient conditions for the game to be beatable?
I have no idea why I'm taking such an interest in klondike (thanks for the heads up Office Shredder) as of late...

 

[phinds]

I use the Windows Solitaire with options: turn over one card at a time, continue turning over the pack as many times as you want, backtrack as far as you want to try different choices. This is the Windows 7 version.

It keeps statistics on how many time I win - it is running about 75%. When I don't win it means that there is no path to a solution.

Staggering hubris, unless you are joking.

 

[lugita15]

Staggering hubris, unless you are joking.

No, he's saying that by means of backtracking, he tried all possible solutions.

 

[Office_Shredder]

Another question that came to mind was, if there is at least one move is it always possible to win but I quickly came up with a counter example for that and then for two moves so another few questions came to mind, is there a minimum number of possible moves required such that if there are that many unique moves then the game is beatable or what are the necessary and sufficient conditions for the game to be beatable?

This is certainly worth thinking about. In free cell (another game that should be available on your computer, also a form of solitaire) there were originally only 32000 games available on windows... i.e. the computer did not randomly shuffle, but had a preloaded (possibly randomly constructed) collection of games that you could play. After extensive search by exhaustion it was discovered that exactly one of the games is unwinnable

http://en.wikipedia.org/wiki/FreeCell#Impossible_games

There are some examples of free cell hands that are clearly impossible, but it seems like almost every reasonable free cell game is winnable. I only mention this because if you're interested in just studying card game combinatorics free cell might be more exploitable due to its almost winnable nature, and the fact that you can pose additional questions such as: is every game winnable if you have 5 cells?

I question the ability of a human to try every single possible play and keep track of them to ensure all possibilities were covered, but I won't say it's impossible. This group

http://web.engr.oregonstate.edu/~afern/papers/solitaire.pdf

says that it should be possible to win a lot more than 3/4

 

[mathman]

Are you sure it doesn't just mean that there is no path to a solution given the state the game is currently in rather than there is no path from the initial state to a solution?
Unless you tried every possible combination of moves, from the initial state, how can you be certain that you just went down a set of incorrect paths and that there isn't some other correct path?

Using (unlimited) backtracking allows me to try all possible paths.

 

[phinds]

Using (unlimited) backtracking allows me to try all possible paths.

And you are saying that you have tried every possible path in every game you every played where you didn't win?

 

[mathman]

And you are saying that you have tried every possible path in every game you every played where you didn't win?

Most games but not all. In many cases, it can be deduced logically that there is no solution.

 

[genericusrnme]

This is certainly worth thinking about. In free cell (another game that should be available on your computer, also a form of solitaire) there were originally only 32000 games available on windows... i.e. the computer did not randomly shuffle, but had a preloaded (possibly randomly constructed) collection of games that you could play. After extensive search by exhaustion it was discovered that exactly one of the games is unwinnable

http://en.wikipedia.org/wiki/FreeCell#Impossible_games

There are some examples of free cell hands that are clearly impossible, but it seems like almost every reasonable free cell game is winnable. I only mention this because if you're interested in just studying card game combinatorics free cell might be more exploitable due to its almost winnable nature, and the fact that you can pose additional questions such as: is every game winnable if you have 5 cells?

I question the ability of a human to try every single possible play and keep track of them to ensure all possibilities were covered, but I won't say it's impossible. This group

http://web.engr.oregonstate.edu/~afern/papers/solitaire.pdf

says that it should be possible to win a lot more than 3/4

Wow

I've never really looked at free call before (along with spider solitare) but I may give it a look at now. I should ask, what mathematical tools and concepts should I have ready at my disposal?

I just briefly skimmed over the pdf you linked me too (I'm going to read it more thoroughly later on) and I see a lot of AI like stuff so I'm glad I took part in that online AI class stanford did earlier this year!
It looks very interesting though, I had no idea that solitare, of all games, would be so difficult as to be 'one of the embarrassments of applied mathematics'.

 

[mathman]

The solitaire games in Windows 7 appear to be preloaded. Too often I have found myself playing repeats.

 

[BillTurlock]

Solitaire, My Way

Solitaire, My Way rules:
Klondike Solitaire, played deal 3 (not one-at-a-time). Unlimited time, and unlimited times through the supply deck. No back-ups except for spasm correction. NO taking down from the top four stacks (which is possible in MS Solitaire).
Obviously, when all cards are face up—you win. It Can Not be otherwise.
My objective: To get all cards face-up, with the least number of cards in the four top stacks. Add the face values of the top four stacks, lowest score wins. It requires a different strategy, but one which will help you in a standard game, namely, don't be too anxious to put cards on on the top four stacks.
My best score, until today, was One (win with only one card (obviously an ace) up there). However, I just got a Perfect Game!
http://www.flickr.com/photos/66766379@N02/8702964457/
http://tinyurl.com/cqvh3zk
Woo Hoo!
Bill Turlock