Pset3 won-function works only with 3x3 board. Where am I wrong?

Question

Pset3 won-function successfully passed this test ./fifteen 3 < ~cs50/pset3/3x3.txt only for a 3 × 3 board. For a 4x4 board the program's output is:

   1   2   3   4

   5   6   7   _

   9  10  12   8

  13  11  15  14

ftw!

The blank space is d*d. The won function contains 2 nested for-loops and inside the one long condition:

for(int i = 0; i < d; i++)
{                     
   for(int j = 0; j < d; j++)
   {
       if (i + 1 < d && i - 1 >= 0 && j + 1 <= d && j - 1 >= 0 && board[i][j - 1] ==    board[i][j] - 1 && board[i][j + 1] == board[i][j] + 1 && board[i - 1][j] == board[i][j] - d && board[i + 1][j] == board[i][j] + d)
       {
           return true;                   
       }           
   }             
}                
return false;

Answer 1

As correctly pointed out by Kareem it is quite confusing when you start to debug the long 'if' condition and it may also at times give you wrong answer.

I would suggest an alternative approach to such problems which require comparisons. You might want to initiate a counter that increments every time an array element matches the winning array element of a winning combination.

As pointed in the shorts, one such algorithm to determine the correct array element is board[i][j] == ( (d*i)+(j+1) ), i.e. each array element is correct if its value is equal to sum of total number of rows times current row number (row number starts from 0) and the current column number plus 1 (column number also starts from 0). If such condition occurs you can then increment your counter. In the end if the counter value matches (d*d-1) i.e. the counter has been incremented correct number of times then you can return true.

Given below is the implementation using such logic.

bool won(void)
{
    int i,j,total=0;

        for (i = 0; i < d; i++)
        {
            for (j = 0; j < d; j++)
            {
                if (board[i][j] == ( (d*i)+(j+1) ))
                {
                    total++;
                }
            }
        }

    if (total == (d*d)-1)
    { return true; }
    else
    { return false; }
}

Answer 2

Following your code, there are some issues.

First, it's not a good practice to have such looong line of code. It's recommended by the CS50 staff that your line shouldn't exceed 80 characters.

Second, the purpose of won() is to check whether the tiles are in ascending order followed by the blank tile. If you've tried to follow your code, or probably use gdb to figure out what is happening, you'd probably find that as soon as your long condition is evaluated to true, this function will return true and end execution no matter how many tiles are left without checking.

Third, what do you think i + 1 and j + 1 are evaluated to when i = d - 1 and j = d - 1. They're gonna be d, right? But unfortunately, d is beyond our 2-dimensional array (i.e., board). So you might run through some errors because of that too.

Lastly, try to write some pseudocode for the successful scenario of how won() should work!

You may update your answer with your pseudocode so that we can help you identify any bugs (if exist)!

Good luck!