CODEWITHSUNDEEP
calgorithmloops
Ambidextroid
Ambidextroid

Reputation: 69

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

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.

Upvotes: 0

Views: 670

Answers (1)

Prune
Prune

Reputation: 77837

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.

Upvotes: 2

Related Questions