Akshay Bhat - 1 year ago 100
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

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 `true`s won, `false` if the `false`s 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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download