Pset3 fifteen.c - Move function allows invalid moves

Question

To implement the move() function I divided it into three functions, one to find the tile inputted by the user, one to check if the move is legal, and one to actually move the tiles.
At first it looked like it worked but it is allowing invalid moves, on the first move it works only valid moves can be made. But after the 2nd move it allows some invalid moves such as:

8    7    6        8    7    6       8    7    6       8    7    6

5    4    3    ->  5    4    3   ->  _    4    3   ->  3    4    _

2    1    _        2    _    1       2    5    1       2    5    1

Taking the last picture as an example, it does not allow moves: 8, 7

But allows everything else: 6, 3, 4, 2, 5, 1

Here's the code: Finds the inputted tile

// declare tile location variables
int tile_locr;
int tile_locc;

// searches for location of inputted tile   
int tile_search(int tile)
{
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < d; j++)
        {
            if (board[i][j] == tile)
            {
                tile_locr = i;
                tile_locc = j;
            }
        }
    }
    return 1;
}

Checks if the move is legal

// checks is move is legal
bool islegal(void)
{
    // check top
    if (board[tile_locr - 1][tile_locc] == 0)
    {
        return true;
    }
    // check bottom
    else if (board[tile_locr + 1][tile_locc] == 0)
    {
        return true;
    }
    //check right
    if (board[tile_locr][tile_locc + 1] == 0)
    {
        return true;
    }
    // check left
    else if (board[tile_locr][tile_locc - 1] == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Moves the tile
blank_locr and blank_locc have been declared as d - 1 in the init() function

bool move(int tile)
{   
    tile_search(tile);
    if (islegal())
    {
        // back up vars
        int temp = board[tile_locr][tile_locc];
        int temp_r = tile_locr;
        int temp_c = tile_locc;

        //move the blank
        board[tile_locr][tile_locc] = board[blank_locr][blank_locc];

        // move tile
        board[blank_locr][blank_locc] = temp;

        // update location of blank
        blank_locr = temp_r;
        blank_locc = temp_c;

        return true;
    }
    else
    {
        return false;
    }
}

I can't figure out what's wrong, any help is appreciated! :)

Answer 1

1. My understanding from your islegal() is that if board[row, column]==0, then that is a blank tile? If so, what roles do blank_locr and blank_locc play in move()? Could you just as easily have used: if (tile_locr-1==blank_locr) instead of if (tile_locr-1 . . .==0), etc in islegal() or is my understanding totally off? It looks like you may not be updating the location of the blank tile properly by not being consistent.

2. On an unrelated note, you run the risk of segfaulting in islegal() if you do not check for values on the borders (e.g. tile_locr - 1 if tile_locr=0).

Answer 2

I cannot spot exactly where your problem is, but I can provide you with a little insight about designing your code in general.

• I can't tell from your snippets, but I imagine you declared tile_locr and tile_locc as global variables. Then, when you search for the tile, you update the value and always return 1. In this particular case, if you previously checked whether tile is actually in board, it should work. But, as a general rule, that's not good design choice. You should always program defensively, i.e.: always asume there will be an error or an unexpected input. In this case, if the user entered a non-existant value (tile > d*d), you'd search the whole board, not find it, and always return the same value (1). So there's no way your code can realize whether you found anything or not.

• In the tile_search function, you're always searching the whole board, whether you found the tile in the first position or in the last one. When the tile is 4x4, it's no big deal. But imagine how much time you'd save if the board was huge (like 1.000.000 x 1.000.000) if you stepped out of the search function as soon as you found your tile:

  int tile_search()
  {
      for (int i = 0; i < d; i++)
      {
          for (int j = 0; j < d; j++)
          {
              if (board[i][j] == tile)
              {
                  // Eureka!
                  tile_locr = i;
                  tile_locc = j;
                  return 0;
              }
          }
      }
  
      // Couldn't find your tile
      return 1;
  }
  

HTH!

Answer 3

The issue is that your islegal function isn't properly checking to make sure that the tile_locc +/- 1 and tile_locr +/- 1 doesn't exceed the boundaries of the board. The reason you are getting inconsistent and strange behavior is because when a value is chosen that would cause the boundaries of the board to be exceeded, the program is still checking that invalid location to test if it's == 0 and somehow, miraculously, it's not seg faulting. Since the unallocated space is filled with "garbage values", it's likely that some of these are being interpreted as == 0.

I tested this by recompiling your code and making some adjustments. For example, when I modified your code to add all of the necessary checks (really just an extra && statement in all of your ifs in islegal(), the program runs fine and all moves are properly allowed or labeled illegal.

Example:

I changed this:

if (board[tile_locr - 1][tile_locc] == 0)

To this:

if (board[tile_locr - 1][tile_locc] == 0  && tile_locr != 0)

//this is ok because we know that as long as the tile_locr isn't equal to zero, then we can safely subtract 1 from it without exceeding the boundaries of the board(array). There's really no board[-1][0], but without this extra statement, the program tries to check that array spot anyway, and is apparently finding something and not seg faulting.

and this:

else if (board[tile_locr + 1][tile_locc] == 0)

to this:

else if (board[tile_locr + 1][tile_locc] == 0)  && tile_locr < d)

Answer 4

This is hard to explain, so I'll try my best.

In order to understand why this is happenning,we must first see how the program creates the board array:

// constants
#define DIM_MIN 3
#define DIM_MAX 9

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

as you can see, every time we exectue the program, the board is created with the max size. Once declared, it allocates all the memory and by default set them all to 0.

|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|

Then, we populate the array within the dimensions given by the user, so for example, if the user enters 3, then the board should look something like this:

|8|7|6|0|0|0|0|0|0|
|5|4|3|0|0|0|0|0|0|
|2|1|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|

So, as you can see, checking for 0 is not the best way to do this, since if I ask 6 for example, it will sy it is legal to move this tile, since a neighbor is 0. The only tiles that work as expected are the ones that are not near boundaries, like in this case: 4 and 7.

But, if in this case, I try to move tile 5, it will also work, even though there are no zeros neighboring this tile... why?

This is because of how c deals with multidimensional arrays. Even though it looks like a table, c stores the array values linearly, so if I declare an array like this:

multiArray[3][3];

it is stored the same way as this:

array[9];

multidimensional arrays are just a more "human" way to deal with information, the computer just allows us to access the values in a different way.

Saying this, the 5 we were trying to move before IS neighboring a 0 too! so your code is also saying its legal to move that tile.

This is a mess, and is not an easy bug the decychper. The easiest way to solve it is to also check if the 0 you're looking for is inside the board, restricting any other 0's to work with your program.