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 == 80 <= rMove, cMove < 8board[rMove][cMove] == '.'color is either 'B' or 'W'.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:
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:
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 TrueWe 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:
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| Case | How to Handle |
|---|---|
| Null board or empty board | Return false immediately as no move can be legal on an invalid board. |
| Move coordinates are out of bounds | Return false immediately if the row or column index is outside the valid range of the board. |
| The target cell is already occupied | 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) | 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 | 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. | Use appropriate data types (e.g., long) to prevent overflow during distance calculations. |
| The current player attempts to move an opponent's piece. | 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. | Return false if any piece is obstructing the valid path between the origin and target cells. |