We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. A Chessboard Game
  5. Discussions

A Chessboard Game

  • fsfarsight
     + 2 comments

    I've implemented a DP solution with an matrix of the whole board and print the winning(O) and losing(X) points of the first player: 1. > X X O O X X O O 2. > X X O O X X O O 3. > O O O O O O O O 4. > O O O O O O O O 5. > X X O O X X O O 6. > X X O O X X O O 7. > O O O O O O O O 8. > O O O O O O O X

    In the testcase (8, 8), because moving to both (7, 6) && (6, 7) would cause the Second player to win, the winner should be the Second. However, the expected answer is First.

    Here is the source code:

    // output 1 if current player will win; output -1 if current player will lose
int chessboardGame(int x, int y, vector<vector<int>>& winner) {
    if (x < 1 || x > 8 || y < 1 || y > 8) {
        return 1;
    } else if (winner[x - 1][y - 1] != 0) {
        return winner[x - 1][y - 1];
    }
    winner[x - 1][y - 1] = -1;
    if (chessboardGame(x - 2, y + 1, winner) == -1) {
        winner[x - 1][y - 1] = 1; 
    } else if (chessboardGame(x - 2, y - 1, winner) == -1) {
        winner[x - 1][y - 1] = 1; 
    } else if (chessboardGame(x + 1, y - 2, winner) == -1) {
        winner[x - 1][y - 1] = 1; 
    } else if (chessboardGame(x - 1, y - 2, winner) == -1) {
        winner[x - 1][y - 1] = 1; 
    }
    return winner[x - 1][y - 1];
}

string chessboardGame(int x, int y) {
    vector<vector<int>> winner(8, vector<int>(8));
    /*
    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
            if (chessboardGame(i, j, winner) == 1) {
                cout << "O ";
            } else {
                cout << "X ";
            }
        }
        cout << "\n";
    }
    */
    if (chessboardGame(x, y, winner) == 1) {
        return "First";
    } else {
        return "Second";
    }
}

    Correct me if I am wrong.