Find winner in a tic tac toe match [closed]

Question

I know people asked this before but I didn't understand the answers.

Assume you have a char board[3][3] as a parameter in the function and that you need to return 1 if the X's won, -1 if the O's won or 0 if no one won yet OR if it's a tie.

int checkforwin(char board[3][3]);

that's the declaration for the function.

Any idea for non primitive testing for winning by one of the opponents?

Answer 1

There are three approaches to solving the problem of detecting a winner in a tic-tac-toe game. There's the brute force method, the algorithmic method, and the data-driven method.

The brute force method consists of a series of if statements. Since there are only 8 ways to win a tic-tac-toe game, only 8 if statements are needed to determine the winner. Consequently, the brute force method compares well to other methods since it has a relatively small number of lines of code, simple, easy to read code, a relatively small executable size, and fast execution speed. The brute force method is the best method because the game of tic-tac-toe is trivial. A slightly more complicated game, like Connect Four, may require more advanced coding techniques, but tic-tac-toe is best solved with simple if statements.

The algorithmic method has been demonstrated in the other responses to this question. David Syzdek's algorithm is by far the best of the algorithms, but is somewhat of a hybrid solution, since it reduces eight if statements to four if statements through the use of a for loop. Note that his algorithm still has hard-coded indices scattered throughout the code.

The data-driven method uses an initialized data set to abstract the problem, so that the code is fully generic, and all of the messiness is gathered into the data set. Here's what the code looks like using a data-driven solution.

#include <stdbool.h>

typedef struct
{
    int valid;
    int rowA, colA;
    int rowB, colB;
    int rowC, colC;
}
    stPath;

static stPath paths[] =
{
    { true,   0, 0,   0, 1,   0, 2 },   // top row
    { true,   1, 0,   1, 1,   1, 2 },   // middle row
    { true,   2, 0,   2, 1,   2, 2 },   // bottom row
    
    { true,   0, 0,   1, 0,   2, 0 },   // left column
    { true,   0, 1,   1, 1,   2, 1 },   // middle column
    { true,   0, 2,   1, 2,   2, 2 },   // right column
    
    { true,   0, 0,   1, 1,   2, 2 },   // TL to BR diagonal
    { true,   0, 2,   1, 1,   2, 0 },   // TR to BL diagonal
    
    { false,  0, 0,   0, 0,   0, 0 }    // end of list
};

int checkforwin(char board[3][3])
{
    // assumes that board array uses 'X' 'O' and <sp> to mark each position
    
    for (stPath *pptr = paths; pptr->valid; pptr++)
    {
        int a = board[pptr->rowA][pptr->colA];
        int b = board[pptr->rowB][pptr->colB];
        int c = board[pptr->rowC][pptr->colC];
        
        if (a == b && b == c && a != ' ')
            return (a == 'X') ? 1 : -1;
    }
    
    return 0;    // no winner yet
}

Note that I'm not advocating a data-driven solution to this particular problem, since the problem itself is too trivial to warrant a data-driven solution.

Answer 2

I would probably do something like the following. You could use if statements without the for loops, however this reduces the size of the source code.

// board[3][3]:
//    [0][0] | [1][0] | [2][0]
//    -------+--------+-------
//    [0][1] | [1][1] | [2][1]
//    -------+--------+-------
//    [0][2] | [1][2] | [2][2]
//
int checkforwin(char board[3][3])
{
    int x;

    for(x = 0; x < 3; x++)
    {
      // check vertical lines
      if ((board[x][0] != '\0') && 
          (board[x][0] == board[x][1]) && 
          (board[x][0] == board[x][2]))
         return(board[x][0] == 'O' ? -1 : 1);

      // check horizontal lines
      if ((board[0][x] != '\0') &&
          (board[0][x] == board[1][x]) && 
          (board[0][x] == board[2][x]))
         return(board[0][x] == 'O' ? -1 : 1);
    };

    // check top left to bottom right diagonal line
    if ((board[0][0] != '\0') && 
       (board[0][0] == board[1][1]) && 
       (board[0][0] == board[2][2]))
      return(board[0][0] == 'O' ? -1 : 1);

    // check bottom left to top right diagonal line
    if ((board[2][0] != '\0') && 
       (board[2][0] == board[1][1]) &&
       (board[0][0] == board[0][2]))
      return(board[2][0] == 'O' ? -1 : 1);

    // no winner
    return 0;
}