Design Tic-Tac-Toe Problem

Problem

Design a Tic-tac-toe game that is played between two players on anxngrid. You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Examples

**Example 1: **

 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
41
42
43
44
45
46


Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]

Output
[null, 0, 0, 0, 0, 0, 0, 1]

Explanation
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up: Could you do better than O(n^2) permove()operation?

Could you get O(1) per move() operation?

Class structure

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


class TicTacToe {

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
    
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
		
    }
}

Solution

Method 1 - Use 2D char array

Here are the steps:

Initialization:
- Create a board with size n x n.
- Use characters ‘X’ and ‘O’ to represent the moves of the two players.
Making a Move:
- Validate the move to ensure it is placed on an empty block.
- Update the board with the player’s move.
- Check if the current move results in a win by evaluating the row, column, primary diagonal, and anti-diagonal containing the move.
Check Win Condition:
- For each move, check the corresponding row, column, and diagonals if they contain all identical marks (X or O).

This ensures that the game accurately tracks moves and winning conditions with each move evaluated in linear time relative to the grid size.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


class TicTacToe {
    private char[][] board;
    private static char X = 'X';
    private static char O = 'O';
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.board = new char[n][n];
        this.n = n;
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        char c;
        if (player == 1) {
            c = X;
        } else {
            c = O;
        }
        if (board[row][col] != 0) {
            // throw error, occupied
            return 0;
        }
        board[row][col] = c;

        if (hasWon(row, col, size, c)) {
            return player;
        }
        return 0;
    }

    private boolean hasWon(int row, int col, char c) {
        // check horizontal
        boolean rowLine = true;
        for (int i = 0; i < n; i++) {
            rowLine = rowLine && (board[i][col] == c);
        }
        if (rowLine) return true;
        
        // check vertical
        boolean colLine = true;
        for (int j = 0; j < n; j++) {
            colLine = colLine && (board[row][j] == c);
        }
        if(colLine) return true;
		
		// is diagonal
		if(row == col) {
			boolean diagLine1 = true;
		    for (int j = 0; j < n; j++) {
                diagLine1 = diagLine1 && (board[j][j] == c);
            }
            if(diagLine1) return true;
		}
		
        // check anti-diagonal
        if (row + col == n - 1) {
            boolean diagLine2 = true;
            for (int j = 0; j < n; j++) {
                diagLine2 = diagLine2 && (board[n - 1 - j][j] == c);
            }
            if(diagLine2) return true;
        }
        return false;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

 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
41
42
43
44
45


class TicTacToe:
    def __init__(self, n: int):
        self.n: int = n
        self.board: List[List[str]] = [[''] * n for _ in range(n)]
        self.X: str = 'X'
        self.O: str = 'O'

    def move(self, row: int, col: int, player: int) -> int:
        c: str = self.X if player == 1 else self.O
        
        if self.board[row][col] != '':
            # invalid move, since the problem guarantees valid moves, we can omit this check
            return 0
        
        self.board[row][col] = c
        
        if self.has_won(row, col, c):
            return player
        
        return 0

    def has_won(self, row: int, col: int, c: str) -> bool:
        # check horizontal
        row_line: bool = all(self.board[row][i] == c for i in range(self.n))
        if row_line:
            return True

        # check vertical
        col_line: bool = all(self.board[i][col] == c for i in range(self.n))
        if col_line:
            return True

        # check diagonal
        if row == col:
            diag_line1: bool = all(self.board[i][i] == c for i in range(self.n))
            if diag_line1:
                return True

        # check anti-diagonal
        if row + col == self.n - 1:
            diag_line2: bool = all(self.board[i][self.n - 1 - i] == c for i in range(self.n))
            if diag_line2:
                return True
        
        return False

Method 2 - Using arrays for rows and cols

The approach optimizes the process of determining the winner by utilizing counters for rows, columns, and diagonals, instead of maintaining the entire n x n board.

Key Observations

Winning Condition: To win Tic-tac-toe, a player must have all their marks in a single row, column, or diagonal.
Optimized Tracking: Instead of tracking each cell, maintain counters for each row, column, and the two diagonals.
Player Identification: Use +1 for Player 1 and -1 for Player 2, making it easy to count and identify winning conditions by the absolute value of the counters.

Steps

Initialization:
- Create arrays to keep count of marks in each row and column (rows and cols).
- Use variables to keep track of the main diagonal and anti-diagonal counts.
Making a Move:
- Update the corresponding row, column, and diagonal counters based on the player’s move.
- Check if the current move results in a win by evaluating if any counter equals n (the size of the grid), after adjusting for the player’s identifier.
Check Win Condition:
- If any row, column, or diagonal counter reaches the absolute value n, the respective player has won.

This ensures that each move and win check operates in constant time, making the implementation highly efficient.

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
41
42
43


public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
	    this.n = n;
        rows = new int[n];
        cols = new int[n];
    }

    /** Player {player} makes a move at ({row}, {col}).
    @param row The row of the board.
    @param col The column of the board.
    @param player The player, can be either 1 or 2.
    @return The current winning condition, can be either:
            0: No one wins.
            1: Player 1 wins.
            2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;

        rows[row] += toAdd;
        cols[col] += toAdd;
        if (row == col) {
            diagonal += toAdd;
        }

        if (col + row == n - 1) {
            antiDiagonal += toAdd;
        }

        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n ||
            Math.abs(diagonal) == n  || Math.abs(antiDiagonal) == n) {
            return player;
        }

        return 0;
    }
}

 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


class TicTacToe {

    int[] rows, cols;
    int d1, d2, n;

    public TicTacToe(int n) {
      rows = new int[n];
      cols = new int[n];
      d1 = 0;
      d2 = 0;
      this.n = n;
    }

    public int move(int row, int col, int player) {
      int val = (player == 1) ? 1 : -1;
      int target = (player == 1) ? n : -n;

      if(row == col) { // diagonal 
        d1 += val;
        if(d1 == target) return player;
      }

      if(row + col + 1 == n) { // anti diagonal 
        d2 += val;
        if(d2 == target) return player;
      }

      rows[row] += val;
      cols[col] += val;

      if(rows[row] == target || cols[col] == target) return player;

      return 0;
    }
}

 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 TicTacToe:
    def __init__(self, n: int):
        self.n: int = n
        self.rows: List[int] = [0] * n
        self.cols: List[int] = [0] * n
        self.diagonal: int = 0
        self.antiDiagonal: int = 0

    def move(self, row: int, col: int, player: int) -> int:
        to_add: int = 1 if player == 1 else -1

        self.rows[row] += to_add
        self.cols[col] += to_add
        if row == col:
            self.diagonal += to_add
        if row + col == self.n - 1:
            self.antiDiagonal += to_add

        if abs(self.rows[row]) == self.n or \
        abs(self.cols[col]) == self.n or \
        abs(self.diagonal) == self.n or \
        abs(self.antiDiagonal) == self.n:
            return player

        return 0

Problem#

Examples#

Class structure#

Solution#

Method 1 - Use 2D char array#

Code#

Method 2 - Using arrays for rows and cols#

Key Observations#

Steps#

Code#

Problem

Examples

Class structure

Solution

Method 1 - Use 2D char array

Code

Method 2 - Using arrays for rows and cols

Key Observations

Steps

Code