Solitaire

This coursework implements a game of solitaire.

Solitaire, or Patience, is a name given to a single-player game, usually a game played with a pack of cards. The game originated in Europe in around 1800, and numerous variations have been developed since.

During this coursework, you will write Python program to simulate a particular variation of solitaire.

The game works as follows. When played as a tabletop game, we start with a standard 52-card

deck, but only the numerical cards 1, 2, 3, 4, 5, 6, 7, 8, 9 are dealt – the court cards (King, Queen Jack) are omitted. The suit of the cards ( ,  , , ) plays no role in the game. As a result, there are 36 cards in play, four copies of each of the numbers 1–9. We’ll refer to the ace as 1, rather than A.

These cards are shu!ed and dealt into six stacks, which we’ll name A through F, each containing six cards, for example:

The aim of the game is to rearrange these cards into four complete stacks of nine ordered cards. Here, ‘ordered’ means in decreasing order going down the stack, i.e.

Here, the complete stacks are A, B, D and F, and stacks C and E are empty, but which are full and empty does not matter: the game is complete once there are four complete stacks. The challenge of the game is, of course, that only certain moves are permitted.

Moving single cards

The basic move in this solitaire varient is to move a card from the top of one stack, and place it onto another stack onto a number that is one larger. For example, in the following game, we could take the 1 card from stack E and move it onto the 2 card on stack C.

This is one of several moves we could have made: we could alternatively have moved the 2 in

stack C onto the 3 in stack A, the 3 in stack A onto the 4 in stack B, or the 7 in stack D onto the 8 of stack F.

Moving multiple cards

We can move more than one of the top cards on a stack at once, so long as those cards are ordered. For example, after our first move there is a pair of ordered cards at the top of stack C:

Just as before, we can move this pair to another stack if the top number in the destination stack   is one larger than the bottom card of those to be moved. In our game, the only stack that satisfies this is stack A, and we can move two cards from stack C to stack A:

You may have noticed that there is another pair of ordered cards, an 8 and a 9, at the top of stack F. We cannot move this pair currently, as there is nowhere for it to go. The rule for moving a 9  card (or multiple cards with 9 the largest) is that a 9 can only move into an empty stack.

We can however move the new stack of 1, 2, 3 formed on stack A onto stack B:

Our available moves are now a bit limited. While we can move the single 8 on stack F onto stack E, that doesn’t really help us progress, as it only reveals a 9. Perhaps the best move is to move the 7 on stack D onto stack A:

At this point, there are still moves we can make, but it’s di"cult to see how we can make enough cards to completely re-order them into four complete stacks as required. However, we are allowed to break the rules established above, in a very specific way.

Blocking moves

A single card at the top of a stack can be moved onto another stack, even if it is not one less than the number at the top of the destination stack. However, in that case, the moved card blocks the destination stack, here indicated with a black card. No further cards can be added to the destination stack. The only way to unblock the stack is to move the single blocking card at the top of the stack onto a valid location – that is, onto an empty stack, or onto a stack whose top  card is one greater than the card being moved. So, we can move the 1 from stack C to stack E.

This blocks stack E, really opens things up. We move the 3 from stack D to stack C, then the 2   from stack D to stack C. Then, we can then move the blocking 1 from stack E onto the 2 on the top of stack C, thus unblocking stack E, as follows:

We’ll now take a succession of steps:

· Move the top four cards from stack B (1, 2, 3, 4) onto stack D

· Move the top five cards from stack D (1, 2, 3, 4, 5) onto stack B · Move the top six cards from stack B (1, 2, 3, 4, 5, 6) onto stack A

 Move the top card from stack D, now a 1, onto stack F. This blocks stack F.  Move the top card from stack D, now a 8, onto stack E.

Our stacks now look like

Making a complete stack

We’ve now got a complete run of numbers of 1, 2, 3, 4, 5, 6, 7, 8, 9 at the top of stack A. Moving these to the empty stack D gives us the first complete stack that we are looking for. Here this

made by moving all nine cards to an empty stack all at once, but a complete stack can be formed over more than one move too.

For example, we could have made the complete stack by first moving the top two cards of stack E (9 and

8) to stack D, then the top seven cards of stack A to stack D.

Either way, once a complete stack is formed, the cards on it are turned over, and no cards can added to or removed from that stack for the rest of the game. (This is indicated here by the numbers begin removed from the cards.)

We now continue the game in the same way, except without being able to use stack D. Can you see how in seven further moves, we could both complete a second stack and both unblock stack F?

In terms of strategy, it is not always best to complete stacks as soon as possible, as this prevents that stack from being used again, constraining what is possible in future moves.

Python implementation

The game state

The most important part of this game is the representation of the game state — that is, which

cards are in which stacks, which stacks are blocked, and which are complete.

We represent the board state with a Python dictionary, (say, s), with three keys:

1.  s['blocked'] is a list of six boolean values, corresponding to the six columns A–F.

The value is True if the column is blocked by a card, or False if it is not.

2.  s['complete'] is a list of six boolean values, corresponding to the six columns A–F. The value is True if the column is completed, or False if it is not.

3.  s['stacks'] is a list of six lists of integers, corresponding to the cards in each stack. The lists are ordered from bottom up, so for example s['stacks'][1][0] is the bottom card on stack B.

could be created in Python with the statement:

s =  { 'blocked' : [ False , False , False , False , False , True], 'complete' :  [ False , False , False , True , False , False], 'stacks' :  [[2 , 7 , 4], [1 , 6 , 5 , 3], [7 , 8 , 9 , 4 , 3 , 2 , 1], [9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1], [5 , 7 , 6 , 4 , 9 , 8], [1 , 3 , 5 , 2 , 9 , 8 , 1]]}

For any one column, blocked and complete should never both be True. An empty stack is

indicated by the corresponding element of s['stacks'] being an empty list []. Note that even though the cards in the completed stack are not shown, the representation in  'stacks' shows   the nine cards in order. Thus, at all times, the lists in  'stacks' should together contain 36

elements, four of each of the digits.

Describing a move

The other key part of the game is the idea of a move. A move is uniquely described by the source stack, the destination stack, and the number of cards to be moved. We’ll represent a move as a

tuple of three integers,

The stacks are numbered from the left, starting with zero, so stack A is 0, stack B is 1 and so on. For example, the move (0,  4,  3) represents a move of three cards from stack A onto stack E, while a move (1,  2,  1) represents a move of one card from stack B onto stack C.

The assessed questions:

This coursework is worth 70 marks, and 70% of the course overall.

 30 marks are allocated for the correctness of the functions defined in problems 1–5. These will be tested in an automated way, as in the previous courseworks.

 15 additional marks are allocated based on number of perfect scores for core problems 1– 5.

 15 marks are allocated for problems 6–8.

 10 marks are for the quality of all the code.

Question 1: The initial state (6 marks)

Write a function initial_state that returns a dict corresponding to the game state at the start of a new game. The cards should be randomly shu!ed, allocated six to each stack, and no stack should be marked complete or blocked.

Question 2: Interpreting user input (6 marks)

At each turn, the user is asked for their input. The user should enter a string of two letters and an integer, e.g. AB3 to indicate that they wish to move three cards from stack A onto stack B, or FD1 to indicate that they wish to move one card from stack F onto stack D.

Write a function parse_move(input_str) which takes a string of this form and converts it

into a move tuple of the format described above, which it then returns. For example parse_move('AB3') should return the tuple (0,  1,  3).

If the number of cards is omitted, make it default to one, so that parse_move('FD') returns (5,  3,  1), corresponding to the move of a single card from stack F to stack D.

In this problem 2, you can assume that the string given by the user is a valid one, namely two letters in the range A–F, optionally followed by a positive integer.

Question 3: Determining if a move is valid (10 marks)

Write a function validate_move(state,  move) which returns True if the move move can be applied to a game in state state. You can assume that the parameter state is a dictionary corresponding to a valid game state (as described above), and that the parameter move is a tuple of three integers.

This function should contain all the logic for checking whether a move is valid, including all the rules described above on moving single cards, multiple cards, card ordering, blocking moves, blocked stacks and completed stacks. The function should also check for nonsensical moves (moving more cards than there are in the stack, moving to a nonexistent stack, etc.)

Question 4: Moving the cards (6 marks)

Write a function apply_move(state,  move) which takes a valid game state state and a

move tuple move. This function does not return anything, but modifies in-place the state

parameter passed to it to apply the move described by the move tuple. You can assume that

state is a valid game state and that move is a valid move that could be played in this state. This function should update the blocked and complete fields of the game state state, as well as    the stacks.

Question 5: Detecting a win (2 marks)

Write a function game_won(state) which takes a valid game state and returns True if the game has been won (that is, all cards are in a completed stack) and False otherwise.

The game

In the template, you are given the pre-written function play_game() which uses the five functions you have just written (initial_state, parse_move, validate_move,

apply_move, game_won) to simulate a game. You can now run the play_game function to play a working game. In questions 1–5, you must not change the existing play_game()

function.

The preceding five questions are the core questions of this coursework, together worth 30

marks. To recognise functions that are completely correct, a bonus is awarded for each question in questions 1–5 that scores full marks:

 1 bonus mark is awarded if one core question scores full marks

 3 bonus marks are awarded if two core questions score full marks  6 bonus marks are awarded if three core questions score full marks  10 bonus marks are awarded if four core questions score full marks 15 bonus marks are awarded if five core questions score full marks

(Because an important part of the game is that all of these functions work together correctly, the bonus grows more quickly as more questions score full marks.)

There are then three additional questions (6–8, worth 15 marks in total), and an assessment of code quality (10 marks), whose marks simply add to the 45 available in questions 1–5 to make a  total of 70.

Question 6: Handling errors (4 marks)

Modify your parse_move function from problem 2 so that raises a ValueError exception if:

 The string is not of the form of: two letters, optionally followed by a positive integer, or  The two starting letters are outside the range A–F

Modify the play_game function to catch this exception and immediately re-prompt the user for another move.

As a result of these modifications, your game should now not crash, regardless of what string the user types in.

Question 7: Resetting the game (2 marks)

Modify the parse_move function so that if the input string is R (or r), the function returns the integer 0, rather than the move tuple.

Modify the play_game function so that if parse_move returns this integer 0, then the game is reset (that is, initial_state is called and the game begins again).

Question 8: Undoing moves (9 marks)

Modify the parse_move function so that if the input string is U (or u), the function returns the integer -1, rather than the move tuple.

Modify the play_game function so that if parse_move returns this integer -1, then the most recent move is undone. By repeatedly typing U or u), the user should be able to undo as many    moves of the game as they like, until they end up back at the initial state. Ensure that the user

cannot undo beyond this point

Code quality (10 marks)

Ten marks are available for the quality of the code that you write in questions 1–8. This will be assessed by humans reading your code, and will be based on:

 Clarity and precision of docstrings for each function

 Clarity of comments elsewhere in the code that describe what the code is doing

 Code quality. Code should be clear, e"cient and easy to maintain. Marks maybe lost for

– Very ine"cient algorithms

– Code that is unnecessarily verbose or di"cult to understand