Design a Tic-tac-toe game that is played between two players on a n x n grid.

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.

Example:
Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.

1	TicTacToe toe = new TicTacToe(3);

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|

Could you do better than O(n^2) per move() operation? Could you trade extra space such that move() operation can be done in O(1)? Could you trade extra space such that move() operation can be done in O(1)?

Tic-Tac-Toe Game Design with O(1) Move

Your TicTacToe object will be instantiated and called as such:

1
2

TicTacToe* obj = new TicTacToe(n);
int param_1 = obj->move(row,col,player);

TicTacToe* obj = new TicTacToe(n);
int param_1 = obj->move(row,col,player);

When a player makes a move, we need to check if he/she wins the game. A simple solution is to check O(N^2) grid for horizontal, vertical and two diagonals to see if they are all occupied by this player. However, a better solution that has O(1) time would be to trade space for time. That is, we use O(N) space to record the number of each players in each row, column and two diagonals.

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

class TicTacToe {
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) {
        board.resize(n);
        rowc[0].resize(n);
        rowc[1].resize(n);
        colc[0].resize(n);
        colc[1].resize(n);
        d[0][0] = 0;
        d[0][1] = 0;
        d[1][0] = 0;
        d[1][1] = 0;
        for (int i = 0; i < n; ++ i) {
            board[i].resize(n);
            rowc[0][i] = 0;
            rowc[1][i] = 0;
            colc[0][i] = 0;
            colc[1][i] = 0;            
        }
    }
    
    /** 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. */
    int move(int row, int col, int player) {
        board[row][col] = player;
        int n = board.size();
        if (++rowc[player - 1][row] == n) return player;
        if (++colc[player - 1][col] == n) return player;
        if (row == col) {
            if (++d[player - 1][0] == n) return player;
        }
        if (n - row - 1 == col) {
            if (++d[player - 1][1] == n) return player;
        }
        return 0;
    }
private:
    vector<vector<int>> board;
    int d[2][2];
    vector<int> rowc[2];
    vector<int> colc[2];
};

class TicTacToe {
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) {
        board.resize(n);
        rowc[0].resize(n);
        rowc[1].resize(n);
        colc[0].resize(n);
        colc[1].resize(n);
        d[0][0] = 0;
        d[0][1] = 0;
        d[1][0] = 0;
        d[1][1] = 0;
        for (int i = 0; i < n; ++ i) {
            board[i].resize(n);
            rowc[0][i] = 0;
            rowc[1][i] = 0;
            colc[0][i] = 0;
            colc[1][i] = 0;            
        }
    }
    
    /** 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. */
    int move(int row, int col, int player) {
        board[row][col] = player;
        int n = board.size();
        if (++rowc[player - 1][row] == n) return player;
        if (++colc[player - 1][col] == n) return player;
        if (row == col) {
            if (++d[player - 1][0] == n) return player;
        }
        if (n - row - 1 == col) {
            if (++d[player - 1][1] == n) return player;
        }
        return 0;
    }
private:
    vector<vector<int>> board;
    int d[2][2];
    vector<int> rowc[2];
    vector<int> colc[2];
};

Instead of storing the counters for each player, We can alternatively reduce the space usage to half i.e. increment the counter for player 1 and decrement the counter for player 2. Then we need to check if the absolute value of the counter equals to N.

tic-tac-toe

–EOF (The Ultimate Computing & Technology Blog) —