Problem Description

You are given an 8 x 8 chessboard, represented as a 2D array board. Each cell contains one of the following characters:

• '.' (an empty square)
• 'B' (a black disc)
• 'W' (a white disc)

• rMove (row index of the move)
• cMove (column index of the move)
• color (the color of the disc you want to place, either 'B' or 'W')

• The chosen cell is empty (i.e., contains '.').
• There exists at least one direction (horizontal, vertical, or diagonal) such that:
  • There is at least one opponent's disc immediately next to the placed disc in that direction.
  • Continuing in that direction, there is a straight line of one or more opponent's discs, ending with one of the player's own discs.

Thought Process

The key challenge is to check all eight possible directions from the given cell to see if placing the disc would "capture" any opponent discs, as per Othello's rules.
A naive approach would be to examine each direction one by one, checking for the required pattern: at least one opponent's disc, followed by the player's own disc, without any empty cells in between.
To optimize, rather than simulating the entire board or flipping discs, we only need to check if such a pattern exists in any direction. This keeps the code efficient and easy to understand.
Using concise loops and early exits helps avoid unnecessary checks once a valid direction is found.

Solution Approach

We solve the problem by following these steps:

1. First, check if the cell at (rMove, cMove) is empty. If not, the move is illegal.
2. For each of the 8 possible directions (up, down, left, right, and the 4 diagonals):
   • Move one step in the current direction. If the next cell is not the opponent's disc, skip this direction.
   • Continue moving in the same direction, counting the number of opponent discs.
   • If we encounter the player's own disc after at least one opponent disc (and before hitting the edge or an empty cell), the move is legal in this direction.
3. If any direction is legal, return True. If none are, return False.

We use a list of direction vectors to represent all possible directions, making the code clean and easy to extend. This approach ensures we efficiently check each direction without redundant work.

Example Walkthrough

Suppose we have the following board (simplified for clarity):

    . B .
    B W .
    . . .
    

1. Cell (0,0) is empty, so we can proceed.
2. Check all directions. Let's try direction (1,1) (down-right diagonal):
   • Cell (1,1) contains 'W' (not opponent), so skip.
3. Try direction (1,0) (down):
   • Cell (1,0) contains 'B' (opponent), so continue.
   • Cell (2,0) is empty, so this direction is invalid.
4. Try direction (0,1) (right):
   • Cell (0,1) contains 'B' (opponent), so continue.
   • Cell (0,2) is empty, so this direction is invalid.
5. Try direction (1,-1) (down-left):
   • Cell (1,-1) is out of bounds, skip.
6. After checking all directions, none are valid, so the move is not legal.

If we try rMove = 2, cMove = 0, color = 'W':

• Direction (-1,0) (up): Cell (1,0) is 'B' (opponent), continue to (0,0) which is empty, so invalid.
• Direction (-1,1) (up-right): (1,1) is 'W' (own), but no opponent in between, so invalid.
• Direction (0,1) (right): (2,1) is empty, so invalid.
• All directions checked, no valid move.

Only if a direction has at least one opponent disc followed by our own disc is the move legal.

Time and Space Complexity

Brute-force Approach:
A brute-force approach might check every possible move for every cell, leading to O(N^2 * D * N) where N is the board size and D is the number of directions. This is unnecessary for this problem.

Optimized Approach:
Our approach checks up to 8 directions, and for each direction, at most O(N) steps (since the board is 8x8, that's at most 8 steps per direction). So the time complexity is O(8 * 8) = O(1) (since the board size is fixed).
Space complexity is O(1) as we use only a few variables.

Summary

To determine if a move is legal in Othello, we check all eight directions for the required pattern: a contiguous line of opponent discs ending with the player's own disc. By using direction vectors and efficient loops, we ensure a concise and effective solution. The key is to validate the move in each direction, returning true as soon as a valid direction is found, keeping both time and space usage minimal.

Code Implementation

class Solution:
    def checkMove(self, board, rMove, cMove, color):
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
                      (-1, -1), (-1, 1), (1, -1), (1, 1)]
        n = 8
        opponent = 'B' if color == 'W' else 'W'
        if board[rMove][cMove] != '.':
            return False
        for dr, dc in directions:
            i, j = rMove + dr, cMove + dc
            count = 0
            while 0 <= i < n and 0 <= j < n and board[i][j] == opponent:
                i += dr
                j += dc
                count += 1
            if count >= 1 and 0 <= i < n and 0 <= j < n and board[i][j] == color:
                return True
        return False
      

class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
        char opponent = (color == 'W') ? 'B' : 'W';
        int n = 8;
        if (board[rMove][cMove] != '.') return false;
        for (auto dir : dirs) {
            int i = rMove + dir.first, j = cMove + dir.second, count = 0;
            while (i >= 0 && i < n && j >= 0 && j < n && board[i][j] == opponent) {
                i += dir.first;
                j += dir.second;
                count++;
            }
            if (count >= 1 && i >= 0 && i < n && j >= 0 && j < n && board[i][j] == color)
                return true;
        }
        return false;
    }
};
      

class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
        char opponent = (color == 'W') ? 'B' : 'W';
        int n = 8;
        if (board[rMove][cMove] != '.') return false;
        for (int[] dir : dirs) {
            int i = rMove + dir[0], j = cMove + dir[1], count = 0;
            while (i >= 0 && i < n && j >= 0 && j < n && board[i][j] == opponent) {
                i += dir[0];
                j += dir[1];
                count++;
            }
            if (count >= 1 && i >= 0 && i < n && j >= 0 && j < n && board[i][j] == color)
                return true;
        }
        return false;
    }
}
      

var checkMove = function(board, rMove, cMove, color) {
    const dirs = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]];
    const n = 8;
    const opponent = color === 'W' ? 'B' : 'W';
    if (board[rMove][cMove] !== '.') return false;
    for (let [dr, dc] of dirs) {
        let i = rMove + dr, j = cMove + dc, count = 0;
        while (i >= 0 && i < n && j >= 0 && j < n && board[i][j] === opponent) {
            i += dr;
            j += dc;
            count++;
        }
        if (count >= 1 && i >= 0 && i < n && j >= 0 && j < n && board[i][j] === color)
            return true;
    }
    return false;
};