From UBC Wiki

Klondike Solitaire

Authors: Regina Adshade Moore & Sam MacKinnon

What is the problem?

A 52 card deck is randomly shuffled and dealt into piles (lists) in the order that a player would normally deal the cards. The specifications for the order when dealing out the piles at the start of the game and the rules of the game can be found here. We will be implementing the draw-1 version of the game where, when dealing the remainder of the deck, the player may turn only one card at a time. The program will systematically look through the “visible” cards and choose a move to make. It will continue making legal moves in the game until it has been solved or there are no moves left to make. It is important to note that not all games will be solvable.


Legal Moves are:

  • Moving a card or stack of cards in the tableau from one pile in the onto another card which is one card higher and a different colour
  • Moving a single card from the deck onto another card in the tableau which is one card higher and a different colour
  • Moving a single card to the foundation pile with the same suit if the top card on that pile is one card lower
  • Moving a king to an empty space on the tableau

How To Play

Start a game with a randomly shuffled deck (may or may not be solvable):
?- start.

Start a solvable game (using a pre-determined deck order):
?- start_solvable.

Make the next available move:
?- move.

Extra queries to try (for those curious)

To see face down cards in rows:
?- row(R,down,X).
where "R" is the row number, and "X" is a list of cards.

To see the cards remaining in the extra-cards deck:
?- deck(X).
where "X" is a list of cards.

What is the something extra?

Our something extra is to render the game-space and show the steps taken to complete the game. After the deck is shuffled and dealt, a user will be able to see the cards dealt into their piles (seen to the right). The deck and the number of cards it contains are shown at the top, followed by the 4 foundations piles showing the number of cards in each, and then the 7 piles that make up the tableau are rendered sideways, stacked from left to right. The user can then query "move." to trigger the program making it's next move. The new layout will then be shown to the user and they will continue making moves until there are no more moves to make (lose) or the game is completed (win).

What did we learn from doing this?

In creating this logical program, we gained experience using lists and learned about dynamically updating lists and moving "objects" from one list to another. We also learned how to write blocks of text to the output, which can be used to created simple text-based visualizations.

Logic programming worked well for finding a possible next move to make in the game. It succeeded in recursively looking through the available cards and determining whether or not a potential move was legal. As we limited the only possible in-game query to a simple "move.", the onus on finding a move is completely on prolog, which proves that the program is solving the randomly-generated games logically.

We have tested our program by running through several games and ensuring that every game either ends with a win or no possible moves. The fact that it is not object-oriented made the task of moving cards somewhat more difficult as it was less suitable for dynamically moving items from one list to another. In order to build a game that progresses step-by-step and re-renders between steps, we needed to dynamically change the game's state - something that Prolog does not seem to be naturally suited for. That said, we got around this issue using retractall/1 and assert/1 predicates to remake lists after each move.

Prolog was also not ideal for rendering the gamespace onto the screen because stacks of cards had to be printed from left to right instead of the usual top to bottom. Overall, even though it may not be the most suitable way of programming this, our program was able to complete the task given to it, and to fulfill all of our expectations.