6
$\begingroup$

Is there a fairly straightforward procedure for determining if a given game of Solitaire (say Klondike) is solvable?

One of my students would like to write a Solitaire game and give an "always winnable" option. It is possible to take a won game and make random plays backwards to create a solvable game.

But my question is: Is there a test for seeing if a game is solvable that can be readily resolved by examining the state of the game?

$\endgroup$
3
  • 1
    $\begingroup$ This will vary much between solitaire games. For clock solitaire you can look for cycles that will block you. For Klondike, I suspect you can find patterns that prove it unwinnable, but the lack of those patterns will not prove it winnable. Another option is to write a program that plays the game. If it wins, present the game. Otherwise, generate another one. $\endgroup$ May 8 '14 at 15:48
  • 1
    $\begingroup$ For making sure it is "always winnable", the most obvious approach is to generate it in reverse - begin in the solved state, and work backwards. I'd expect that the set of solvable games is much smaller than the set of all possible games, so randomly generating and then testing the games may be too slow. $\endgroup$
    – Glen O
    May 10 '14 at 3:50
  • $\begingroup$ Solitaire: Man Versus Machine (2005) $\endgroup$ Oct 21 '16 at 11:42
2
+150
$\begingroup$

Perhaps we can start pruning the search space by identifying characteristics of unwinnable games and searching for those.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.