Tic Tac Toe getWinner() method logic for a grid of any size nxn

Question

I have a college assignment in which I have to make a Tic Tac Toe game work. Some of the code has been provided by my instructor like method signatures etc. Now the rules for this particular project state that a player wins if they get n consecutive spaces on an nxn grid. So 3 for 3x3, 5 for 5x5, etc. Now I got it to work for a 3x3 grid by kind of hard coding it.

Please have a look at how it is done in my code. Now I check if 3 cells contain the same player (X or O). But I don't know how to generalize my method as n increases.

package tictactoe;

/**
 * An implementation of the TicTacToeGame interface.
 * 
 * ATTENTION STUDENTS: You MUST use exactly this class specification. Do not 
 * rename the class, and do not remove the "implements TicTacToeGame", or
 * you will receive no credit for your submission.
 */
public class TicTacToe implements TicTacToeGame {
    int size;
    String whoseTurn = "X";//X,O,""
    String[] board;
    int count;
    /**
     * Constructs a new instance, implementing the TicTacToeGame interface.
     * 
     * ATTENTION STUDENTS: You MUST use exactly this signature for your constructor.
     * Do not rename the class and do not change the argument, or you will receive
     * no credit for your submission.
     * 
     * @param n the length and width of the board; n >= 3
     */
    public TicTacToe(int n) {
        size = n*n;
        board = new String[size];
        resetBoard();
        count = 0;
    }

    @Override
    public int getN() {
        return size;
    }

    @Override
    public String toString() {
        String result = "";
        int ctr = 1;
        for(int i = 0; i < size; i++){
            result += board[i];
            if(ctr % Math.sqrt(size) == 0)
                result += '\n';
            ctr++;  
        }
        return result;
    }

    @Override
    public String getWinner() {
        int len = (int)(Math.sqrt(size));
        int diag = len - 1;
        int antiDiag = len + 1;
        for(int i = 0; i < (size - len); i++){
            if((board[i].equals("X")) && (board[i+1].equals("X")) && (board[i+2].equals("X")))
                return "X";
            if((board[i].equals("O")) && (board[i+1].equals("O")) && (board[i+2].equals("O")))
                return "O";

            if((board[i].equals("X")) && (board[i+len].equals("X")) && (board[i+2*len].equals("X")))
                return "X";
            if((board[i].equals("O")) && (board[i+len].equals("O")) && (board[i+2*len].equals("O")))
                return "O";

            if((board[diag].equals("X")) && (board[2*diag].equals("X")) && (board[3*diag].equals("X")))
                return "X";
            if((board[diag].equals("O")) && (board[2*diag].equals("O")) && (board[3*diag].equals("O")))
                return "O";

            if((board[antiDiag].equals("X")) && (board[2*antiDiag].equals("X")) && (board[3*antiDiag].equals("X")))
                return "X";
            if((board[antiDiag].equals("O")) && (board[2*antiDiag].equals("O")) && (board[3*antiDiag].equals("O")))
                return "O";
        }
        return "";
    }

    @Override
    public String getCurrentPlayer() {
        while(count < size)
            return whoseTurn;
        return "";
    }

    @Override
    public boolean isValidMove(int space) {
        if((count<(size)) && (board[space].equals(" ")))
            return true;                

        whoseTurn = "";
        return false;

    }

    @Override
    public void move(int space) throws IllegalArgumentException {
        board[space] = this.getCurrentPlayer();
        if(whoseTurn.equals("X"))
            whoseTurn = "O";
        else
            whoseTurn = "X";

        count++;        

    }
    private void resetBoard(){
        for(int i = 0; i < size; i++)
            board[i] = " ";
    }

}

Answer 1

You should declare the variables by using the smallest scope that is needed. By omitting the scope specifier (private,public etc) the variable can be accessed by the classes which are in the same package.

So for your class you should declare them private.

---

If the name of a method implies something like getN() one expect to get exactly that what is implied by the name. You are returning size which is n * n. You should store the n which is passed inside the constructor and return it in this method.

Storing n will help you a lot more than only for this method. Every time you are using Math.sqrt(size) you could just use n instead.

---

Using braces {} for single if statement or single line loop statements will make your code less error prone.

---

You don't use the isValidMove() method. In addition one wouldn't expect for a invalid move that the next player would become "".

You need to implement this method and it should be called first at the move() method and if it returns false you should throw an IllegalArgumentException.

---

The getCurrentPlayer() method doesn't need a while loop. A simple if statement would be enough.

---

For the getWinner() method you should consider to store the last player in a variable. In this way you wouldn't need to check for .Equals("X") nor .Equals("O").

If you also store the last move, you don't need the checks for diagonal lines if the last move isn't in the middle or in the corners.

Assuming a 5x5 grid and player X will make his move

X _ _ _ _    _ _ _ _ _    _ _ _ _ _
_ _ _ _ _    _ _ _ _ _    _ _ _ _ _
_ _ _ _ _    _ X _ _ _    _ _ X _ _
_ _ _ _ _    _ _ _ _ _    _ _ _ _ _
_ _ _ _ _    _ _ _ _ _    _ _ _ _ _
    1            2            3

• For the first example you need to check horizontal and vertical based on the moves position and the diagonal from the upper left corner to the lower right corner.

• For the second example you need to check only horizontal and vertical.

• For the third example you need to check horizontal, vertical and both diagonals.

The horizontal check

For the horizontal check we need the current row where the move had been made. This row can be computed by dividing the current move by n. To get the first position of this row we multiply the row by n to get the start position of the checking loop.

int startPosition = (lastMove / n) * n;  

You need to keep in your mind that by dividing 2 int you will get an int back.

Let us check this for examples

Example 1:

startPosition = (0 / 5) * 5 == 0

Example 2:

startPosition = (11 / 5) * 5 == 10

Example 3:

startPosition = (12 / 5) * 5 == 10  

So now we have a starting position for the horizontal checking loop we can add a method to check the horizontal line. In the loops body we will check if the current position of the board does not equal the last player so we can return early.

Private boolean isHorizontalWin(int lastMove, String lastPlayer) {
    int startPosition = (lastMove / n) * n == 0
    for (int i = startPosition; i < startPosition + n; i++) {
        if (!board[i].equals(lastPlayer)) {
            return false;
        }
    }
    return true;
}  

The vertical check

For the vertical check we need the current column. This column we can compute by subtracting n from the current move until the result is < n. Let us add a method for this.

private int getCurrentColumn(int lastMove) {
    while (lastMove >= n) {
        lastMove -= n;
    }
    return lastMove;
}  

This is now the starting position for the vertical checking loop. The iterating variable needs to be incremented by n.

But what is the ending condition?

Example 1:

• we have a startPosition == 0 and the last check should be performed at board[20]

Example 2:

• we have a startPosition == 1 and the last check should be performed at board[21]

Example 3:

• we have a startPosition == 2 and the last check should be performed at board[22]

So for all three examples:

for (int i = startPosition; i < size ; i += n) {  

}  

The diagonal check(s)

Here the starting positions are clear. It is the upper left corner so 0 and the upper right corner so n - 1.

If we loop from the upper left to the lower right, the last position to check is size -1.

If we loop from the upper right to the lower left, the last position to check is size - n.

Let us use new samples for getting the value of which we need to increment the iterating variable.

n == 3

0 1 2
3 4 5
6 7 8  

Here if we check upper left to lower right, we need to increment by 4. From upper right to lower left we need to increment by 2.

n == 5

 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

Here if we check upper left to lower right, we need to increment by 6. From upper right to lower left we need to increment by 4.

Again we see a pattern:

upper left to lower right: n + 1
upper right to lower left: n - 1

---

You need, for implementing the missing points, to add methods for

• checking if the move is a special move, in other words

  • does the last move needs a winning check for the upper left to lower right diagonal
  • does the last move needs a winning check for the upper right to lower left diagonal

• checking if the current player has

  • vertically won
  • left to right diagonal won
  • right to left diagonal won

This would lead to the refactored getWinner() method which could look like

public String getWinner() {
   if(isHorizontalWin(lastMove, lastPlayer)) {
       return lastPlayer;
   }
   if(isVerticalWin(lastMove, lastPlayer)) {
       return lastPlayer;
   }
   if(isLeftToRightCheckNeeded(lastMove) && isLeftToRightWin(lastPlayer)) {
       return lastPlayer;
   }
   if(isRightToLeftCheckNeeded(lastMove) && isRightToLeftWin(lastPlayer)) {
       return lastPlayer;
   }
   return "";
}  

Answer 2

There are bugs in your implementation.

For the 3x3 case, try 1, 0, 2, 4, 3 and then call getWinner(). Your program will return "X" as the winner because X has 1, 2, 3. It doesn't realize that 3 is a different row from 1 and 2.

Checking isValidMove() with an invalid move makes the whoseTurn variable incorrect.

Your antiDiag check is incorrect, as you never check 0 (the first square in the diagonal) but do check 12 (outside the board). Note that I find this name confusing, as your antiDiag is the one that runs from the top left to the bottom right. I would describe the other diagonal as the antidiagonal.