Evaluation function for Tic-Tac-Toe

Problem

Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

Players take turns placing characters into empty squares ' '.
The first player A always places 'X' characters, while the second player B always places 'O' characters.
'X' and 'O' characters are always placed into empty squares, never on filled ones.
The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Examples

Example 1:

$$ grid = \begin{bmatrix} \colorbox{lightgreen} X & . & . \\ . & \colorbox{lightgreen} X & . \\ \ O & O & \colorbox{lightgreen} X \end{bmatrix} $$

1
2
3
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

$$ grid = \begin{bmatrix} X & X & \colorbox{lightgreen} O \\ X & \colorbox{lightgreen} O & . \\ \colorbox{lightgreen} O & . & . \end{bmatrix} $$

1
2
3
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

$$ grid = \begin{bmatrix} X & X & O \\ O & O & X \\ X & O & X \end{bmatrix} $$

1
2
3
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

Solution

Method 1 - Run the simulation

Here are the key points:

Initialization and Moves: Each move is valid and alternates between player A and player B.
Winning Condition: The game checks if any row, column, or diagonal has the same character (‘X’ or ‘O’) repeated three times.
End Conditions:
- Win: One player wins if they have three of their marks in a row, column, or diagonal.
- Draw: The game ends in a draw if all cells are filled without a winner.
- Pending: The game is pending if there are still empty cells and no winner.

Here are the steps:

Set Up the Board: A 3x3 grid initialized to empty.
Simulate Moves: Apply each move in the given order.
Check for Winner:
- Check rows, columns, and both diagonals for a win condition after each move.
Determine Result:
- If a win is detected, return the respective player.
- If all cells are filled, return “Draw”.
- Otherwise, return “Pending”.

Code

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public String tictactoe(int[][] moves) {
        char[][] board = new char[3][3];
        boolean playerA = true;

        for (int[] move : moves) {
            int row = move[0];
            int col = move[1];
            board[row][col] = playerA ? 'X' : 'O';
            playerA = !playerA;
        }

        if (checkWinner(board, 'X')) {
            return "A";
        }
        if (checkWinner(board, 'O')) {
            return "B";
        }

        return moves.length == 9 ? "Draw" : "Pending";
    }

    private boolean checkWinner(char[][] board, char c) {
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == c && board[i][1] == c && board[i][2] == c) {
                return true;
            }
            if (board[0][i] == c && board[1][i] == c && board[2][i] == c) {
                return true;
            }
        }
        if (board[0][0] == c && board[1][1] == c && board[2][2] == c) {
            return true;
        }
        if (board[0][2] == c && board[1][1] == c && board[2][0] == c) {
            return true;
        }
        return false;
    }
}

 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
28
class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        board: List[List[str]] = [[''] * 3 for _ in range(3)]
        player_A: bool = True

        for move in moves:
            row, col = move
            board[row][col] = 'X' if player_A else 'O'
            player_A = not player_A

        if self.check_winner(board, 'X'):
            return "A"
        if self.check_winner(board, 'O'):
            return "B"

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

    def check_winner(self, board: List[List[str]], c: str) -> bool:
        for i in range(3):
            if board[i][0] == c and board[i][1] == c and board[i][2] == c:
                return True
            if board[0][i] == c and board[1][i] == c and board[2][i] == c:
                return True
        if board[0][0] == c and board[1][1] == c and board[2][2] == c:
            return True
        if board[0][2] == c and board[1][1] == c and board[2][0] == c:
            return True
        return False

Complexity

⏰ Time complexity: O(m), where m is the number of moves since each move is processed once. Checking for a win condition is constant time O(1).
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Run the simulation#

Code#

Complexity#