It's time to play! Most people are familiar with the puzzle game "Tag". To formalize it, “Tag” is a two-dimensional 4x4 field, in this field there are not 16, but 15 squares, that is, one slot remains empty. Each of the squares is numbered and can move horizontally or vertically within the field (if, of course, there is room to move). The goal is to place the numbers in order, from 1 to 15 from left to right from top to bottom. Then the empty space will be in the lower right corner. The movement of any tile (or several) is a “step” in this game space. The combination shown in the picture above is already stacked, but note that 12 or 15 tiles can be pushed into the empty space. The rules state that a tile cannot be moved diagonally or removed from the playing board. There are actually a lot of configurations to start the game (you can count how many exactly), but for the sake of simplicity, let's arrange the tiles in order from largest to smallest and leave an empty space in the lower right corner of the board. The only thing is, let's swap 1 and 2 so that the puzzle is solvable. Now go to your workbench's ~/ directory, then /pset3/fifteen and open fifteen.c . It contains the code for the game engine. The task is to add code to the game. But first, let's compile our “engine” (you probably already know how to do this). Despite the fact that the game is not finished, you can launch the application. It will be more convenient to run it in a larger than usual terminal window, which can be opened by clicking on the green plus (+) next to one of the code tabs and selecting New Terminal . Or you can open the terminal window in full screen by clicking on the Maximize icon in the upper right corner of the console. You see that some things work somehow. But in fact, most of the game has not yet been written. And here - get ready - is your exit!
Study
Study the code and comments of fifteen.c and then answer the questions below:
Apart from a 4x4 board, what field size does our engine allow?
What data structure is the game field?
What function is called to greet the player at the start of the game?
What features do you need to implement?
Note: If you want auto-check to tell you if you answered the questions correctly, next to the file fifteen.c, find the file fifteen.txt and write down the answers to these questions in it.
Implementation
Well, let's start implementing the game. Remember, we are moving in tiny steps, don’t try to do everything at once. Instead, let's implement features one at a time and make sure they work before moving forward. In particular, we suggest that you implement the game functions in the following order: init (initialization), draw (drawing), move (take a step), won (win). Design decisions (such as how much space to insert between our number tiles) are yours. The playing field should look something like this: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Once again, please note that in the starting position, 1 and 2 are located in the reverse order (this applies to the classic 4x4 field if the number of tiles is odd). If the number of tiles is even and the field is 3x3, there is no need to swap the two “lowest” tiles. 8 7 6 5 4 3 2 1 _ To test your implementation of “Tag,” you need to try playing them (don’t forget, you can exit the program before its natural completion by pressing the key combination crtl+c). Make sure the program will work if incorrect numbers are entered. And remember that just as you automated the input into find, you can automate the “walkthrough” of the game. In fact, in the ~cs50/pset3 folder there are files 3x3.txt and 4x4.txt , which contain all the sequences of steps for winning on 3x3 and 4x4 fields. To test the program, for example, using the first of the files, run the following command: ./fifteen 3 < ~cs50/pset3/3x3.txt Set up the argument you need to speed up the animation. And in general, if you want, you can always change the game. To have fun with "ANSI escape sequences" including color. Take a look at our implementation of clear and check out http://isthe.com/chongo/tech/comp/ansi_escapes.html to learn new tricks. If you wish, write your own functions or change the prototypes of the functions that we wrote. The only limitation is that you do not change the logic of the main function, otherwise we will not be able to apply some automatic tests to it to confirm that your program is working correctly. In particular, main must return 0 if and only if the user solved the puzzle. Non-zero values must be returned for all error options. If any errors occur, write to us. Well, if you want to play with the implementation of the application prepared by the CS50 assistants, run the following command: ~cs50/pset3/fifteen If you are interested in seeing a cooler implementation, with automatic puzzle solving, check out the “Hacker” version of the program: ~cs50/hacker3/fifteen Instead of entering a number in the game window, type the word GOD. Great, isn't it? If you want to check the correctness of your program officially with check50, note that check50 assumes that the empty space of the playfield is filled with 0; if you chose a different value, replace it with zero for correct verification. Also, check50 assumes that you are indexing the board fields in the order [row] [column], not board [column] [row]. check50 2015.fall.pset3.fifteen fifteen.c
Learn more about the implementation of Fifteen game functions
init (initialization)
draw
move (take a step)
won (win)
init
In this function we introduce the playing field. To do this, we use a two-dimensional array of integers. The array dimension is MAX x MAX, where MAX is a constant indicating the maximum number of tiles that can fit in a row or column of a field. Thus, we need to define the variable int board[MAX][MAX] However, remember that the size of the playing field is determined by the user. Therefore, we need to define a variable that would indicate the board size that the user must enter. This is int d . where d is the board dimension, d <= MAX. However, in C you can't change the size of an array, so you have to settle for the maximum size. In init you need to put the values on the board. Read more about two-dimensional arrays if you haven't worked with them yet. In short, they have two indices, the first denotes the row number, the second the column number. For our problem, we start with the maximum number and end in the case of d = 3 (“Eights”) with one and an empty corner. If we still have “Tag”, then we swap 1 and 2. What to do with the empty space? Our array consists of integers, so the void must be filled with some integer. Therefore, you must choose some integer to initialize the empty tile (or, in the case of a physical game, the absence of a tile). Loops can be used to initialize the game board and fill it with a starting set of tiles. We loop through indices i and j, where board[i][j] is a tile that is located in row number i and column number j. We fill the board in descending order. If the number of tiles (without empty ones) is odd, swap 1 and 2.
draw
This function should print the current state of the playfield. Remember that we can have values with one or two digits, so for beautiful formatting after numbers 1-9 the function should print a space ( #s ). This can be done using the %2d placeholder . printf (“%2d”, board[i][j]); Also don't forget about the empty cell. Select the character that will represent it (in our example, this is an underscore). The draw function should draw this character as soon as you hit an empty cell. So our loop would be something like this: for каждой строки for каждого element строки print meaning и пробел print новую строку Remember that the order in which the draw function draws the tiles to the screen should reflect the order in which they are in the array defined in the init function .
move
Once you have initialized the playing field and drawn the initial tile positions, you need to allow the user to edit the position of the tiles, that is, make movements. So in Fifteen.c the program takes output from the user, builds the game board and then calls the move function and tells it which tile he wants to move. Be careful: you are applying the function specifically to the number on the tile, and not to its position on the board (in the array). So you need to find the actual position of the tile. Additionally, you should only allow the user to move the tile when possible. In the picture above, we can only move tiles number 2, 5 and 8. How to determine this? By the value of an empty tile. So the move function works something like this:
Accepts the tile number that the user wants to move
Looks for the position in the array (on the playing field) of this tile
Remembers the position of an empty tile
If an empty tile is adjacent to one that the user wants to move, they are swapped in the array.
won
This function checks if the game has ended after each user step. It returns true if the tiles are in the correct order (including the position of the empty tile in the lower right corner). In this case, the program can be terminated. If the tiles are still scattered, the function returns false and passes the reins to the move function . How to organize an inspection? As in the case of initializing and drawing the board - using two nested for loops. For example, you can set a condition that each subsequent number in the array must be greater than the previous one. Notice what value is written in the empty tile. Or another way - use a counter to make sure that all the tiles are in place, if you can handle it and write the formula to get it. We wish you good luck in your experiments!
How to validate your code and get marks
Attention! If it is important for you to check only the correctness of tasks, then use cs50check. If you want to get grades on the edx platform, follow the procedure described below. Keep in mind, this procedure uses the same cs50check to check tasks. The only difference is that it remembers the results and calculates the overall score.
Near the top left corner of the CS50 IDE , where its file browser is located (not in the terminal window), right-click on your pset3 directory and click Download . You should see that the browser has downloaded the pset3.tar.gz archive .
In a separate window or tab, log in to CS50 Submit
Click on the Submit icon in the upper left corner of the screen
In the list of folders on the left, click on the Problem Set 3 directory , then click on the Upload New Submission button. It's on the right.
On the screen that appears, click on the Add files ... button. A window for selecting files from your computer will open.
Navigate to the folder where you saved pset3.tar.gz. It's most likely located in your Downloads folder or wherever your browser puts files by default. When you find pset3.tar.gz , click on it once to select it, then click Open .
Click Start upload . Your files will be uploaded to CS50 servers .
On the screen that appears, you should see the No File Selected window . If you move your mouse cursor to the left, you will see a list of downloaded files. To confirm, click on each of them. If you are unsure about something, you can re-upload the files by repeating the same steps. You can do this as many times as you like until the end of 2016.
It's time to play! Most people are familiar with the puzzle game "Tag". To formalize it, “Tag” is a two-dimensional 4x4 field, in this field there are not 16, but 15 squares, that is, one slot remains empty. Each of the squares is numbered and can move horizontally or vertically within the field (if, of course, there is room to move). The goal is to place the numbers in order, from 1 to 15 from left to right from top to bottom. Then the empty space will be in the lower right corner. The movement of any tile (or several) is a “step” in this game space. The combination shown in the picture above is already stacked, but note that 12 or 15 tiles can be pushed into the empty space. The rules state that a tile cannot be moved diagonally or removed from the playing board. There are actually a lot of configurations to start the game (you can count how many exactly), but for the sake of simplicity, let's arrange the tiles in order from largest to smallest and leave an empty space in the lower right corner of the board. The only thing is, let's swap 1 and 2 so that the puzzle is solvable. 
Now go to your workbench's ~/ directory, then /pset3/fifteen and open fifteen.c . It contains the code for the game engine. The task is to add code to the game. But first, let's compile our “engine” (you probably already know how to do this). Despite the fact that the game is not finished, you can launch the application. It will be more convenient to run it in a larger than usual terminal window, which can be opened by clicking on the green plus (+) next to one of the code tabs and selecting New Terminal . Or you can open the terminal window in full screen by clicking on the Maximize icon in the upper right corner of the console. You see that some things work somehow. But in fact, most of the game has not yet been written. And here - get ready - is your exit!
Read more about two-dimensional arrays if you haven't worked with them yet. In short, they have two indices, the first denotes the row number, the second the column number. For our problem, we start with the maximum number and end in the case of d = 3 (“Eights”) with one and an empty corner. If we still have “Tag”, then we swap 1 and 2. What to do with the empty space? Our array consists of integers, so the void must be filled with some integer. Therefore, you must choose some integer to initialize the empty tile (or, in the case of a physical game, the absence of a tile). Loops can be used to initialize the game board and fill it with a starting set of tiles. We loop through indices i and j, where board[i][j] is a tile that is located in row number i and column number j. We fill the board in descending order. If the number of tiles (without empty ones) is odd, swap 1 and 2.
In the picture above, we can only move tiles number 2, 5 and 8. How to determine this? By the value of an empty tile. So the move function works something like this:
GO TO FULL VERSION