LeetCode 1958 - Check if Move is Legal

This problem asks us to determine whether a move in a board game is legal based on specific line rules. The board is an 8 x 8 matrix where cells can be empty '.', white 'W', or black 'B'.

leetcodemediumarraymatrixenumeration

LeetCode Problem 1958

Difficulty: 🟡 Medium
Topics: Array, Matrix, Enumeration

Solution

Problem Understanding

This problem asks us to determine whether a move in a board game is legal based on specific line rules. The board is an 8 x 8 matrix where cells can be empty '.', white 'W', or black 'B'. A move is represented by the row and column (rMove, cMove) and the color of the piece to place.

A move is legal if placing the piece at (rMove, cMove) completes a good line. A good line is a line of at least three consecutive cells in a straight line (horizontal, vertical, or diagonal) where the endpoints are the same color, the middle cells are the opposite color, and there are no empty cells in between.

The input constraints are helpful: the board is small and fixed (8 x 8), the move is always on an empty cell, and the color is always valid. Edge cases to consider include placing a piece on the edge of the board, creating lines in multiple directions, and scenarios where the move might appear valid in the middle of a line but not as an endpoint.

The goal is to check all eight directions from the move and confirm if at least one direction forms a good line with the newly placed piece as an endpoint.

Approaches

Brute Force Approach

The brute-force approach involves examining every potential line that could include the new piece. We iterate through all possible line lengths (from 3 up to 8, the size of the board) in each of the eight directions. For each line, we check if it starts and ends with the new color and has only the opposite color in between. This approach is correct but unnecessarily complex because most line checks will quickly fail once we encounter a boundary or the wrong color.

Optimal Approach

The key insight is that a legal move only requires checking lines extending from the move in all directions until we reach a boundary or a mismatch. We do not need to precompute all possible line segments. Instead, for each direction, we step outward from (rMove, cMove) and count consecutive cells of the opposite color. If we reach a cell of the same color after at least one opposite-colored cell, we have found a good line, and the move is legal.

This approach leverages the small fixed board size and the simple rules of line formation, avoiding unnecessary checks.

Approach Time Complexity Space Complexity Notes
Brute Force O(8 * 8) O(1) Checks all line segments starting from every cell, overly redundant
Optimal O(1) O(1) Checks 8 directions from the move, linear in board size, constant for 8x8

Algorithm Walkthrough

  1. Define all eight directions to check: vertical, horizontal, and diagonals.
  2. For each direction (dr, dc), initialize (r, c) to the move's coordinates and move one step in that direction.
  3. Track a count of consecutive cells with the opposite color.
  4. Step along the line until either hitting the board boundary, an empty cell, or a cell of the same color.
  5. If the count of opposite-colored cells is at least 1 and the next cell in the same direction is of the same color as the move, then a good line is formed.
  6. Return true immediately if any direction forms a good line.
  7. If no directions form a good line, return false.

Why it works: The algorithm guarantees correctness because it checks all potential endpoints of good lines starting from the move. By requiring at least one opposite-colored cell and terminating at the same color, we satisfy the good line definition.

Python Solution

from typing import List

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        directions = [
            (0, 1),  # right
            (1, 0),  # down
            (0, -1), # left
            (-1, 0), # up
            (1, 1),  # down-right
            (1, -1), # down-left
            (-1, 1), # up-right
            (-1, -1) # up-left
        ]
        opposite = 'B' if color == 'W' else 'W'

        for dr, dc in directions:
            r, c = rMove + dr, cMove + dc
            count_opposite = 0

            while 0 <= r < 8 and 0 <= c < 8 and board[r][c] == opposite:
                count_opposite += 1
                r += dr
                c += dc

            if count_opposite > 0 and 0 <= r < 8 and 0 <= c < 8 and board[r][c] == color:
                return True

        return False

Implementation Walkthrough: We iterate over each direction and move along the board checking consecutive opposite-colored cells. The check count_opposite > 0 ensures that the move is an endpoint and not in the middle of an empty or same-colored line. If we find a matching endpoint after the sequence of opposite colors, we return true. Otherwise, after checking all directions, we return false.

Go Solution

func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
    directions := [][2]int{
        {0, 1}, {1, 0}, {0, -1}, {-1, 0},
        {1, 1}, {1, -1}, {-1, 1}, {-1, -1},
    }
    var opposite byte
    if color == 'B' {
        opposite = 'W'
    } else {
        opposite = 'B'
    }

    for _, dir := range directions {
        r, c := rMove+dir[0], cMove+dir[1]
        countOpposite := 0

        for r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == opposite {
            countOpposite++
            r += dir[0]
            c += dir[1]
        }

        if countOpposite > 0 && r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == color {
            return true
        }
    }

    return false
}

Go-specific notes: Slices are indexed with integers, and the bounds check ensures we do not access outside the 8x8 board. We use byte for characters and explicit variable initialization for clarity.

Worked Examples

Example 1

rMove = 4, cMove = 3, color = 'B'

Starting from (4,3), check all directions:

  • Left: encounters 'B' at (4,2) and (4,1) - good line, return true.
  • No need to check other directions since one is already valid.

Example 2

rMove = 4, cMove = 4, color = 'W'

  • All directions checked; some contain opposite-colored cells but never terminate in 'W'.
  • No good lines with move as endpoint, return false.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Each move checks at most 8 directions and 7 cells per direction in a fixed 8x8 board
Space O(1) Constant space for variables, no extra data structures

Since the board size is fixed, this solution is effectively constant time.

Test Cases

# Basic examples
assert Solution().checkMove([
    [".",".",".","B",".",".",".","."],
    [".",".",".","W",".",".",".","."],
    [".",".",".","W",".",".",".","."],
    [".",".",".","W",".",".",".","."],
    ["W","B","B",".","W","W","W","B"],
    [".",".",".","B",".",".",".","."],
    [".",".",".","B",".",".",".","."],
    [".",".",".","W",".",".",".","."]
], 4, 3, "B") == True  # Example 1

assert Solution().checkMove([
    [".",".",".",".",".",".",".","."],
    [".","B",".",".","W",".",".","."],
    [".",".","W",".",".",".",".","."],
    [".",".",".","W","B",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".","B","W",".","."],
    [".",".",".",".",".",".","W","."],
    [".",".",".",".",".",".",".","B"]
], 4, 4, "W") == False  # Example 2

# Edge cases
assert Solution().checkMove([["."]*8 for _ in range(8)], 0, 0, "B") == False  # Empty board
assert Solution().checkMove([
    ["B","W",".",".",".",".",".","."],
    [".","W",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".",".","."],
    [".",".",".",".",".",".