Find Winner on a Tic Tac Toe Game

This problem can be solved by keeping track of the game state, specifically the state of each row, column, and diagonal. At each move, we update the state of the corresponding row, column, and diagonal, and check if any of them have reached a winning state. Here is how we can implement it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        # Initiate the rows, columns and diagonals
        rows = [0]*3
        cols = [0]*3
        diag = anti_diag = 0
        n = len(moves)
        # Winning condition
        win = 3 if n%2 == 0 else -3
        # Iterate over moves
        for i, (x, y) in enumerate(moves):
            # Player A corresponds to 1, Player B corresponds to -1
            player = 1 if i%2 == 0 else -1
            # Update the rows, columns, diagonals
            rows[x] += player
            cols[y] += player
            if x == y:
                diag += player
            if x == 2 - y:
                anti_diag += player
            # Check if any player has won
            if win in [rows[x], cols[y], diag, anti_diag]:
                return "A" if player == 1 else "B"
        # Check for draw or pending game
        return "Draw" if n == 9 else "Pending"

In this code, each player move is encoded as 1 for player A and -1 for player B. This makes it easier to determine which player has won, since a row, column, or diagonal will sum to 3 or -3 when a player wins. If there is no winner after all moves have been processed, we check if the game is a draw (all squares filled) or still pending.

There’s an error in the condition checking for a win. The winning condition should be checked after each move instead of checking it at the end of all moves. The mistake is that the check for win is inside the loop of moves but after the updates to the game state for the current move.

A correct version of the function should look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0]*3
        cols = [0]*3
        diag = anti_diag = 0

        for i in range(len(moves)):
            player = 1 if i%2 == 0 else -1
            x, y = moves[i]
            rows[x] += player
            cols[y] += player
            if x == y:
                diag += player
            if x + y == 2:
                anti_diag += player
            if any(abs(line) == 3 for line in [rows[x], cols[y], diag, anti_diag]):
                return "A" if player == 1 else "B"

        return "Draw" if len(moves) == 9 else "Pending"

This function will correctly determine the winner or state of the game at any point in the sequence of moves. If there’s no winner and all spots on the board have been filled, it will return “Draw”. If there’s no winner and spots are still available, it will return “Pending”.

Brute Force Solution

The brute force solution would be to iterate through all the possible winning line combinations every time a player makes a move.

For the Tic Tac Toe game, there are 8 winning line combinations in total: 3 rows, 3 columns, and 2 diagonals.

Here is the Python code for the brute force solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        board = [[' ']*3 for _ in range(3)]

        for i, move in enumerate(moves):
            row, col = move
            # Player A uses 'X', Player B uses 'O'
            board[row][col] = 'X' if i % 2 == 0 else 'O'

        # Check rows and columns
        for i in range(3):
            if board[i][0] == board[i][1] == board[i][2] != ' ':
                return "A" if board[i][0] == 'X' else "B"
            if board[0][i] == board[1][i] == board[2][i] != ' ':
                return "A" if board[0][i] == 'X' else "B"

        # Check diagonals
        if board[0][0] == board[1][1] == board[2][2] != ' ':
            return "A" if board[0][0] == 'X' else "B"
        if board[0][2] == board[1][1] == board[2][0] != ' ':
            return "A" if board[0][2] == 'X' else "B"

        # If no winner and the board is full, it's a draw.
        if len(moves) == 9:
            return "Draw"
        # Otherwise, the game is still pending.
        return "Pending"

The brute force solution iterates through all the moves and fills the board accordingly. Then, it checks each row, column, and diagonal to see if there is a winner. The space complexity is O(1), and the time complexity is O(1) as well, since the size of the board is constant and does not change with the input. However, it’s not as efficient as it could be, because it checks all possibilities after each move, rather than only those influenced by the most recent move.

To go from a brute force solution to an efficient solution, we can take advantage of the structure of the problem. For the Tic Tac Toe game, instead of checking all the rows, columns, and diagonals after every move, we can instead update and check only the row, column, and (if applicable) diagonal affected by the most recent move.

In the brute force solution, we populate the entire game board and check all possible winning combinations after each move. This approach involves redundant operations because the status of many lines won’t change after a new move unless the new move happens to be on them.

In an optimized solution, we use the position of the latest move to update our records and make the judgement. More specifically, we maintain counters for each row, column, and the two diagonals. After each move:

  • We increment or decrement the corresponding row and column counter based on the player (Player ‘A’ increments the counter and Player ‘B’ decrements the counter).
  • If the move is on one of the diagonals, we update the corresponding diagonal counter as well.
  • We then check if any of the updated counters have reached the winning value (3 or -3), and if so, we know which player has won.

This approach significantly reduces the number of operations needed to judge the result after each move. The space complexity remains O(1), and the time complexity is also O(1) for each move, which is a significant improvement from the brute force solution.

The main idea here is to maintain the game state dynamically and make the judgement based on the latest move only, rather than checking the whole board every time. It’s a conceptually simple optimization, but quite effective. It is also a good example of a general approach that can be applied in many other situations: updating your results dynamically based on the latest operation, instead of re-computing everything from scratch.

Q&A

Solving this problem gives a great basis for another popular classical problem “Placing N Queens on the Chess board”.

Absolutely. The Tic Tac Toe problem shares similar characteristics to the N Queens problem. Both problems require checking conditions on rows, columns and diagonals. This is exactly what we do in the N Queens problem where we need to place N queens on an NxN chessboard such that no two queens threaten each other.

The N Queens problem is generally solved using backtracking. It’s a depth-first search algorithm for finding all solutions to some computational problem, notably constraint satisfaction problems. It incrementally places queens on the board, checks if the current board is safe, and then recursively adds safe queens.

These problems emphasize on the importance of understanding the rules of the game or constraints. Once we know these constraints, we can create an algorithm that respects these constraints and finds a solution.

The description is poor. It says “In case the game ends in a draw return “Draw””, but in a case like moves = [[1,1],[2,0],[0,2],[0,1],[0,0],[2,2],[2,1],[1,2]], that’s “Draw” rather than “Pending”, because there’s no way to win and any next move doesn’t matter. However, the expected result is “Pending”.

Indeed, the phrasing of the problem statement seems to cause some confusion.

According to standard Tic-Tac-Toe rules, a game is considered a “Draw” when all squares are filled and there’s no winner. However, in this problem, as you observed, “Draw” is returned only when all squares are filled, regardless of whether or not a win is still possible with remaining moves.

In cases like your example, where a win is no longer possible but not all squares are filled, it continues to be marked as “Pending”. This approach might differ from some common interpretations of Tic-Tac-Toe rules, but it’s the specific instruction given in this problem statement.

It’s crucial to read problem statements carefully and make sure your solution adheres to the provided specifications, even when they may differ from standard or intuitive rules.

To design a Tic Tac Toe game, you have to at first judge who wins. Use “012345678” to denote the positions in board. There are exactly 8 lines to observe; each line L has 3 elements, say x0, x1, x2 which are using number 0, 1 or 2 denoting its status: 1 for player ‘X’, 2 for player ‘O’ and 0 for none.

X12 3X5 OOX “A”

XXO XO5 O78 “B”

XXO OOX XOX “Draw”

Consider the judge function f(x0,x1,x2)=x0x1+x1x2+x2x0f(x_0, x_1, x_2)=x_0x_1+x_1x_2+x_2x_0f(x 0 ​ ,x 1 ​ ,x 2 ​ )=x 0 ​ x 1 ​ +x 1 ​ x 2 ​ +x 2 ​ x 0 ​

if f=3f=3f=3 then player ‘X’ wins, if f=12f=12f=12 then player ‘O’ wins, otherwise check all other lines.

While your idea of having a function to judge the winner based on values of three spots is a sound strategy, the calculation of f(x0,x1,x2)=x0x1+x1x2+x2x0 does not fully cover all scenarios in the game.

For example, consider a line where x0 = 1, x1 = 2, and x2 = 1 (denoting a row like ‘XOX’). The calculation would be f = 1*2 + 2*1 + 1*1 = 4. This does not fall into either f = 3 or f = 12, yet we can’t decide a winner based on this line.

In Tic Tac Toe, each of the eight lines (3 rows, 3 columns, and 2 diagonals) represents a potential win condition. A more straightforward way is to simply check each line to see if all spots are ‘X’ or all are ‘O’. If a line meets this condition, we can directly determine the winner.

If you want to stick with a mathematical function, consider encoding ‘X’ and ‘O’ differently, like ‘X’ as 1 and ‘O’ as -1. Empty spots can be 0. Then, for each line, sum the encoded values f = x0 + x1 + x2. If f = 3, ‘X’ wins; if f = -3, ‘O’ wins. Other values mean that line is either still in play or drawn. You would check all lines and if none of them yields a winner, then either the game is still in progress or it’s a draw depending on whether there are any empty spots left.

Totally 8 ways to win: placement of 3 same characters on:

3 rows; 3 cols; 2 diagonals. Therefore we can use arrays of size 3 to accumulate the count of same characters on rows and cols; use int variables to accumulate the count of same characters on diagonals.

Note:

D1 and D2 refer to main and skew diagonals respectively; Use r == c and r + c == 2 to judge main and skew diagonals.

Indeed, your strategy is correct and aligns with a common approach to solve this problem.

Here’s a Python code snippet that implements your logic. In this code, the positions of moves are recorded separately for player A and B. After each move, it checks if the current player meets any winning condition:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        # Initialize the counters for rows, cols, and diagonals
        rows, cols = [0]*3, [0]*3
        d1 = d2 = 0

        # Determine the current player
        player = 1 if len(moves) % 2 == 1 else -1

        for r, c in moves[-1::-2]:
            rows[r] += player
            cols[c] += player
            if r == c: d1 += player
            if r + c == 2: d2 += player

        # Check if the current player wins
        if 3 in (rows + cols + [d1, d2]): return "A"
        if -3 in (rows + cols + [d1, d2]): return "B"

        # Check if the game is pending or draw
        return "Pending" if len(moves) < 9 else "Draw"

The variable player is used to represent the current player (1 for A and -1 for B). After each move, the row and column counters of the current player are updated. If the move is on one of the diagonals, the corresponding diagonal counter is updated as well. After each update, it checks if there is any winning line for the current player. The game is considered pending if no winning line is found and the number of moves is less than 9; otherwise, it’s a draw.