Pset3 Game of Fifteen Won Function

Question

The won function for fifteen is driving me crazy! Here's my implementation. I've run it through debug50 and it appears to work as expected. However, check50 only passes on a 4x4 board, but not a 3x3. Can someone help me spot the error in my code?

bool won(void)
{
    int counter1 = 0;
    int counterr = 0;
    int counterc = 0;

    for (int row = 0; row < d; row++)
    {
        for (int column = 0; column < d; column++)
        {
            counterc++;

            if(counterc == d)
            {
                counterc = 0;
                counterr++;
            }

            if (board[row][column] < board[counterr][counterc])
            {
                counter1++;
            }
        }
    }
    if (counter1 == d * d - 2) // The minus 1 is to account for the 0 at the end
        return true;

    else
        return false;
}

Answer 1

I suspect that a 4x4 can also generate false wins, given the right sequence of inputs.

The problem is that the won() function, as written, can report a win when the tiles are in a certain order. If the blank tile is out of place but the remaining tiles are in sequential order, it will result in a win being reported.

A simple fix would be to check that the 0 tile is in the correct location. In fact, doing this first will significantly increase the efficiency of the won function because most of the time, the 0 tile is out of place. If it is out of place, there's no reason to check anything else.

You might also increase efficiency by comparing each tile against a counter instead of the next tile.

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

Answer 2

A possible pseudocode for win would be:

for row
    for column
        // in each movement, if the position of board [i] [j] coincides with  
        //  the expected value increases
        // the counter in 1 if some value differs from the expected we left won
        if board[i][j] == expected value
        count++
        else 
          return false

        // if at the end of the loop count matches the number of tiles, we are 
        //in the winning configuration  
       if count == d*d -1
       return true 

The trick is expected value, there is a simple arithmetic relationship between i, j and d that gives us such relationship for example in the winning configuration:

board[0][0] = 1
board[0][1] = 2

etc... I let you find this relationship