CS 3 project choice 3
Yukon solitaire

Background

The solitaire game of Yukon is played as follows. First, the deck of 52 cards is dealed into seven stacks as shown in the diagram below. This is called the tableau. The leftmost stack contains one card, face up. The next stack contains one face-down card, with five face-up cards on it, arranged so their suits and ranks are visible. The third stack contains two face-down cards and five face-up cards; the fourth stack contains three face-down cards and five face-up cards; and so on.







U





D
U
U
U
U
U




D
D
U
U
U
U
U



D
D
D
U
U
U
U
U


D
D
D
D
U
U
U
U
U

D
D
D
D
D
U
U
U
U
U
D
D
D
D
D
D
U
U
U
U
U


"U" means face up,
"D" means face down.
The physical top of each stack is listed at the bottom of the corresponding column of cards in the diagram.


There are also four foundation stacks, one for each suit, that are initially empty.

These are generally placed above the tableau.

There are two kinds of moves:

The game is won when all 52 cards are moved to the foundation. More details are available on the web (Google "yukon solitaire" for information).

Here is a segment from an actual game.

Tableau (stack top is the bottom card in each column)






7♣






Q♠
A
6♣
8
7






6
2
K♠
3♣
3






K♣
10♠
A♣
4♠
10






A
A♠
9♣
2♠
Q






9
7
3
2
5






J
4
8♣
4♣
3♠



"—" means a face-down card.
Possible moves from one tableau stack to another: 6 to 7♣, 2 to 3♠, 4♠ to 5, 9♣ to 10, 2♠ to 3, 2 to 3♠, 4♣ to 5. When a card moves, all cards atop it on the tableau stack also move.

No moves may be made from the tableau to a foundation stack.

We choose to move the 9♣ (along with the 2♠ and Q) to the 10. This frees up the A♠, which we move to a foundation stack, and the A, which we also move. Finally, we turn up the exposed face-down card formerly under the A. Here's the result.

Foundation
A♠ A
Tableau (stack top is the bottom card in each column)






7♣






Q♠
A
6♣
8
7






6
2
K♠
3♣
3






K♣
10♠
A♣
4♠
10 9♣
2♠
Q






Q♣






9
7
3
2
5






J
4
8♣
4♣
3♠




Possible moves from one tableau stack to another: 6 to 7♣, 2 to 3♠, 4♠ to 5, 2♠ to 3, 2 to 3♠, J to Q♣, 4♣ to 5.

No moves may be made from the tableau to a foundation stack (the 2 and 2♠ would have to be on top of a stack to be eligible to move to a foundation).

Now we choose to move the J atop the Q♣. Again, the cards on top of the J get moved also. This exposes a face-down card, which we turn up. We then move the 6 and the cards on top of it to the 7♣. This also exposes a face-down card. Here's the result.

Foundation
A♠ A
Tableau (stack top is the bottom card in each column)





7♣
6
2
K♠
3♣
3





Q♠
A
6♣
8
7





10





K♣
10♠
A♣
4♠
10 9♣
2♠
Q





Q♣
J
4
8♣
4♣
3♠





9
7
3
2
5





9♠
Possible moves from one tableau stack to another: 2 to 3♠, 8 to 9♠, 4♠ to 5, 9♣ to 10, 2♠ to 3, 4♣ to 5, 2 to 3♠, 9♠ to 10.

After a few more moves, the game appears as follows.

Foundation
A♠ A A♣
Tableau (stack top is the bottom card in each column)




7♣
6




Q♠
A
6♣
8
7




5♠
4
8♣
4♣
3♠
2
K♠
3♣
3




K♣
Q
J♠
10
9♠




Q♣
J
10♠
9
7
3
2
5
4♠




J♣
10
9♣
2♠




6


Possible moves from one tableau stack to another: A to 2♠, 8 to 9♠, 5♠ to either red 6, 3 to 4♠, 2♠ to 3.

The 2♠ may also move to the foundation ♠ pile.

First we move the 2♠ to the A♠ in the foundation. Then we move the 5♠ to the 6, creating an empty stack to which any K may be moved. We move the K♣ to expose a face-down card. Here's the board that results.

Foundation (only the top card in each stack is shown)
2♠ A A♣
Tableau (stack top is the bottom card in each column)




7♣
6
5♠
4
8♣
4♣
3♠
2
K♠
3♣
3




Q♠
A
6♣
8
7




K♣
Q
J♠
10
9♠




5




Q♣
J
10♠
9
7
3
2
5
4♠




J♣
10
9♣




6
Possible moves from one tableau stack to another: 5♠ to 6, 4♣ to 5, 3 to 4♠, 8 to either black 9, 4♠ to 5.

We went on to lose this game.

Yukon isn't all that hard to win. One book, The Complete Book of Solitaire and Patience Games, by A.H. Morehead and G. Mott-Smith, estimates the odds of winning as 1 in 4. One former CS3 instructor claims to have done somewhat better, winning around 42% of the time.

Problem

You are to complete a program to play Yukon solitaire. A framework for this program appears here and in the file ~cs3/public_html/programs/yukon.fw.scm. It specifies the representation of a board—you don't get to change this—and provides relevant access procedures:

It also provides various procedures for shuffling a deck of cards, building the initial board, and printing the board. It includes calls to several procedures that you are to write: Finally, the framework code includes an incomplete test for a win that uses the true-for-all? procedure you wrote in an earlier lab activity.

Miscellaneous requirements and suggestions

You are not to change the representation of a board or any of the framework code except for the three procedures possible-moves, choice-from, and updated described above. Respect the data abstractions set up for boards and cards by using the access procedures provided. (You will need to provide extra board operations to implement the updated procedure.) Your code should not include complicated cond expressions that rely heavily on there being only four foundation stacks or only seven tableau stacks. Use recursion or higher-order procedures to code more general (and shorter) procedures.

Put your completed program in a file named yukon.scm in a directory named finalproject. In a file named yukon.tests, include tests that exercise your program completely. (Also provide the file partners.readme if you're working in partnership.) In particular, one of your tests should include a winning game. Test your procedures individually as well as in combination, and include the results of these tests in your yukon.tests file.

This project breaks down naturally into two big pieces—the generation of moves and the updating of the board—plus the improved choice-from. In our solution, each of these was a couple of pages of code. Each big piece is a candidate for the second or third checkoff. A procedure that's not required but is likely to prove useful for debugging your updated procedure is a board consistency checker.