pset3 / move function

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;
``````

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.

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
}
``````
• for some reason, following your algorithm, always returns me "Illegal move."(at least it returns something, not like mine.) if the last line of my function isn't return, I get error message "control may reach end of non-void function". Jul 22, 2014 at 19:32
• @user1929 how do you search for the tile? In other words, how do you obtain `row` and `column`?
– kzidane
Jul 22, 2014 at 19:39
• with linear search. int row, column; //search to find the blank tile's position for( int i = 0; i < d; i++ ) { for( int j = 0; j < d; j++ ) { if( board[i][j] == 0 ) { row = i; column = j; } } Jul 22, 2014 at 19:57
• @user1929 well, this doesn't seem right. You're iterating correctly though. However, I don't know why you're checking whether `board[i][j]` is equal to 0. You seem to be misunderstanding this and you're searching for the blank tile. Rather, you should search for the tile that's passed to `move()` as an argument. As for the blank tile, you probably may use global variables to store its row and column keeping in mind that you should update this row and this column after each move is made. See this answer for more info!
– kzidane
Jul 22, 2014 at 20:35
• @user1929 I've updated my answer with some pseudocode!
– kzidane
Jul 22, 2014 at 20:36

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`?

• Thomas thank you very much for your answer! I'll apply your suggestions to my code and work on it! Jul 22, 2014 at 16:16
• @user1929 Good luck; I expanded my answer a bit in case you still have trouble.
– Air
Jul 22, 2014 at 16:22
• can I modify the variables the program passes to move? I want to save the blank tile's position. then I could play with absolute values. something like: abs(blank_i - tile_i)== 1 && abs(blank_j - tile_j) == 0 ... what do you think??? Jul 22, 2014 at 17:10
• @user1929 The specs say: "Youâ€™re welcome to write your own functions and even change the prototypes of functions we wrote. But we ask that you not alter the flow of logic in `main` itself so that we can automate some tests of your program once submitted. In particular, `main` must only return `0` if and when the user has actually won the game..." So yes, you can modify the prototype of `move` to pass different variables.
– Air
Jul 22, 2014 at 17:43
• Thanks a lot.And what do you think about my logic?Could this work? Jul 22, 2014 at 17:58