Methods to produce solvable deals in Klondike solitaire?

Question

About 20% of Klondike-solitaire deals are not solvable. My question is what is the best method to get solvable deals?

I thought about two options:

1. Deal a random permutation, then try to solve it with a solver like Solvitaire, if failed, re-deal.
2. Start at the winning state, and play random reverse moves until getting to a starting state. (requires a tool that produce random reverse-moves).

Reference: The Winnability of Klondike Solitaire and Many Other Patience Games

Answer 1

There are several options, depending on what you mean by "produce", and what you mean by "solvable".

Thoughtful Klondike

The following three options assume "solvable" to be in the thoughtful variant (identity of the face-down cards is known).

1: Fetch winnable layouts from the Solvitaire experiment set

Solvitaire was ran on 1,000,000 randomly generated instances, from which a list of seeds for solvable instances was generated. You can view the raw data for that here.

2: Find any solvable deal using Solvitaire

As you mentioned, you could use Solvitaire to check if a layout was solvable. For deal-3 Klondike, you have approximately an 80% chance of the deal being solvable, and Solvitaire runs in <1 second in ~80% of instances. Therefore, you have approximately a 64% chance of finding a winnable instance quickly using Solvitaire and random layouts (with a Solvitaire timeout of 1000ms).

3: Random reversed moves

As you mentioned, you can generate random reversed moves to reach a winning state. The problem with this approach is that you can encounter "loops", where you return to the same layout, even if you disallow any move which undoes the move you just made.

Even without such "loops", you can still find perfectly solvable layouts which require millions of moves to solve.

I would suggest that option 2 is more viable.

Non-thoughtful Klondike

If you don't know the identity of the face-down cards, the definition of "solvable" is slightly challenging. Here are some interpretations, and their solutions:

• A winning sequence of moves exists, but you may need infinate "undo" actions to win.
  Solution: this is effectively the thoughtful variant, chose option 1 or 2 from above.
• Undo actions aren't allowed, and any choice of the face-down card to turn face-up will win.
  Solution: This was my Master's project at Uni. I couldn't figure out a static layout to do this, but I managed to dynamically generate layouts. I achieved this for deal-1 Klondike here - any choice of the face-down card provides a winning sequence of moves. Deal-3 proved more challenging, and although I created something similar to the deal-1 variant, my difficulty in creating an effective AI for non-thoughtful deal-3 Klondike prevented me from proving that it can always be won.