CSC 427: Data Structures and Algorithm Analysis
Fall 2004

HW4: Lists and Skip-3 Solitaire

For this assignment, you are to write a C++ program that allows the user to play the Skip-3 solitaire game. In Skip-3, cards are dealt one at a time from a standard deck and placed in a single row. If the rank or suit of a card matches the rank or suit either 1 or 3 cards to its left, then that card (and any cards in the pile beneath it) can be moved on top of the matching card. For example, suppose the three of clubs, five of diamonds, nine of clubs, and jack of hearts are initially dealt. They would be placed in a row, in left-to-right order, as shown below.

3C 5D 9C JH

If the next card dealt is the three of hearts, then that card is placed to the right and is found to match the jack of hearts immediately to its left. Thus, the three of hearts can be moved on top of the jack of hearts, shortening the row of cards. The consolidation of these piles then allows the three of hearts to match with the three of clubs that is 3 cards to the left. Thus, the pile topped by the three of hearts can be moved on top of the three of clubs, shortening the row even further. Pictorially, the consolidation steps are:

3C 5D 9C JH 3H 3C 5D 9C 3H <-- after first consolidation 3H 5D 9C <-- after second consolidation

Here is another example:

5H 7C JH TD JC 5H JC JH TD <-- after first consolidation 5H JH TD <-- after second consolidation JH TD <-- after third consolidation

Note that the addition of a single card can enable several consolidation steps. In fact, a single consolidation can start a chain reaction in which many piles of cards, both to the left and right, are consolidated. The goal of the game is to end with as few piles of cards as possible. Theoretically, the game could end with a single pile of 52 cards, although that outcome is extremely unlikely. Also, note that only the top card in a pile needs to be stored, since the cards below it are never seen again. Thus, your class that models a row of piles should utilize a list of Cards, representing the tops of the piles. You will then need to use an iterator to step through the list and look for matches, and possibly use the insert and remove member functions to perfrom consolidations.

The game should start with a randomly shuffled deck (use the DeckOfCards class from HW2), and allow for cards to be dealt in a row. The entire row of cards should be displayed at the beginning of the game and after each step (either a consolidation of two piles or the addition of a new card to the row). If one or more consolidations are possible, the player should somehow be able to specify which consolidation to perform. If there are no possible consolidations, then a new card should be dealt and added to the end of the row.

The interface specification for this program is intentionally vague. You are to design a reasonable interface that makes it simple for the player to view and control the game. How you accomplish that is up to you.