Problem Description

You are playing a game on an 8x8 board similar to Reversi/Othello. The board contains three types of cells:

• . represents a free/empty cell
• W represents a white piece
• B represents a black piece

You want to place a piece of your color (color) at position (rMove, cMove). However, this move is only legal if it creates a "good line."

A good line is defined as:

• A line (horizontal, vertical, or diagonal) of 3 or more cells
• The two endpoints must be the same color
• All cells between the endpoints must be the opposite color
• No free cells (.) can be in the middle of the line

When you place your piece at (rMove, cMove), it becomes one endpoint of the good line. The other endpoint must already exist on the board in the same color as your piece.

For example, if you're playing black (B) and want to place at position X:

• Valid: B W W X → becomes B W W B (a good line of length 4)
• Valid: B W X → becomes B W B (a good line of length 3)
• Invalid: B . W X → has a free cell in the middle
• Invalid: B X → only 2 cells, need at least 3

Given the board state, the position where you want to move (rMove, cMove), and your color, determine if placing a piece at that position would be a legal move by checking if it would form at least one good line in any of the 8 directions (horizontal, vertical, or diagonal).

Return true if the move is legal, false otherwise.

Intuition

To check if a move is legal, we need to verify if placing our piece at (rMove, cMove) would create at least one good line in any direction.

From the position where we want to place our piece, we can extend in 8 possible directions: up, down, left, right, and the four diagonals. Each direction can be represented by a pair of offsets (a, b) where a and b can be -1, 0, or 1 (excluding the case where both are 0, which means no movement).

For each direction, we start from (rMove, cMove) and move step by step in that direction. As we move:

1. We count how many cells we've traversed (cnt)
2. We check what type of cell we encounter at each step

The key insight is that for a valid good line:

• We must first pass through one or more cells of the opposite color
• Then we must reach a cell of our own color
• The total length must be at least 3 (including our starting position)

So when traversing in a direction, if we encounter:

• A cell of our own color AND we've already moved at least 2 steps (cnt > 1), we've found a valid good line
• An empty cell (.) or our own color too early (when cnt <= 1), this direction won't form a good line, so we stop checking this direction
• A cell of the opposite color, we continue moving in that direction

We only need to find one valid good line in any of the 8 directions to confirm the move is legal. If we check all directions and don't find any good line, the move is illegal.

Solution Approach

The solution uses a brute-force enumeration approach to check all 8 possible directions from the target position.

We iterate through all possible direction vectors using two nested loops where a and b range from -1 to 1. This gives us 9 combinations, but we skip the case where both a = 0 and b = 0 (no movement), leaving us with 8 directions:

• Horizontal: (-1, 0) and (1, 0)
• Vertical: (0, -1) and (0, 1)
• Diagonal: (-1, -1), (-1, 1), (1, -1), and (1, 1)

For each direction (a, b):

1. Initialize position and counter: Start from (rMove, cMove) and set cnt = 0 to track the number of cells traversed.

2. Traverse in the current direction: Use a while loop to move step by step:

   • Check boundaries: 0 <= i + a < 8 and 0 <= j + b < 8
   • Increment counter: cnt += 1
   • Update position: i, j = i + a, j + b

3. Check for valid good line: At each step, examine the current cell board[i][j]:

   • If cnt > 1 and board[i][j] == color: We've found a cell of our color after passing through at least one other cell. This forms a valid good line, so return True.
   • If board[i][j] is either our color (when cnt <= 1) or an empty cell .: This direction cannot form a good line, so break and try the next direction.
   • Otherwise (the cell is the opposite color): Continue traversing in this direction.

4. Return result: If no valid good line is found after checking all 8 directions, return False.

The time complexity is O(1) since the board size is fixed at 8×8, and we check at most 8 directions with at most 7 steps each. The space complexity is also O(1) as we only use a constant amount of extra variables.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Board (5x5 for simplicity):

  0 1 2 3 4
0 . . . . .
1 . B W W .
2 . . . . .
3 . . . . .
4 . . . . .

• We want to place a Black piece (B) at position (1, 4)
• So rMove = 1, cMove = 4, color = 'B'

Step-by-step execution:

We'll check all 8 directions from position (1, 4):

1. Direction (-1, -1) - diagonal up-left:

   • Start at (1, 4), cnt = 0
   • Move to (0, 3): cnt = 1, board[0][3] = '.' (empty)
   • Break immediately (empty cell found)
   • Result: No good line

2. Direction (-1, 0) - up:

   • Start at (1, 4), cnt = 0
   • Move to (0, 4): cnt = 1, board[0][4] = '.' (empty)
   • Break immediately
   • Result: No good line

3. Direction (-1, 1) - diagonal up-right:

   • Start at (1, 4), cnt = 0
   • Would move to (0, 5): out of bounds
   • Result: No good line

4. Direction (0, -1) - left:

   • Start at (1, 4), cnt = 0
   • Move to (1, 3): cnt = 1, board[1][3] = 'W' (opposite color)
   • Continue...
   • Move to (1, 2): cnt = 2, board[1][2] = 'W' (opposite color)
   • Continue...
   • Move to (1, 1): cnt = 3, board[1][1] = 'B' (our color!)
   • Since cnt > 1 and we found our color, we have a good line!
   • The line would be: B W W B (length 4)
   • Return True

We found a valid good line in the left direction, so the move is legal. The function returns True without needing to check the remaining directions.

If we had continued checking:

• Directions (0, 1), (1, -1), (1, 0), (1, 1) would all encounter empty cells or go out of bounds quickly

The key insight: We only needed to find ONE valid good line to confirm the move is legal. The left direction gave us the line B W W B after placing our piece, which satisfies all requirements (length ≥ 3, same color endpoints, opposite color in between, no empty cells).

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n) where m is the number of rows and n is the number of columns in the board. Since the board is fixed at 8×8, this simplifies to O(8 + 8) = O(16) = O(1).

The analysis works as follows:

• The outer loops iterate through 8 directions (3×3 grid minus the center), giving us a constant factor of 8
• For each direction (a, b), the while loop traverses at most max(m, n) cells in that direction before hitting a boundary
• In the worst case, we might traverse the entire diagonal, row, or column, which is at most max(m, n) = 8 cells
• Therefore, the total operations are 8 × max(m, n) = O(m + n)

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables a, b for direction iteration
• Variables i, j for current position tracking
• Variable cnt for counting cells traversed
• No additional data structures that scale with input size are used

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly handling the initial position

A common mistake is forgetting that the move position (rMove, cMove) starts as an empty cell (.) and should be treated as if it already contains our color piece when checking for good lines. Some implementations might incorrectly check board[rMove][cMove] or try to validate it before conceptually placing the piece.

Wrong approach:

# Checking if the initial position is valid before "placing" the piece
if board[rMove][cMove] != '.':
    return False

Correct approach: The solution correctly starts traversing from the next position after (rMove, cMove) by immediately moving in the chosen direction before checking the board state.

2. Off-by-one error in counting pieces

Another pitfall is miscounting the number of pieces in the line. The good line must have at least 3 pieces total, including both endpoints. Some might forget to count the initial position or misunderstand when to check cnt > 1.

Wrong approach:

# Checking cnt >= 1 instead of cnt > 1
if cnt >= 1 and board[current_row][current_col] == color:
    return True

This would incorrectly validate a line of only 2 pieces (the placed piece and an adjacent piece of the same color).

Correct approach: The solution uses cnt > 1, ensuring that when we find a piece of our color, we've traversed through at least one cell after the initial position, guaranteeing a minimum line length of 3.

3. Not breaking early when encountering invalid cells

Some implementations might continue checking even after encountering an empty cell or a same-colored piece too early, leading to incorrect validation of lines with gaps.

Wrong approach:

# Only breaking on empty cells, not on early same-color pieces
if board[current_row][current_col] == '.':
    break
# Missing the case where we hit our color when cnt <= 1

Correct approach: The solution correctly breaks when encountering either an empty cell OR our own color when cnt <= 1, ensuring no gaps in the line and preventing invalid 2-piece lines.