# Pset3 Game of Fifteen Won Function

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

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. ;-)

• Many thanks! I rewrote my code to check if 0 was in the bottom right corner, and compared the array to a counter, as you suggested. It now works perfectly. Thanks again for your help! Jun 7, 2017 at 21:48

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 = 1
board = 2
``````

etc... I let you find this relationship

• Yes, but did you figure out what was wrong with his code, MARS? ;-) Jun 7, 2017 at 21:33