pset3 / move function

Question

The program cannot recognize a legal ( or illegal ) move too. How did you check whether a move is legal or not? Here's my code block for testing:

//check if the move is legal
//posi and posj = i and j of tile to be moved 
di = posi-1;
dj = posj-1;
ai = posi + 1;
aj = posj + 1;
if( di >= 0 )
{
   if( board[posi-1][posj] == 0 )  
   {
       board[posi-1][posj] = tile;
       board[posi][posj] = 0;//empty tile
       flag = 1;
   }
}
else if( ai < d )
{
   if( board[posi+1][posj] == 0 )
   {
       board[posi+1][posj] = tile;
       board[posi][posj] = 0;
       flag = 1;
    }
 }
else if( dj >= 0 )
{
   if( board[posi][posj-1] == 0 )
   {
       board[posi][posj-1] = tile;
       board[posi][posj] = 0;
       flag = 1;
    }
}
else if( aj < d )
{
   if( board[posi][posj+1] == 0 )
   {
       board[posi][posj+1] = tile;
       board[posi][posj] = 0;
       flag = 1;
   }
}

if( flag == 1)
   return true;
else
   return false;  

Answer 1

The move() function basically does 3 main things:

1. receives the number on the tile to be move.
2. validates the move.
3. if the move is valid, it makes it and returns true. Otherwise, it returns false.

First, receiving the number on the tile to be moved involves some linear search to get the row and the column of that tile in the board.

Second, validating the move has to do with checking the adjacent tiles. Given a tile that's in row, col in the board, these are the 4 possible adjacent tiles

              row - 1, col
row, col - 1    row, col    row, col + 1
              row + 1, col

Notice, however, that 4 adjacent tiles is actually the maximum number of adjacent tiles for any tile to have. Meanwhile, there are tiles that have less number of adjacent tiles (e.g., the corner tiles).

Lastly, if the blank tile is in one of these adjacent locations, you should swap the two tiles. Don't forget to update the row and the column of the blank tile and return true.

If, however, the number that was passed to our function as the number on the tile to be moved is not really in our board, or the blank tile is not in one of the adjacent positions to that tile, the move() function should return false immediately.

---

What's wrong with your code?

Well, you don't really need to use all of these variables. i and j which I assume they correspond to row and col are probably enough and can be used directly in the process of checking the adjacent squares.

I'm really confused following all of these variables as they make your code harder to read and to understand specially when there are no comments. Besides, they make your program take more memory than it'd really need with a better solution. Hopefully, I could figure out that they're used to prevent checking illegal array indexes.

Obviously, the linear search part is missing, so I'll assume you already found the tile at board[i][j].

So with all of these variables, you're over-complicating things a little bit. One of the main issue is, as noticed @AirThomas mentioning something about it, the if/else if/else statements.

In short, only the first met condition of these is executed and the others are ignored. Not as you might have thought that multiple of them might be executed.

Following that, you may return true immediately after making the move.

---

How to solve that?

First, minimize your usage of variables and get rid of the extra variables and simplify things a little. Try to count on two main variables i, j or row, col whatever you call them as they're enough for the checking adjacent tiles process. For example, I could have something like this to check the adjacent squares

// up
if (row > 0)
{
    if (board[row - 1][column] is the blank tile)
    {
        make the move
        return true
    }
}

// right
if (column < d - 1)
{
    if (board[row][column + 1] is the blank tile)
    {
        make the move
        return true     
    }    
}

// bottom
if (row < d - 1)
{
    if (board[row + 1][column] is the blank tile)
    {
        make the move
        return true
    }
}

// left
if (column > 0)
{
    if (board[row][column - 1] is the blank tile)
    {
        make the move
        return true
    }
}

return false

Remember why I didn't use else if here? To allow one or more of these conditions to be met. And notice that I'm returning true immediately once I'm making the move.

And lastly, I'm returning false if none of these conditions is met indicating that the move is invalid. Recall that false should be returned in case the tile wasn't found in the board at the first place.

---

Edit:

to find the row and the column of the tile using linear search, you may do the following

declare a bool named found and set it to false

for (row = 0 to (row < d), increment row by 1)
{
    for (column = 0 to column < d, increment column)
    {
        if (board[row][column] is equal to tile)
        {
            set found to true
            break
        }
    }

    if tile found
        break
}

Answer 2

This is one of the tricker aspects of the problem set, in my opinion.

The "plain English" condition you are checking here is whether there's an empty space adjacent to the selected tile. But in terms of what the computer understands, that raises many more questions, like how do you identify adjacent spaces? Once you've identified them, how do you tell whether they're on the board or "out of bounds?" And then, how do you access them to determine if they are "empty" or have a tile already?

Your approach overall is solid, although I hate your variable names di, dj, ai and aj - this is 2014, you have plenty of space on your hard drive and monitor to store and display source code. So use words! And then re-use them in your inner if conditions while you're at it. Notice also that you have a lot of duplicated code with this approach - only one of the three lines in each of your inner if bodies changes from block to block.

---

Those are stylistic issues; you want to know why your code doesn't work.

A good debugging practice for short algorithms can be to run through your code "by hand" using a piece of paper and a pen or pencil. Write down variables when they're declared and what values are stored in them, do arithmetic, check conditions, talk through the code out loud - it will make you sound like a crazy person, but it's effective.

In this case, you have an if ... else if construct happening. The thing about if ... else if is that only one or the other block will ever be executed. So if your first outer condition di > 0 is true, your code will never check any of the other three outer if blocks - even when the inner condition board[posi-1][posj] == 0 fails.

You could split your outer blocks into separate if statements, since only one of the four possible adjacent locations can ever pass both tests. That should work, but it's not the cleanest solution because you would check all four positions even if you found a legal move in the first check.

This goes back to style, and I'll give you this clue: Instead of instructing the computer to check four positions for a legal move, is there a way you could instruct the computer to check positions until you find a legal move or run out of positions?