Game of Fifteen pset3 - won() function works, but why?

Question

I've managed to get a thumbs up from check50 in the Game of Fifteen, but I have no idea why. It's really eating at me and I refuse to go forward until I understand it.

Here's my less than eloquent function:

bool won(void)
{

int i,j;
int y = d*d;
int x;

if (board[d-1][d-1] != 0)
{
    return false;
}

for (i = 0, x = 1; i < d && x < y-1; i++) 
{
    for (j = 0; j < d; j++)
    {
        if (board[i][j] == x) 
        {
            x++;
        }
        else if (board[i][j])
        {
            return false;
        }
    }
}
return true;
}

My issue is with the else if statement, which seems to be needed in order to appease the check50 gods. When completely removed, the very first call to won() seems to return true and the game ends immediately. When changed to just "else" rather than "else if", the final check returns false and the game expects another move.

Running the program through gdb I saw that board[i][j] contains 0 on that final check, so I thought it might have something to do with returning true or false. I changed it to "else if (0)" and the game ends at "ftw" without ever running. I tried "else if (1)" and the game runs, but the function returns false.

It was just dumb luck that I had the "else if (board[i][j])" there when I compiled it; to be honest, I never meant to test it that way. I just forgot to delete that snippet of code. So why does it only work with that bit of code? Obviously I'm missing something. If someone can point me in the right direction I'd greatly appreciate it. I want to make sure I understand WHY.

Thank ya!

Answer 1

Think about what happens in various scenarios. First, the first if test checks that 0 is in the last tile. If it isn't, the code returns false, so from there on, 0 must be in the last tile. Keep this in mind.

Now, in the nested for loops, the code starts checking that the tiles are in order, starting at 1. The first check verifies that the correct value is in the tile. This continues until it gets to the last tile, which will be 0. So, at that point, the test if (board[i][j] == x) fails, causing the code to go to the else clause, which is another if test. The second if test, if (board[i][j]) results in false because the last tile contains 0. If it had anything else, it would be true because any non-zero evaluates as true, but that's not possible because of the initial test noted above.

Now, let's talk about else if. If it were just else, it would be a problem. The else clause would only execute under two conditions. 1) If the tiles are not in the correct order, the else clause would execute and return false, which is fine, or, 2) if the tiles are in order and it gets to the 0 tile, the else clause would execute and return a false when it shouldn't.

By having else if, the if statement handles the second condition. If the tile is 0, then it evaluates as false and the return false is skipped and the code drops through to the return true. If the last tile isn't 0, then the return false is executed. But that only happens when the tiles are out of order as in the first condition and the else clause is engaged before the last tile.

Does it make more sense now?

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)