Taro Logo

Check if Move is Legal

Medium
Asked by:
Profile picture
4 views
Topics:
ArraysStringsTwo Pointers

You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by '.', white cells are represented by 'W', and black cells are represented by 'B'.

Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal).

A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free). You can find examples for good lines in the figure below:

Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.

Example 1:

Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
Output: true
Explanation: '.', 'W', and 'B' are represented by the colors blue, white, and black respectively, and cell (rMove, cMove) is marked with an 'X'.
The two good lines with the chosen cell as an endpoint are annotated above with the red rectangles.

Example 2:

Input: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
Output: false
Explanation: While there are good lines with the chosen cell as a middle cell, there are no good lines with the chosen cell as an endpoint.

Constraints:

  • board.length == board[r].length == 8
  • 0 <= rMove, cMove < 8
  • board[rMove][cMove] == '.'
  • color is either 'B' or 'W'.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the dimensions of the game board, and what data type is used to represent it?
  2. What are the valid values for 'move', and how are the coordinates represented (e.g., 0-indexed or 1-indexed)?
  3. What defines a 'legal' move? Are there specific rules regarding blocking, capturing, or moving beyond the board's boundaries?
  4. Should I handle cases where the provided 'move' is outside the board's dimensions or attempts to move to an invalid cell (e.g., already occupied or outside the rules)?
  5. What is the desired return value (e.g., boolean indicating legality, or an error code for illegal moves)?

Brute Force Solution

Approach

The brute force approach in this game involves examining every possible move to determine if it is allowed by the game's rules. We will explore all possible game state transitions after making a move to see if the result is valid. If any of these transitions result in a legal board, the move is determined to be legal.

Here's how the algorithm would work step-by-step:

  1. First, consider the location where you want to make your move.
  2. Then, imagine making that move. What would the game board look like after your move?
  3. Next, carefully check every rule of the game to see if making that move broke any of them.
  4. For example, does it put you out of bounds? Does it land you on an occupied space when that's not allowed? Does it violate any other rule of the game?
  5. If any of those rules are broken, the move is illegal, and you stop checking.
  6. If you have checked all the rules and none of them are broken, then the move is legal.

Code Implementation

def check_if_move_is_legal_brute_force(
    game_board,
    move_row,
    move_column
):
    # Imagine making the move on a copy of the board.
    hypothetical_game_board = [
        row[:] for row in game_board
    ]

    hypothetical_game_board[move_row][
        move_column
    ] = "X"

    # Check if the move is out of bounds.
    if (
        move_row < 0
        or move_row >= len(game_board)
        or move_column < 0
        or move_column >= len(game_board[0])
    ):
        return False

    # Check if the move lands on an occupied space when not allowed.
    if game_board[move_row][move_column] != "-":
        return False

    # Add more game-specific rule checks here.
    # For example, checking if the move results in checkmate.
    # This is where game specific rules must be checked
    if not is_board_legal(
        hypothetical_game_board
    ):
        return False

    return True

def is_board_legal(board):
    return True

Big(O) Analysis

Time Complexity
O(1)The described brute force approach involves examining a single potential move on the board. While checking that move, the algorithm iterates through a fixed set of game rules to validate the move's legality. Since the number of game rules and the checks associated with each rule is constant and independent of the board size or any other input variable 'n', the overall time complexity is O(1).
Space Complexity
O(1)The provided explanation outlines a process of checking rules against a potential move. It involves simulating the move, and then evaluating if any rules are violated. No additional data structures that scale with the size of the game board (N) are mentioned, nor is any recursion used. The algorithm focuses on direct rule checking and evaluating the state of the board after the move, but does so without storing extensive data beyond the immediate move being checked and rule being tested. Therefore, it uses a constant amount of extra space.

Optimal Solution

Approach

We need to determine if a given move in a game is valid according to the game's rules. Instead of exploring all possible move outcomes, the optimal approach directly checks if the proposed move violates any rules. If the move doesn't break any rules, it's legal; otherwise, it's not.

Here's how the algorithm would work step-by-step:

  1. First, understand the game's rules and restrictions. What actions are allowed, and under what conditions?
  2. Next, examine the proposed move in detail. What piece is being moved, and to which location?
  3. Check if the piece's movement follows its defined movement capabilities. Can that type of piece even move that way?
  4. Check for any obstacles in the path of the move. Are there pieces blocking the way that prevent this move?
  5. Check if the destination square is valid. Is it within the game board's boundaries, and is it occupied by a friendly piece?
  6. If all the previous checks pass, then analyze the resulting board state. Does this move put the player's own king in check?
  7. If after all these tests, no rule is violated, then the move is legal. Otherwise, the move is illegal.

Code Implementation

def is_move_legal(board, piece, start_row, start_col, end_row, end_col):
    # First, check if the destination is within bounds
    if not (0 <= end_row < len(board) and 0 <= end_col < len(board[0])):
        return False

    # Check if the destination is occupied by a friendly piece
    if board[end_row][end_col] != '' and board[end_row][end_col][0] == piece[0]:
        return False

    # Check if the move is legal for the piece type
    if piece[1] == 'Pawn':
        if not is_pawn_move_valid(board, start_row, start_col, end_row, end_col):
            return False
    elif piece[1] == 'Rook':
        if not is_rook_move_valid(board, start_row, start_col, end_row, end_col):
            return False
    else:
        # In a real implementation, add logic for all piece types.
        return True

    # Finally, check if the move puts the king in check. This is crucial.
    hypothetical_board = [row[:] for row in board]
    hypothetical_board[end_row][end_col] = piece
    hypothetical_board[start_row][start_col] = ''
    if is_king_in_check(hypothetical_board, piece[0]):
        return False

    return True

def is_pawn_move_valid(board, start_row, start_col, end_row, end_col):
    if start_col == end_col and board[end_row][end_col] == '':
        if start_row - end_row == 1:
            return True
    return False

def is_rook_move_valid(board, start_row, start_col, end_row, end_col):
    if start_row != end_row and start_col != end_col:
        return False

    if start_row == end_row:
        step = 1 if end_col > start_col else -1
        for col in range(start_col + step, end_col, step):
            if board[start_row][col] != '':
                return False
    else:
        step = 1 if end_row > start_row else -1
        for row in range(start_row + step, end_row, step):
            if board[row][start_col] != '':
                return False
    return True

def is_king_in_check(board, player_color):
    # In a real implementation, check for all threats to the king.
    return False

Big(O) Analysis

Time Complexity
O(1)The proposed solution involves a fixed number of checks against the game's rules, regardless of the board size or the number of pieces. Each step, from validating movement capabilities to checking for obstacles and resulting check conditions, performs a limited set of operations. The operations do not scale with the board size, therefore, the time complexity is constant.
Space Complexity
O(1)The algorithm primarily involves checking conditions and doesn't create auxiliary data structures that scale with the input size (N). While checking for obstacles might involve iterating through a path, the space required for this iteration (e.g., storing the current position) remains constant. Similarly, checking if the move puts the king in check does not create any large auxiliary data structures. Therefore, the space complexity is constant.

Edge Cases

Null board or empty board
How to Handle:
Return false immediately as no move can be legal on an invalid board.
Move coordinates are out of bounds
How to Handle:
Return false immediately if the row or column index is outside the valid range of the board.
The target cell is already occupied
How to Handle:
Return false if the cell at the specified coordinates already contains a piece.
The move is not a valid move type (e.g., not horizontal, vertical or diagonal)
How to Handle:
Return false if the move does not follow the rules of the game implemented by the 'isLegalMove' function.
The board is full and no moves are possible
How to Handle:
The game logic should ideally handle this, but the 'isLegalMove' function must handle it without crashing, likely by correctly returning false for any attempted move on a full board.
Integer overflow when calculating distances or sums of coordinates.
How to Handle:
Use appropriate data types (e.g., long) to prevent overflow during distance calculations.
The current player attempts to move an opponent's piece.
How to Handle:
Return false if the piece at the origin coordinates does not belong to the current player.
The path for the move is blocked by another piece.
How to Handle:
Return false if any piece is obstructing the valid path between the origin and target cells.