# Background

## Goals

This project is to combine all of the materials that you have learned in this class: lists, recursion, HOF's, lambda, sequential programming. Design is also a factor in this, as it is larger than previous projects.

## Restrictions

In this project, everything is fair game. This is also a partner project, meaning, if you choose to, you can work with ONE other person in the class.

## Project Overview

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. An online version with similar rules to ours can be found at World of Solitaire.

 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:

• Moves from tableau to foundation
The top card of any tableau stack is eligible to be moved to a foundation stack. An ace is the only card that may be moved to an empty foundation stack. Foundation stacks are built up in order, one stack for each suit, so a 2 may be placed atop the A, the 3 on the 2, and so on.
• Moves from one tableau stack to another
Any face-up card in the tableau, together with the cards on top of it, may be moved onto a card of the opposite color and next lower rank that's at the top of a tableau stack. A king, also together with the cards on top of it, is the only card that can be moved to an empty tableau stack. When a face-down card is exposed by such a move, it is turned face up.

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:

• foundations, which returns a list of the four foundation stacks;
• tableau, which returns a list of the seven tableau stacks;
• face-up, which returns the list of face-up cards in the given stack with the top of the stack first in the list; and
• face-down, which returns the list of face-down cards in the given stack.
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:
• possible-moves, which should return a list of all possible moves one can make with the given board. You may choose the representation of a move; however, the comments in your code should clearly document how a move is represented. The version of possible-moves supplied in the framework always returns an empty list. You should be able to move a tableau stack to another tableau stack or a card from a tableau stack to the foundation. It is not necessary to be able to move a card from the foundation back to the tableau.
• choice-from, which chooses a move from among those in a given list of moves. The version of choice-from provided in the framework code merely presents a list of moves to the user and asks for a selection. You should change the representation to a more user-friendly method of displaying the list of moves. How you want to do it is up to you, but it should be obvious to the user what s/he is going to type to select and where they are moving from/to. You should also improve this in one of the following ways:
• completely error-check the user's input to ensure that it will not cause the program to crash, and continue to ask for a selection as long as the user responds with nonsense; or
• highlight obviously useful moves, for example, those that allow a face-down card to be exposed.
(You don't need to do both.)
• updated, which returns the result of making the chosen move on the given board. The version of updated supplied in the framework returns the board unchanged.
• true-for-all?, which takes a function and an argument. It returns a boolean that checks whether the function is true for all elements in the 2nd argument.

### 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 file named yukon-tests.scm, include tests that exercise your program completely. Use the testing framework in earlier projects. 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.scm 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.

## Due Date

This project is due one week from now, on August 13th, 11:59 pm. You have 3 slip days total between all projects but use them wisely. To submit the project type "submit finalproject" from unix. The filename should be called yukon.scm. Along with the file itself, you should include a test file, called yukon-tests.scm. This should be in the same format that you used in projects 1 & 2 & 3 (using the add-test-case framework).