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$
    – Ross Millikan
    Commented May 8, 2014 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
    Commented May 10, 2014 at 3:50
  • $\begingroup$ Solitaire: Man Versus Machine (2005) $\endgroup$
    – Rodrigo de Azevedo
    Commented Oct 21, 2016 at 11:42

1 Answer 1

Reset to default
2
+150
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .