Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves?

Description of the game:

Two decks of cards (36 pieces each) are connected and shuffled, and then they are laid out in 8 piles of 9 cards each. Possible work only with the top cards in each of the piles, namely, transfer one or several consecutive cards of a lower value to a card of a larger one (suits are not taken into account). If there are 9 cards in one of the piles in the correct order (ace-king-queen-jack-10-9-8-7-6), then this set is removed. If all the cards are removed from one pile, it can still be used and any card can be placed on top


There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics to search more promising moves first.

The eight queens puzzle is the typical example of backtracking in a much simpler setting, the cited page has a sample Pascal program (readable enough for any C-savy person). Dijkstra wrote a highly detailed discussion of the program, see his "EWD316: A Short Introduction to the Art of Programming".


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.