CS21 Lab 7: Fifteen Puzzle (TDD)

Design is due Saturday, November 2, before midnight

Full Implementation is due Saturday, November 9, before midnight

Goals

practice using Top-Down Design
write a complex program, with multiple functions, from scratch

Notes

Please read through the entire lab before starting!

This is a two-part lab, split over two weeks. For the first week you will focus on using top-down design to create the overall structure for the program. Once your proposed structure has been reviewed and approved by your professor or lab instructor, you will use bottom-up implementation to complete the full program.

You have two weeks to complete the full program. The first week is for the design, and the second for the full program. Your initial top-down design is due this Saturday (Nov 2) and the full implementation the following week (Nov 9). It is highly recommended that you submit your top-down design as soon as is possible so that we have time to give you feedback before you begin your full implementation. If you submit your design on the last day at midnight, it might take us a few days to get to it and send you comments.

fifteen puzzle

For this lab we will write a terminal-based version of the 15-puzzle:

---------------------
|    |  1 |  2 |  3 |
---------------------
|  4 |  5 |  6 |  7 |
---------------------
|  8 |  9 | 10 | 11 |
---------------------
| 12 | 13 | 14 | 15 |
---------------------

This is a sliding puzzle with tiles, where each tile has a number on it (1-15). The player’s task is to slide the tiles around on the grid until they are in order (1-15). There are 15 tiles in a 4x4 grid, so the one missing tile allows the others to slide horizontally and vertically.

Examples and Program Requirements

Here are a few examples of the running program, to help you see how things should work. Pay attention to how the game proceeds, and how input from the user is handled. For the examples shown, assume the "0" tile is the blank space/missing tile, so any tile next to the "0" can be moved.

You have some freedom in how you want your game to look. Here are our requirements for the full program:

the program should print out adequate instructions throughout the game (see examples)
the program starts with tiles in a random order
the user selects which tile to move with a simple number (1-15)
the user can quit at any time by entering -1
the program should handle invalid user input properly by re-asking for a value (see Example 2)
the program should handle invalid moves by not doing them (and telling the user it was an invalid move)
the game should end once the tiles are in order, with the blank space at the top left (see Example 1)
all output should be clean and easy to read

Top-Down Design Requirements

You should complete your top-down design (TDD), submit it (run handin21), and obtain feedback on it before beginning the full game implementation. Special procedures for this two-week lab:

create your design in design-fifteen.py first
after you have a working design (see below), run handin21 to turn it in! Then send a short email to tddf19@cs.swarthmore.edu, letting us know your design is done. We will take a look at each design and send you comments (usually within a day or two). If the design is incomplete or insufficient, you may be asked to submit a second design.
after you have the design done and have heard back from us, please copy the file to fifteen.py and implement the full game in fifteen.py (i.e., leave design-fifteen.py as is!)
```
cp design-fifteen.py fifteen.py
```
please ensure your design meets the following requirements before submitting:
- main() should be completely written, and should perform high-level steps without focusing on details
- main() should call the functions you create in your design, in the appropriate order, and with arguments that match parameters. Return values should be saved in main(), even if you don’t do anything with them yet.
- all functions should be stubbed out with parameters, a block comment, and a return statement. They don’t need to actually do anything yet, except possibly call other functions.
- if your function is meant to return something, you should return a dummy value of the appropriate type (e.g., return 0 for an int, or [1,2,3] for a list).
- your design should have several functions. Each function should be function worthy (i.e., not a trivial task) and also demonstrate encapsulation (one clearly defined purpose).
- the design should run without syntax errors (although it doesn’t play the game yet)

Your goal for the design is to completely write main(), such that it won’t need to change much as you implement and test all of the other functions.

Here is an example of a working fifteen top-down design. Your design doesn’t have to match this exactly, but should allow the user to input some choices, and should show the (fake) game progress.

Tips

Note: both of these tips are probably not needed until you implement the game in the second week of this lab, but are included here to help you with the design.

data structure

You are free to use your own data structure, but we suggest using a list-of-lists made up of integers, like this:

puzzle = [[10, 7, 6, 2], [5, 13, 1, 3], [9, 15, 0, 4], [8, 12, 14, 11]]

In the above, the first sublist ([10, 7, 6, 2]) would be the top row of the puzzle, the second sublist would be the second row, and so on.

If you choose to use this data structure, then any position in the puzzle can be accessed using the following row,column format:

>>> puzzle = [[10, 7, 6, 2], [5, 13, 1, 3], [9, 15, 0, 4], [8, 12, 14, 11]]
>>> row = 0
>>> col = 0
>>> print(puzzle[row][col])
10
>>> col = 1
>>> print(puzzle[row][col])
7
>>> col = 2
>>> print(puzzle[row][col])
6

finding a tile’s location

At some point in coding up this game you will probably want to find where a given tile is in the puzzle. For example, if the user wants to move the 4 tile in the above puzzle, you’ll need to know the 4 tile is in row 2, column 3, and the blank/0 tile is in row 2, column 2 (and they are neighbors!). A check of all tile locations, using nested for loops can help you accomplish this.

Here is the pseudo code for searching the puzzle data structure for a particular tile’s location (row and column):

for every row in the puzzle:
   for every column in the puzzle:
       if the number stored at this row,column is what we want:
          save the row number
          save the column number

After those loops are done, you should have the correct row and column number of the tile you are looking for.

Extra Challenge

This will not affect your grade or gain extra points. It is included just as an extra challenge, if you are interested (and have already finished the entire game).

You may know or have noticed, if we initially put the numbered tiles on the board in random locations, sometimes we get a puzzle that can’t be solved! That’s totally fine for this lab. However, if you want to guarantee that your puzzle can be solved, try moving the tiles from an initially ordered state (0 1 2 3 on the top row, etc) a certain number of times.

To do this, you’ll need to first figure out what moves are possible (which tiles have the blank tile as a neighbor), given the initial ordered board. Then just randomly choose and make a move from the list of possible moves.

If you repeat this 50-100 times (find all possible moves, pick one and make the move), you should have a good starting point puzzle that is still solvable.

Answer the Questionnaire

Please edit the Questions-07.txt file in your cs21/labs/07 directory and answer the questions in that file.

Once you’re done with that, run handin21 again.

Turning in your labs….

Remember to run handin21 to turn in your lab files! You may run handin21 as many times as you want. Each time it will turn in any new work. We recommend running handin21 after you complete each program or after you complete significant work on any one program.