Well, this first requires knowing how a game can be won, which means we need to set forth the rules.

Now, I'm really rusty on Solitaire, as I don't play (matter of principles) but this is my best shot:

- There are several "play" piles, starting with one card, and built up to the right with one additional card per column. The rightmost column has several cards stacked. The topmost card of each pile is turned over and accessible; any others are not accessible.

- There are four "discard" piles, one for each suit; cards must be discarded in ascending order from Ace to King. None of these are accessible under the rules I know of.

- Remaining cards are placed in a "draw" pile, where the top card is drawn and either placed in play, discarded, or burned by leaving it face-up next to the draw pile. Only the most recently burned card is accessible.

- Cards can be stacked on any of the face-up play piles; a card can stack on another card IFF it is of an alternate color and is one denomination lower in value (e.g. 7 red stacks on 8 black).

- The game is won if all cards of all suits are discarded. The game is lost when the final draw card is drawn and no legal moves remain (or any remaining legal moves are nothing more than a stalemate and cannot lead the player to victory).


Now, where you get yourself in trouble is when you factor in player unpredictability. A guarantee that the game can be won is not the same as a guarantee that the game cannot be lost.

So let's assume an ideal, perfect player, one who will not make any mistakes. We'll take the easy road and assume also that this player does not practice card counting or other statistical analysis mechanisms for determining the "best" course of action when difficult decisions must be made.


Where to take it from here:
- Describe the exact conditions under which a game cannot be won. See if there are similar groups of conditions (e.g. the group of conditions some low-level card becomes trapped and cannot be discarded, leading to a dead state) and categorize them. List all the possible ways a game might be unwinnable (but note that this is not the same as listing every possible unwinnable game).

- Remove any of the conditions that require the player to make a mistake, given our perfect-player assumption from earlier.

- Now find some mathematical rules that stitch together these conditions. See if you can write some code that checks a shuffled deck and tests it for winnability.

- Once you can detect an unwinnable game, you have two choices. One is to brute-force (probably the best) and simply shuffle until you get a game that comes up winnable. The other option is to look again at your unwinnability patterns and invert them; see if there is a way to construct a deck that will never match an unwinnability rule. Then find the parts of such constructed decks that can be random, and the parts that must be consistent; shuffle the random parts, and leave the rest alone.

The easy brute force solution would be to shuffle the cards randomly and have the computer play the game to see if it is winnable. Do that until a winnable shuffle is found. It shouldn't take long -- I bet the computer could play hundreds of games in a second.

Brute force > crazy complex mathematics.

Quote:Original post by _goat
Brute force > crazy complex mathematics.

I'm glad you think so. Now find me the next Mersenne prime number. [wink]

Couldn't you, like, start with a finished game and then work backwards until you end up with a deck of cards?

Maybe that isn't as easy as I originally thought it would be.

Quote:Original post by smart_idiot
Couldn't you, like, start with a finished game and then work backwards until you end up with a deck of cards?

Maybe that isn't as easy as I originally thought it would be.

I think that might almost be as bad as brute force, because there's so many different places a card could have come from, depending on the so-many-places that so-many-cards are located.

Sure it might be harder and take longer to figure out algorithms for the first repliers approach, but it will leave you with a much more efficient way of doing things.

EDIT: If you're having trouble figuring out which conditions the game cannot be solved under, first try writing a program that randomly shuffles the cards. Have the computer play it and see if its win-able. If not, record the order of cards somewhere. When you have enough of them, analyze them to find out as much as you can about what's not valid

I would definately start with a finished game and play it backwards with random reversible moves (that is if the game was being played forward in time, the move would be legal). You are absolutely ensured to generate a shuffle that can lead to a winning game if the player makes the right decisions. And even if the player still doesn't make the anti-decisions of the shuffle algorithm, he/she may still win.

Quote:Original post by Mastaba
I would definately start with a finished game and play it backwards with random reversible moves (that is if the game was being played forward in time, the move would be legal). You are absolutely ensured to generate a shuffle that can lead to a winning game if the player makes the right decisions. And even if the player still doesn't make the anti-decisions of the shuffle algorithm, he/she may still win.

I disagree. You'd be very likely to end up with a biased set of possible dealings, and besides it's likely to be pretty difficult, as there would be far more choices going in that direction.

You already have the code for detecting valid moves. Simply write a simple A* algorithm implementation to solve the game and then you just have to excersize it a few times until you find a solvable one. Chances are you'll most often find a solvable one on the first few hits, taking under a second.

You'll ge the added bennefit of being able to have the computer play it by itself, for a screensaver type of effect.
JohnBolton has the rioght idea.

Yes, I understand there are multiple choices that could be made, but that's the point of choosing among them randomly. And because the moves are reversible, you will produce a well shuffled deck that can lead to a winnable game, and you complete the shuffle in O(N) time.