We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Move is Legal

Number: 2080

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an 8x8 board with cells that can be free ('.'), white ('W'), or black ('B'), determine if placing a stone of a given color at a free cell (rMove, cMove) is legal. A move is legal if the placed stone becomes an endpoint of at least one "good line". A good line (horizontal, vertical, or diagonal) is a contiguous line of three or more cells where both endpoints are the same color (equal to the player's color) and all cells in between are of the opponent’s color (with no free cells).

Key Insights

  • You must check in all eight directions (horizontal, vertical, and diagonal) from the move cell.
  • In each direction, the immediate neighbor must be of the opponent's color.
  • Continue along the direction until you either run off the board, hit a free cell, or encounter a cell of the player's color.
  • A direction forms a good line if at least one opponent cell is encountered before finding a player's color cell.
  • Since the board is fixed at 8x8, each direction check is constant time.

Space and Time Complexity

Time Complexity: O(1) (since the board size is fixed at 8x8 and each direction is checked with a constant number of steps) Space Complexity: O(1) (only a few extra variables are used)

Solution

The solution iterates over all eight possible directions from the move location. For each direction, it first checks whether the adjacent cell is of the opponent’s color; if not, that direction is immediately discarded. If the adjacent cell is valid, it continues moving in that direction, collecting only opponent pieces until a cell of the player's color is encountered. If such a cell is found and at least one opponent cell was between the new stone and that endpoint, the move is legal via that direction. If at least one direction results in a valid good line, return true; otherwise, return false.

Code Solutions

# Function to determine if a move is legal on the board.
def checkMove(board, rMove, cMove, color):
    # Determine opponent's color.
    opponent = 'B' if color == 'W' else 'W'
    # List of 8 directions: vertical, horizontal, and diagonal.
    directions = [(-1, -1), (-1, 0), (-1, 1),
                  (0, -1),          (0, 1),
                  (1, -1),  (1, 0),  (1, 1)]
    
    # For each direction, check if a good line can be formed.
    for dr, dc in directions:
        r = rMove + dr
        c = cMove + dc
        
        # Check boundary conditions and if the immediate neighbor is the opponent.
        if r < 0 or r >= 8 or c < 0 or c >= 8 or board[r][c] != opponent:
            continue
        
        # Traverse in the direction while the cells are the opponent's color.
        while 0 <= r < 8 and 0 <= c < 8 and board[r][c] == opponent:
            r += dr
            c += dc
        
        # Check if we are still within the board and found a cell with our color.
        if 0 <= r < 8 and 0 <= c < 8 and board[r][c] == color:
            return True  # Found a valid good line.
    
    # No good line found in any direction.
    return False

# Example usage:
# board = [
#    [".",".",".","B",".",".",".","."],
#    [".",".",".","W",".",".",".","."],
#    [".",".",".","W",".",".",".","."],
#    [".",".",".","W",".",".",".","."],
#    ["W","B","B",".","W","W","W","B"],
#    [".",".",".","B",".",".",".","."],
#    [".",".",".","B",".",".",".","."],
#    [".",".",".","W",".",".",".","."]
# ]
# print(checkMove(board, 4, 3, "B"))  # Expected output: True
← Back to All Questions