How to Design a Tic-Tac-Toe Game?

  • 时间:2020-09-24 11:41:27
  • 分类:网络文摘
  • 阅读:89 次

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-150x150 How to Design a Tic-Tac-Toe Game? algorithms c / c++ code design questions games

tic-tac-toe

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
The Brace Expansion Algorithms using Breadth First Search or Dep  Coding Exercise: Sum of Digits in the Minimum Number  Javascript Coding Exercise: The QuickSort Implementation in Java  In-place Run-Length String Compressions using C++  Algorithms to Compute the Factor Combinations for An Integer usi  How and Why You Should Use Infographics On Your Blog  How to Make Your “Contact Us” Page Kick Ass  The A to Z of Content Marketing: Habits Every Content Marketer S  Keeping the Flame Going: How to Rock a Steady Job and Still Have  How to Use Social Media and User-Generated Content to Boost Traf 
评论列表
添加评论