0

I've been working on this for a while and just can't seem to understand why it isn't passing the tests. It's timing out on the 3x3 board when the blank is top middle. I've rechecked my islegal() function and can't seem to figure out what's wrong. If anyone has any ideas that would be great. Thanks.

int board[DIM_MAX][DIM_MAX];

// dimensions
int d;
int tileVal;


//blank tile locators
int blankRow;
int blankCol;

//tile to swap locators
int tileRow;
int tileCol;

// prototypes
void clear(void);
void greet(void);
void init(void);
void draw(void);
void search(int tile);
void swap(int tile);
bool islegal(void);
bool move(int tile);
bool won(void);


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

    // ensure valid dimensions
    d = atoi(argv[1]);
    if (d < DIM_MIN || d > 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;
    }

    // open log
    FILE *file = fopen("log.txt", "w");
    if (file == NULL)
    {
        return 3;
    }

    // greet user with instructions
    greet();

    // initialize the board
    init();

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

        // draw the current state of the board
        draw();

        // log the current state of the board (for testing)
        for (int i = 0; i < d; i++)
        {
            for (int j = 0; j < d; j++)
            {
                fprintf(file, "%i", board[i][j]);
                if (j < d - 1)
                {
                    fprintf(file, "|");
                }
            }
            fprintf(file, "\n");
        }
        fflush(file);

        // check for win
        if (won())
        {
            printf("ftw!\n");
            break;
        }

        // prompt for move
        printf("Tile to move: ");
        int tile = get_int();

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

        // log move (for testing)
        fprintf(file, "%i\n", tile);
        fflush(file);

        // move if possible, else report illegality
        if (!move(tile))
        {
            printf("\nIllegal move.\n");
            usleep(500000);
        }

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

    // close log
    fclose(file);

    // success
    return 0;
}

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

/**
 * Greets player.
 */
void greet(void)
{
    clear();
    printf("WELCOME TO GAME OF FIFTEEN\n");
    usleep(2000000);
}

/**
 * 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)//TODO
{
    int tileVal = ((d*d)-1);
    //even grid end swap
    for(int row=0;row<d;row++){
        for(int col=0;col<d;col++){
            board[row][col] = tileVal;
            tileVal--;
        }
    }
    if (tileVal % 2 != 0){
        int temp = board[d-1][d-2];
        board[d-1][d-2] = board[d-1][d-3];
        board[d-1][d-3] = temp;
    }
    blankRow = (d-1);
    blankCol = (d-1);

}

/**
 * Prints the board in its current state.
 */
void draw(void) //TODO
{
    for(int row=0; row<d; row++){
        for(int col=0; col<d; col++){
            if(board[row][col] > 9){
                printf("%i ", board[row][col]);
            }
            else if(board[row][col]>0){
                printf(" %i ", board[row][col]);
            }
            else{
                printf(" _ ");
            }
        }
        printf("\n");
    }
}

/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false.
 */
bool move(tile)
{
    // TODO
    if(tile>(d*d)-1 || tile<1){
        return false;
    }
    search(tile);
    if(islegal()){
        swap(tile);
        return true;
    }
    else{
        return false;
    }
    return false;
}

//define search function to find tile lcoations
void search(int tile){
    for(int row=0; row<d; row++){
        for(int col=0; col<(d*d); col++){
            //set tile placeholders
            if(board[row][col] == tile){
                tileRow = row;
                tileCol = col;
            }
        }
    }
}

//define islegal function
bool islegal(void){
    //top
    if (tileRow > 0 && board[tileRow - 1][tileCol] == 0)
        return true;
    // bottom
    if (tileRow < d-1 && board[tileRow + 1][tileCol] == 0)
        return true;
    // left
    if (tileCol > 0 && board[tileRow][tileCol - 1] == 0)
        return true;
    // right
    if (tileCol < d-1 && board[tileRow][tileCol + 1] == 0)
        return true;
    else{
        return false;
    }
}

//define swap function
void swap(int tile){
    int temp = tile;
    board[tileRow][tileCol] = board[blankRow][blankCol];
    board[blankRow][blankCol] = temp;

    // update location of blank tile
    blankRow = tileRow;
    blankCol = tileCol;
}

/**
 * Returns true if game is won (i.e., board is in winning configuration),
 * else false.
 */
bool won(void)
{
    int count = 1;
    for(int row=0; row<d; row++){
        for(int col=0; col<d; col++){
            if(board[row][col] == count){
                count++;
            }
        }
    }
    if(count == d*d && board[d-1][d-1] == 0){
        return true;
    }
    return false;
}
1

Firstly, you are not setting your board up properly. According to the specification:

If, however, and only if the board contains an odd number of tiles (i.e., the height and width of the board are even), the positions of tiles numbered 1 and 2 must be swapped, as in the below.

Your init function is using tileVal to determine when to swap the board:

if (tileVal % 2 != 0){

But in the previous loop, you are decrementing tileVal. By the time your function tests tileVal in this if statement, tileVal is -1. You should be testing with the dimension d which hasn't changed.

if (d % 2 == 0) {  // if the board dimensions are even

When you're debugging, and not sure where a problem was, eliminate parts of your code. For instance, if you ran your code with ./fifteen 3 and started a game, you would see that the 3x3 board is swapping tiles when it shouldn't (it has 8 tiles and odd board dimensions). And ./fifteen 4 is also swapping tiles (which it should). If you don't see a problem where you think the problem is, try starting at the top of main, and verifying that each step is performing as it should.

Secondly, you have a runtime error in your search function.

for(int col=0; col<(d*d); col++){

Your array has d rows and d cols. You can't iterate col past d-1. This for loop should be like the row for loop.

for(int col=0; col<d; col++){

There is also a compile error in your program as posted, but that is easily fixed. Hopefully these fixes will get you closer to a solution.

  • Thank you so much. You were right, init() was the problem... l changed that and search and it passed all tests. Thanks! – Michael Aug 31 '17 at 19:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .