Game of Fifteen

I'm slowly catching up on write ups of my cs50 psets, and next up is the next challenge from pset3, the Game of Fifteen.

It's fairly simple, it draws the current state of the board, you enter which tile you want to move, and it redraws the board until you win.

I will preface this write up by saying this is the one Hacker Edition I didn't complete. The more challenging version asked you to create the game with a built-in "god mode" that could solve the puzzle on it's own. I spent a week reading white papers and attempting a solution, and eventually called it quits. I think it's fair to say I'm not good enough at solving the puzzle on my own to be able to program a computer to solve it for me :)

After compiling the program you call it from the terminal by typing:

./fifteen [d]

Where d is the number of tiles you want the width/height to be, with a minimum of 3 and a maximum of 9.

We set those along with a global array to hold the board state like so:

// constants 
#define DIM_MIN 3 
#define DIM_MAX 9 

// board 
int board[DIM_MAX][DIM_MAX]; 

The main function checks to make sure the command line arguments are correct, opens up a log file, greets the user, and then initializes the board.

/** 
 * Initializes the game's board with tiles numbered 1 through d*d - 1 
 * (i.e., fills 2D array with values but does not actually print them).   
 */ 
void init(void) 
{ 
    // Get Total number of spaces 
    int total = d * d; 
     
    // Add tiles to board 
    for (int i = 0; i < d; i++) 
    { 
        for (int j = 0; j < d; j++) 
        { 
            // Decrement value by one and assign to array 
            board[i][j] = --total; 
        } 
    } 
     
    // Swap 2 and 1 if even number of spaces 
    if ((d * d) % 2 == 0) 
    { 
        board[d - 1][d - 3] = 1; 
        board[d - 1][d - 2] = 2; 
    } 
} 

This ensures there is a blank space and is actually solvable, since if it's an even total, the 1 and 2 need to be swapped.

Once the board has been set, the program enters an "infinite" while loop, running until the puzzle is solved and then end.

Each time through the loop the screen clears and redraws the current state of the board, making sure any user input is reflected on the screen.

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

/**
 * Prints the board in its current state.
 */
void draw(void)
{
    // Loop through board array
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            // Print line instead of zero
            if (board[i][j] == 0)
            {
                printf("  _");
            }
            else 
            {
                printf("%3i", board[i][j]);
            }
        }
        
        printf("\n\n");
    }
}

Once the board has been drawn to screen, we do a check to see if you've won or not:

/**
 * Returns true if game is won (i.e., board is in winning configuration), 
 * else false.
 */
bool won(void)
{
    // Set counter
    int counter = 0;
    
    // Check each tile to ensure it's in order
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            // Check if last spot and if not correct value
            if (++counter != (d * d) && board[i][j] != counter)
            {
                return false;
            }
        }
    }
    
    return true;
}

If you haven't won, it's your turn to move a tile. The program asks for an integer (if you type 0 it exits the program), and checks to see if that tile can be moved. If it can be, it updates the board and the while loop continues:

/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false. 
 */
bool move(int tile)
{
    // Check if valid tile
    if (tile > d * d - 1 || tile < 1) 
    {
        return false;
    }
    
    // Search board for row, and column
    int row = 0, column = 0;
    
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            if (board[i][j] == tile)
            {
                row = i;
                column = j;
            }
        }
    }
    
    // Check nearby spaces
    if (row - 1 >= 0 && board[row - 1][column] == 0)
    {
        board[row - 1][column] = board[row][column];
        board[row][column] = 0;
        return true;
    }
    else if (row + 1 < d && board[row + 1][column] == 0)
    {
        board[row + 1][column] = board[row][column];
        board[row][column] = 0;
        return true;
    }
    else if (column - 1 >= 0 && board[row][column - 1] == 0)
    {
        board[row][column - 1] = board[row][column];
        board[row][column] = 0;
        return true;
    }
    else if (column + 1 < d && board[row][column + 1] == 0)
    {
        board[row][column + 1] = board[row][column];
        board[row][column] = 0;
        return true;
    }
    
    return false;
}

The program looks at the spaces around the tile you chose to see if any are open, otherwise it logs it as an illegal move.

And that's it! The game continues until you've either won or quit. Pretty simple to get it working with human input, but like I said, getting the Hacker Edition able to solve itself is a whole other story... If any of you CS50 students figured it out I'd love to see your programs!

For my full implementation, you can see the file in my GitHub project as always.