Checking for a win in Tic Tac Toe

Question

I'm working on Tic Tac Toe and I want do it for any ROW x COL board with any WIN_SIZE (e.g. 4x4 board requires 3 to win). I've done the hasWon method already but I'm not sure is it done right. Can you check what can I do better here?

public boolean hasWon(Seed theSeed) {
    int count = 0;

    for (int col = 0; col < COLS; ++col) {               //check columns
        if (cells[currentRow][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }
    count = 0;

    for (int row = 0; row < ROWS; ++row) {              //check rows
        if (cells[row][currentCol].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }
    count = 0;

    int row = currentRow;

    for (int col = currentCol; col >= 0; --col) {      //check forward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

    count = 0;
    row = currentRow;

    for (int col = currentCol; col >= 0; --col) {  //check backward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    return false;
}

Answer 1

public boolean hasWon(Seed theSeed) {

What is a Seed? The way that you are using it, I'd expect a Player object.

    for (int col = 0; col < COLS; ++col) {               //check columns
        if (cells[currentRow][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

A more common format would be

    //check squares in currentRow
    for (int col = 0; col < COLS; ++col) {
        if (cells[currentRow][col].content == theSeed) {
            count++;
        } else {
            count = 0;
        }

        if (count == WIN_SIZE) {
            return true;
        }
    }

I added the else because I would expect a match to need to be consecutive. As is, you would accept any row containing WIN_SIZE total matches. Maybe that's what you want, but it's not what I would expect.

You iterate over columns when you are checking a row. The original comment was a bit confusing on that aspect.

While there is a single statement form of control structures (if), it is often recommended not to use it. It's less clear about what goes with what and it's easier to edit in a way that causes problems but is syntactically correct.

    count = 0;

    int row = currentRow;

    for (int col = currentCol; col >= 0; --col) {      //check forward diagonal
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row--;
        if (row < 0)
            break;
    }
    row = currentRow;
    count--;
    for (int col = currentCol; col < COLS; ++col) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
        row++;
        if (row == ROWS)
            break;
    }

This looks more complicated than it needs to be. Consider

    // check forward diagonal
    for (int col = currentCol, row = currentRow; col >= 0 && row >= 0; --col, --row) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

    for (int col = currentCol + 1, row = currentRow + 1; col < COLS && row < ROWS; ++col, ++row) {
        if (cells[row][col].content == theSeed)
            count++;
        if (count == WIN_SIZE)
            return true;
    }

Yes, you can use two variables in one for loop.

Rather than decrementing the count, this skips the current square in the second loop.

Or do the whole thing in one loop.

    // check forward diagonal
    count = 0;
    int col = 0;
    int row = 0;
    if (currentCol >= currentRow) {
        col = currentCol - currentRow;
    } else {
        row = currentRow - currentCol;
    }

    for (; col < COLS && row < ROWS; ++col, ++row) {
        if (cells[row][col].content == theSeed) {
            count++;
        }

        if (count == WIN_SIZE) {
            return true;
        }
    }

More work up front to figure out the first square in the diagonal, but only a single loop.

I left off the else case, as I'm not sure whether the current behavior is intentional or not. The single loop version works with the else as before. The double loop versions don't.

Answer 2

In your code there are four loops with very similar functionality. Each loop checks the board in a different direction. This could be extracted to a method and reuse the method 4 times:

/**
 * 
 * @param theSeed   Value expected in each cell
 * @param row       Row index to check
 * @param col       Col index to check
 * @param count     Number of consecutive elements found in the line. 
 * @param rowIncrement   Increment to the row index for the next evaluation
 * @param colIncrement   Increment to the col index for the next evaluation
 * @return  true if there is a winner combination in the line, otherwise false. 
 */ 
private boolean checkLine(Seed theSeed, int row, int col, int count, int rowIncrement, int colIncrement) {
    if (!areValidIndexes(row, col)) {
        return false;
    }

    if (theSeed == cells[row][col].getContent()) {
        count++;
        if (count >= WIN_SIZE) {
            return true;
        } else {
            return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement);
        }
    } else {
        return false;
    }
}


private boolean areValidIndexes(int row, int col) {
    if (row >= 0 && row < ROWS &&
        col >= 0 && col < COLS) {
        return true;
    }
    return false;
}

To simplify the usage of this method, we could create some wrapper method for each direction:

private boolean checkRow(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 1, 0);
}

private boolean checkColumn(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 0, 1);
}

private boolean checkForwardDiagonal(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, 1, 1);
}

private boolean checkBackwardDiagonal(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, col, 0, -1, 1);
} 

At this point, implement the hasWon method is very straightforward, just iterate over each cell and check each direction:

public boolean hasWon(Seed theSeed) {
    for (int row = 0; row < ROWS; row++) {
        for (int col = 0; col < COLS; col++) {
            if (checkRow(theSeed, row, col) ||
                checkColumn(theSeed, row, col) ||
                checkForwardDiagonal(theSeed, row, col) ||
                checkBackwardDiagonal(theSeed, row, col)) {

                return true;
            }
        }
    }
    return false;
}

---

UPDATE

As suggested in the comments, the algorithm could be more efficient if only the row, column and diagonals of the last move are checked.

The method checkLine would be more useful to implement this change if the full line is checked for a winner combination:

/**
 * 
 * @param theSeed   Value expected in each cell
 * @param row       Row index to check
 * @param col       Col index to check
 * @param count     Number of consecutive elements in the line. 
 * @param rowIncrement   Increment to the row index for the next evaluation
 * @param colIncrement   Increment to the col index for the next evaluation
 * @return  true if there is a winner combination in the line, otherwise false. 
 */
private boolean checkLine(Seed theSeed, int row, int col, int count, int rowIncrement, int colIncrement) {
    if (!areValidIndexes(row, col)) {
        return false;
    }

    if (theSeed == cells[row][col].getContent()) {
        count++;
        if (count >= WIN_SIZE) {
            return true;
        } else {
            return checkLine(theSeed, row + rowIncrement, col + colIncrement, count, rowIncrement, colIncrement);
        }
    } else {
        // Reset the count and keep processing the line
        return checkLine(theSeed, row + rowIncrement, col + colIncrement, 0, rowIncrement, colIncrement);
    }
}

Now, the wrapper methods to check each direction have more functionality and they calculate the beginning of the row, column or diagonal. The methods for the row and column are straightforward, just set to 0 the index for the row or column:

private boolean checkRow(Seed theSeed, int row, int col) {
    return checkLine(theSeed, 0, col, 0, 1, 0);
}

private boolean checkColumn(Seed theSeed, int row, int col) {
    return checkLine(theSeed, row, 0, 0, 0, 1);
}

For the diagonals, we need to calculate the starting indexes. We are at the start of the diagonal when the row index or column index are in the edge, so we calculate the minimum distance to the edge and increase or reduce the indexes that amount:

private boolean checkForwardDiagonal(Seed theSeed, int row, int col) {
    int minDistanceToEdge = Math.min(row, col);
    return checkLine(theSeed, row - minDistanceToEdge, col - minDistanceToEdge, 0, 1, 1);
}

private boolean checkBackwardDiagonal(Seed theSeed, int row, int col) {
    int minDistanceToEdge = Math.min(ROWS - 1 - row, col);
    return checkLine(theSeed, row + minDistanceToEdge, col - minDistanceToEdge, 0, -1, 1);
}

The hasWon method can now use the wrapper functions to check only the row, column and diagonals of the last move:

public boolean hasWon(Seed theSeed, int row, int col) {
    return checkRow(theSeed, row, col) ||
           checkColumn(theSeed, row, col) ||
           checkForwardDiagonal(theSeed, row, col) ||
           checkBackwardDiagonal(theSeed, row, col);
}