Akshay Bhat Akshay Bhat - 4 months ago 15
Java Question

Algorithm to find winner of tic tac toe

What is the best optimal way to find out the winner in 3x3 Tic tac toe game where board is represented by a matrix ? Suggestions please

Answer

I am assuming you are using a double dimension array of Booleans. Since a Boolean can have three values (null, true and false). Since only 2 players can play at any given time, then you only need three values. undefined, player 1 and player 2.

Here is a method that will work with any Boolean array as long as the size is more than 1. It will return true if the trues won, false if the falses won and null if there isn't a winner yet.

public static Boolean getWinner(Boolean[][] grid) {
    if (grid == null)
        return null;
    int size = grid.length;
    if (size == 0)
        return null;
    if (size == 1 && (grid[0][0] != null)) {
        return grid[0][0];
    }
    boolean flag = true;
    // checks horizontal
    for (int index = 0; index <= size - 1; index++) {
        flag = true;
        for (int i = 1; i <= size - 1; i++) {
            if (grid[index][i] != grid[index][i - 1]) {
                flag = false;
                break;
            }
        }
        if (flag)
            return grid[index][0];
    }
    // checks vertical
    for (int index = 0; index <= size - 1; index++) {
        flag = true;
        for (int i = 1; i <= size - 1; i++) {
            if (grid[i][index] != grid[i - 1][index]) {
                flag = false;
                break;
            }
        }
        if (flag)
            return grid[0][index];
    }
    // checks diagonal
    flag = true;
    for (int index = 1; index <= size - 1; index++) {
        if (grid[index][index] != grid[index - 1][index - 1]) {
            flag = false;
            break;
        }
    }
    if (flag)
        return grid[0][0];
    flag = true;
    for (int index = 1; index <= size - 1; index++) {
        if (grid[size - index - 1][index] != grid[size - index][index - 1]) {
            flag = false;
            break;
        }
    }
    if (flag)
        return grid[size - 1][0];
    return null;
}