Game of Fifteen - A Sliding Puzzle Game

Question

Update: I addressed the changes and created an updated post.

I'm reviewing C by working through the edX CS50 problem sets. This task was to implement Game of Fifteen aka 15 Puzzle. Project details here.

Implemented as an interactive console game. The board is initialized with "tiles" as descending values with the objective being to reorder as ascending by swapping the empty tile (represented as _) with adjacent tiles. Valid movements are similar to a rook in chess (can't move diagonal) but can only swap tiles that are touching. Here's a demo:

Note that there's a dependency on CS50 Library.

---

I'd really appreciate feedback; the good the bad and the ugly. I have a few things in mind:

• I'd like to add unit tests but I don't think it's possible without getting rid of all the global variables. Advice on how to make things more testable?
• I'm thinking the file is probably too big. How might you recommend splitting things up into other files? Part of the reluctance to do so was related to the confines of the CS50 project and getting their automated tests to pass. I think the global variables need refactored to do this as well.
• I was wondering about creating a Tile struct to store the index of each Tile rather than having to calculate index's so often. I'm unsure if that would be a good approach.

I implemented get_index() as linear search rather than binary search because I figured that the tradeoff of having to sort the array nearly every time wouldn't be worth it. Does that sound reasonable?

fifteen.c

 /**
 * Implements Game of Fifteen (generalized to dim x dim).
 *
 * Usage: fifteen d
 *
 * whereby the board's dimensions are to be d x d,
 * where d must be in [DIM_MIN,DIM_MAX]
 */

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "fifteen.h"

// hopefully shut up compiler about usleep()
#define _XOPEN_SOURCE (500)
#define _BSD_SOURCE

#define DIM_MIN (3)
#define DIM_MAX (9)

static int last_row;
static int last_col;
static int num_tiles;
static int empty_tile_index;
static int dim;

int board[DIM_MAX][DIM_MAX];

enum {
    EMPTY_SPACE = -1,
    ONE_OFFSET = 2,
    TWO_OFFSET = 3,
};

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("Usage: fifteen d\n");
        return 1;
    }

    dim = atoi(argv[1]);
    if (dim < DIM_MIN || dim > DIM_MAX)
    {
        printf("Board must be between %i x %i and %i x %i, inclusive.\n",
            DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX);
        return 2;
    }

    init_globals();
    greet();
    init();

    // accept moves until game is won
    while (true)
    {
        clear();
        draw();

        if (won())
        {
            puts("Solved! Ya did good, kid.");
            break;
        }

        printf("Tile to move: ");
        int tile = GetInt();

        // quit if user inputs 0 (for testing)
        if (tile == 0)
        {
            break;
        }

        if (!move(tile))
        {
            printf("\nIllegal move.\n");
            usleep(500000);
        }

        // sleep thread for animation's sake
        usleep(500000);
    }

    return 0;
}

/**
 * Clears screen using ANSI escape sequences.
 */
void clear(void)
{
    printf("\033[2J");
    printf("\033[%d;%dH", 0, 0);
}

void greet(void)
{
    clear();
    printf("WELCOME TO GAME OF FIFTEEN\n");
    usleep(2000000);
}

/**
 * Initializes the game's board with tiles numbered 1 through dim*dim - 1
 * (i.e., fills 2D array with values but does not actually print them).
 *
 * Note: tiles in descending order relative to increasing index:
 *
 *     |15|14|13|12|
 *     |11|10| 9| 8|
 *     | 7| 6| 5| 4|
 *     | 3| 1| 2| _| <-- Note: we swap 2 & 1 when dimensions are even
 *
 */
void init(void)
{
    for (int i = 0, num = num_tiles-1; i < num_tiles; i++, num--) {
        board[get_row(i)][get_col(i)] = num;
    }

    /* Per rules, if dimensions are even, tiles 1 & 2 must be swapped */
    if (dim % 2 == 0) {
        swap(num_tiles - ONE_OFFSET, num_tiles - TWO_OFFSET);
    }

    board[last_row][last_col] = EMPTY_SPACE;
}

/**
 * Swap the board elements at index1 & index2
 * Returns false on error, else true.
 */
bool swap(int index1, int index2)
{
    if (!valid_index(index1)) {
        return false;
    } else if(!valid_index(index2)) {
        return false;
    }

    int row1 = get_row(index1);
    int col1 = get_col(index1);

    int row2 = get_row(index2);
    int col2 = get_col(index2);

    int tmp = board[row1][col1];
    board[row1][col1] = board[row2][col2];
    board[row2][col2] = tmp;

    return true;
}

/**
 * Prints the board in its current state.
 */
void draw(void)
{
    int tile;
    bool is_end_of_row;

    for (int i = 0; i < num_tiles; i++) {
        is_end_of_row = (i % dim == dim - 1);
        tile = board[get_row(i)][get_col(i)];

        if (tile == EMPTY_SPACE) {
            printf("%2c ", '_');
        } else {
            printf("%2d ", tile);
        }

        if (is_end_of_row) {
            puts("\n");
        }
    }
}

/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false.
 */
bool move(int tile)
{
    int swapped_tile_index = get_index(tile);

    if (!valid_move(tile)) {
        return false;
    }

    bool swapped = swap(get_index(tile), empty_tile_index);
    empty_tile_index = swapped_tile_index;

    return swapped;
}

/**
 * Validate a move using the given tile's index by comparing
 * to potential moves indexes depicted in the figure below:
 *
 * Valid moves exist in a + shape around the empty tile:
 *     | |o| |
 *     |o|_|o|
 *     | |o| |
 *
 * Returns true if valid, otherwise false.
 */
bool valid_move(int tile)
{
    int tile_index = get_index(tile);

    if (!valid_index(tile_index)) {
        return false;
    }

    /* NOTE: at times these will be invalid board coordinates but it's fine
     * because they will never match the current tile_index
     */
    int row_above_index = empty_tile_index - dim;
    int row_below_index = empty_tile_index + dim;
    int col_left_index  = empty_tile_index - 1;
    int col_right_index = empty_tile_index + 1;

    if (tile_index == row_above_index) {
        return true;
    } else if (tile_index == row_below_index) {
        return true;
    } else if (tile_index == col_left_index) {
        return true;
    } else if (tile_index == col_right_index) {
        return true;
    } else {
        return false;
    }
}

/**
 * Returns true if game is won (i.e., board is in winning configuration),
 * else false.
 */
bool won()
{
    if (board[last_row][last_col] != EMPTY_SPACE) {
        return false;
    }

    for (int i = 0; i < num_tiles-1; i++) {
        if (board[get_row(i)][get_col(i)] != i+1) {
            return false;
        }
    }

    return true;
}


/**
 * Linear search to retrieve index of the tile from the board array.
 * Returns index of value if it exists, else -1 if not in board.
 */
int get_index(int tile)
{
    // valid tiles {1, num_tiles-1}
    if (tile <= 0 || tile >= num_tiles) {
        return -1;
    }

    for (int i = 0; i < num_tiles; ++i) {
        if (board[get_row(i)][get_col(i)] == tile) {
            return i;
        }
    }

    return -1;
}

/**
 * Returns false if the given index is outside the bounds of the board,
 * else true.
 */
bool valid_index(int index)
{
    if (index < 0 || index >= num_tiles) {
        return false;
    }

    return true;
}

int get_row(int index)
{
    return index / dim;
}

int get_col(int index)
{
    return index % dim;
}

/* Initializes global variables dependent on dimension argument */
void init_globals()
{
    num_tiles = dim*dim;
    last_row = (num_tiles - 1) / dim;
    last_col = dim - 1;
    empty_tile_index = num_tiles - 1;
}

fifteen.h

#ifndef FIFTEEN_H
#define FIFTEEN_H

#include <stdbool.h>

bool move(int tile);
bool swap(int index1, int index2);
bool valid_index(int index);
bool valid_move(int tile);
bool won();
int get_col(int index);
int get_index(int tile);
int get_row(int index);
void clear();
void draw();
void greet();
void init();
void init_globals();

#endif /* end of include guard: FIFTEEN_H */

Answer 1

The GOOD, there are no MAGIC numbers, good job! The naming conventions of the constants and enums follow the current coding standards. The code is quite readable which suggests it is maintainable. Excellent use of comments! Most of the functions are good examples of coding.

Obsolete Functions
Prefer standard functions that are portable over obsolete functions. usleep() is obsolete. See this StackOverflow Question.

At least the problem was documented:

// hopefully shut up compiler about usleep()
#define _XOPEN_SOURCE (500)
#define _BSD_SOURCE

Global Variabls
Avoid global variables whenever possible. The code already isolates them to the file using static, which is good, but there should be other ways to implement this solution that avoid globals. A suggestion would be to use a struct that defines the game and contains all the globals.

typedef struct
{
    int last_row;
    int last_col;
    int num_tiles;
    int empty_tile_index;
    int dim;
    int board[DIM_MAX][DIM_MAX];
} GameOf15_Data;

Pass the struct between the functions that need it, The struct should probably be defined in a header file so that the display functions can use it as well (See section below).

Separate Display from Game Logic
Over time the Model View Controller (MVC) pattern has been developed. The Model in this case is the game logic. The core game logic here could be reusable with multiple display mechanisms. In a proffesional environment the functions for display such as clear(), greet() and draw() would be in other files to allow for different display mechanisms (Windows, console, xbox, etc.). The use of multiple files would call for a more complex build strategy such as Make, or CMake.

Function Complexity
The function main() is too long and complex, there are at least 2 parts of this that could be turned into functions/subroutines. The code to report the error usage can be moved into a function and the code in the while (true) loop should be in a function possible called execute_game(). This Programmers Question discusses when is it good to break up a function, and points to a good reference book.

Answer 2

Bug - Valid Move

Your valid_move method has this comment in it.

/* NOTE: at times these will be invalid board coordinates but it's fine
* because they will never match the current tile_index
*/

Unfortunately, it's not fine, because some users don't play by the rules...

Give two lines of grid:

13 12 11 15  9
 _  8  7  6 10

If I input 9, the 9 will move into the _ position:

13 12 11 15  _
 9  8  7  6 10

Similarly, after the move, if I input 9 again, the _ and 9 will again swap positions.

static

So, the other thing that screamed out at me when I first opened the file was that it's kind of odd that all of your variables are state variables are static, apart from board. It seems like it should be static as well, unless I'm missing something?

Also, you're not marking any of your methods as static and you're including them in the header file. Is this because you're preparing for another consumer of your functions? Or should these methods really be static as well?