Most efficient way to check for a win in a variable size tic-tac-toe grid?

Question

I'm writing a tic-tac-toe game in C where the user chooses the size of the grid. The grid is a 2D array.

I'm having trouble efficiently checking for a win. This is my current idea:

for(int y = 0; y < gridSize; y++)
{
    int lineTotal = 0;
    for(int x = 0; x < gridSize; x++)
    {
        if (grid[x][y] == grid[0][y])
        {
            lineTotal++;
            if (lineTotal == gridSize && grid[x][y] == playersLetter)
            {
                return 1;
            }
        }
    }
}

Which checks every row for a full line. If I want to check each column, I have to swap x and y re-do each loop. I also have to do another loop to check the diagonals, though that's not too hard seeing as there are only two.

My problem is I want to limit the amount of iterations of all the loops to gridSize^2.

This is already gridSize^2. If you repeat this for columns, it will be 2 x gridSize^2, which is still gridSize^2. This will be very fast, even for large arrays. — Bill the Lizard, Nov 28 '18 at 19:48
[Why is constant always dropped from big O analysis?](https://stackoverflow.com/q/22188851/1288) — Bill the Lizard, Nov 28 '18 at 20:01

score 2 · Accepted Answer · answered Nov 28 '18 at 20:00

Make this easier: iterate once through the loops, keeping a count of X vs O in each of your combinations:

int row[gridSize], col[gridSize], diag1, diag2

for(int y = 0; y < gridSize; y++)
int lineTotal = 0;
{
    for(int x = 0; x < gridSize; x++)
    {
        if (grid[x][y] == 'X') {
            row[x]++
            col[y]++
            if (x == y)          diag1++
            if (x+y == gridSize) diag2++
        }
        else if (grid[x][y] == 'XO {
            row[x]--
            col[y]--
            if (x == y)          diag1--
            if (x+y == gridSize) diag2--
        }
    }
}

Now, just check your totals; if any of them reached gridSize, X wins; if -gridSize, O wins.

Perhaps even easier, keep these as running sums through the game. For instance, when X moves into cell x, y:

if (row[x]++ == gridSize)  `X` wins
if (col[x]++ == gridSize)  `X` wins
if (x == y && diag1[x]++ == gridSize)  `X` wins
if (x+y == gridSize and diag[x]++ == gridSize)  `X` wins

Also, note that the first one, especially, is easier if you code the grid with -1, 1, and 0 for X, O, and empty.

Most efficient way to check for a win in a variable size tic-tac-toe grid?

1 Answers1