-3

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

Akshay Bhat
  • 236
  • 3
  • 16

2 Answers2

3

These functions should do it. I had used a character array when I made my tic-tac-toe.

int  rowcheck(char ch[3][3])
{
    int i;
    char ans;
    for(i=0;i<3;i++)
    {
        if(ch[i][0]==ch[i][1] && ch[i][1]==ch[i][2])
        {
            ans=ch[i][0];
            break;
        }
    }
    if(ans=='O')
    return 1;
    else if(ans=='X')
    return 2;
    else
    return 0;
}
int  colcheck(char ch[3][3])
{
    int i;
    char ans;
    for(i=0;i<3;i++)
    {
        if(ch[0][i]==ch[1][i] && ch[1][i]==ch[2][i])
        {
            ans=ch[0][i];
            break;
        }
    }
    if(ans=='O')
    return 1;
    else if(ans=='X')
    return 2;
    else
    return 0;
}
int  diagcheck(char ch[3][3])
{
    char ans;
    if(ch[0][0]==ch[1][1] && ch[1][1]==ch[2][2])
    ans=ch[0][0];
    if(ch[0][2]==ch[1][1] && ch[1][1]==ch[2][0])
    ans=ch[0][2];
    if(ans=='O')
    return 1;
    else if(ans=='X')
    return 2;
    else
    return 0;
}

Player 1 wins if 1 is returned else Player 2 wins. Check out this link for more info:

https://keepkoding.wordpress.com/2015/12/12/everybody-knows-tic-tac-toe/

Mind you, this link is in C++ but the logic is simple to understand.

Vaibhav Bajaj
  • 1,934
  • 16
  • 29
  • yes I understood the logic thanks !!! – Akshay Bhat Jul 21 '16 at 06:48
  • But is there any better way like with less time complexity ? – Akshay Bhat Jul 21 '16 at 06:49
  • 3
    If you need to check equality, I see no better way than this. Also, considering you are playing Tic Tac Toe, I see no reason to reduce time complexity. But if you must, the easiest way would be not to do such checks till at least 6 moves have been done. Considering only 9 moves can be done, this reduces more than 2/3rd of the time. If you liked my answer, please upvote it. – Vaibhav Bajaj Jul 21 '16 at 06:51
  • 1
    @AkshayBhat Umm maybe you should check my answer, for a more efficient algorithms that can give you the winner for an array of any given size. – nick zoum Jul 21 '16 at 07:18
  • 1
    @nickzoum Yeah, a bit of generalization is great. This was one of my first games that I just pasted the code of and at that point in time, I was just getting started with programming. It was in the later games that I started generalizations and proper comments. Thanks for the tip and feel free to check out my blog for other games like Snake or a Sudoku Solver. – Vaibhav Bajaj Jul 21 '16 at 07:29
  • Thank you guys !! It worked I had used enums and successfully modified it thanks for your valuable suggestions – Akshay Bhat Jul 21 '16 at 11:38
3

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 won, false if the false 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;
}

Sidenote: If you are using an Enum instead of a Boolean then you only need to change the two Booleans on the first line and all the == with equals

nick zoum
  • 7,216
  • 7
  • 36
  • 80