Check If Move Is Legal Leetcode Problem 1958 [Python Solution]

In this blog post, we will tackle the Check If Move Is Legal problem from LeetCode.

This problem falls under the category of Graphs and is rated as a medium difficulty problem.

The problem statement can be found on the LeetCode website.

The task at hand is to determine if a move on an 8×8 game board is legal.

The game board is represented as a grid, where cells can be empty ('.'), white ('W'), or black ('B').

A legal move is defined as changing an empty cell to the color you are playing as (either white or black) in such a way that it becomes the endpoint of a good line.

A good line is a line of three or more cells where the endpoints are of one color and the cells in between are of the opposite color.

In this blog post, we will walk you through the problem, its constraints, a brute force approach, and an efficient Python solution.

We'll also discuss the reasoning behind our efficient approach and analyze the time and space complexity.

Let's dive into the problem and explore the solutions.

Problem Overview

You are given an 8×8 grid board, where each cell represents a position on a game board.

The cells can be in one of three states:

Empty cell ('.')
White cell ('W')
Black cell ('B')

A move consists of choosing an empty cell and changing its color to the color you are playing as (either white or black).

However, a move is considered legal only if, after changing the cell's color, it becomes the endpoint of a good line.

A good line is a sequence of three or more cells, including the endpoints, where the endpoints are of one color, and the remaining cells in the middle are of the opposite color.

The cells in a good line cannot be empty.

Constraints

Before we delve into the solution, let's understand the constraints of the problem:

The board is an 8×8 grid, so board.length == board[r].length == 8.
You are given the row and column of the cell to change, denoted by rMove and cMove, respectively.
The cell at (rMove, cMove) is guaranteed to be empty, represented by a '.'.
The color you are playing as is either 'B' (black) or 'W' (white).

Now that we have a clear understanding of the problem and its constraints, let's explore the solution.

Example 1:

To illustrate the problem, let's consider an example:

Input:
board = [[".",".",".","B",".",".",".","."], [".",".",".","W",".",".",".","."], [".",".",".","W",".",".",".","."], [".",".",".","W",".",".",".","."], ["W","B","B",".","W","W","W","B"], [".",".",".","B",".",".",".","."], [".",".",".","B",".",".",".","."], [".",".",".","W",".",".",".","."]] rMove = 4 cMove = 3 color = "B"

Output:
true

In this example, the board is represented with '.' (empty), 'W' (white), and 'B' (black) cells.

We are provided with the coordinates (4, 3) and the color 'B'.

The goal is to determine if changing the cell at (4, 3) to 'B' results in a legal move.

The cell at (4, 3) is marked with an 'X'.

There are two good lines with the chosen cell as an endpoint, which are annotated with red rectangles.

Thus, the output is true because it's a legal move.

Example 2:

Let's take another example:

Input:
board = [[".",".",".",".",".",".",".","."], [".","B",".",".","W",".",".","."], [".",".","W",".",".",".",".","."], [".",".",".","W","B",".",".","."], [".",".",".",".",".",".",".","."], [".",".",".",".","B","W",".","."], [".",".",".",".",".",".","W","."], [".",".",".",".",".",".",".","B"]] rMove = 4 cMove = 4 color = "W"

Output:
false

In this example, we again have an 8×8 board with empty, white, and black cells.

We are provided with the coordinates (4, 4) and the color 'W'.

The question is whether changing the cell at (4, 4) to 'W' results in a legal move.

There are no good lines with the chosen cell as an endpoint in this case, so the output is false.

Understanding Constraints

To tackle this problem, we need to consider the constraints and design our solution accordingly.

Here are the key constraints to keep in mind:

Board Dimensions: The game board is an 8×8 grid, which means it has 8 rows and 8 columns.

This is a fixed constraint we can work with.

Empty Cell: The cell at (rMove, cMove) is guaranteed to be empty (represented by '.').

This means we don't need to check whether it's empty before making a move.

Color: The color can be either 'B' (black) or 'W' (white).

We will use this color to make the move.

Now that we've established a clear understanding of the problem and its constraints, let's explore the approaches to solve it.

Brute Force Approach

Before we dive into the efficient approach, let's start by considering a brute force solution to the problem.

The brute force approach involves checking all possible lines that include the cell at (rMove, cMove) as an endpoint.

We will explore each direction (up, down, left, right, and diagonals) and count the number of consecutive cells of the same color in each direction.

If we find any line with at least three cells of the same color, it's a good line, and the move is legal.

Here's a Python code snippet for the brute force approach:

def checkMove(board, rMove, cMove, color):
    # Define directions (up, down, left, right, diagonals)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]

    # Helper function to check if a move in a given direction is legal
    def legal(row, col, color, direction):
        dr, dc = direction
        row, col = row + dr, col + dc
        length = 1

        while 0 <= row < 8 and 0 <= col < 8:
            length += 1
            if board[row][col] == '.':
                return False
            if board[row][col

] == color:
                return length >= 3
            row, col = row + dr, col + dc
        return False

    # Set the cell at (rMove, cMove) to the specified color
    board[rMove][cMove] = color

    # Check each direction for a legal move
    for direction in directions:
        if legal(rMove, cMove, color, direction):
            return True

    return False

The code starts by defining the eight possible directions: up, down, left, right, and diagonals.

It then defines a helper function, legal, that checks if a move in a given direction results in a legal line.

The main function sets the cell at (rMove, cMove) to the specified color and checks each direction for a legal move using the legal function.

While this brute force approach would work, it's not the most efficient solution, especially when dealing with a large game board.

We can optimize the solution to reduce unnecessary checks and improve runtime.

Efficient Approach

To optimize the solution, we can take advantage of the fact that good lines are continuous.

If we start from the changed cell and traverse in a particular direction (e.g., up), we can keep track of the count of consecutive cells with the same color.

If we reach three consecutive cells of the same color, it's a good line.

We will apply this approach to all eight possible directions: up, down, left, right, and diagonals.

If any of these directions result in a good line, the move is legal.

Here's an efficient Python code solution:

View on GitHub ➹

def checkMove(board, rMove, cMove, color):
    # Dimensions of the board
    ROWS, COLS = len(board), len(board[0])

    # Define directions (up, down, left, right, diagonals)
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [-1, -1], [1, -1], [-1, 1]]

    # Set the cell at (rMove, cMove) to the specified color
    board[rMove][cMove] = color

    def legal(row, col, color, direc):
        dr, dc = direc
        row, col = row + dr, col + dc
        length = 1

        while 0 &lt;= row &lt; ROWS and 0 &lt;= col &lt; COLS:
            length += 1
            if board[row][col] == &#39;.&#39;:
                return False
            if board[row][col] == color:
                return length &gt;= 3
            row, col = row + dr, col + dc
        return False

    for d in direction:
        if legal(rMove, cMove, color, d):
            return True

    return False

This efficient approach follows a similar structure to the brute force solution but optimizes the process by traversing each direction only once and checking for good lines.

Time and Space Complexity

Let's analyze the time and space complexity of our efficient solution:

Time Complexity:
– We iterate through each of the eight possible directions (up, down, left, right, and diagonals) once.
– Within each direction, we traverse the board to check for good lines, but we stop as soon as we find a good line or reach an invalid position.
– In the worst case, we may traverse the entire board, but we only do this for one direction at most.

So, the overall time complexity is O(1), or more precisely, O(8).

Space Complexity:
– The space complexity is constant, as we use a fixed amount of additional memory for variables and the direction array.

Hence, the space complexity is O(1).

Reasoning Behind Our Approach

Our approach efficiently solves the problem by considering the continuous nature of good lines and traversing in different directions from the changed cell.

This allows us to avoid redundant checks and achieve a runtime complexity of O(1) in practice.

We set the cell at (rMove, cMove) to the specified color and then iterate through eight possible directions, applying the legal function to each direction.

The legal function checks if a move in a given direction forms a good line, which is defined as having at least three consecutive cells of the same color.

If we find a good line in any direction, the move is considered legal.

This approach optimizes the runtime and space usage and provides a clear and concise solution to the problem.

Conclusion

In this blog post, we tackled the Check If Move Is Legal problem from LeetCode.

We explored the problem statement, its constraints, and provided an efficient Python solution to determine if a move is legal on an 8×8 game board.

We also discussed the reasoning behind our approach, highlighting how we optimize the solution by considering the continuous nature of good lines.

If you found this blog post helpful, please consider liking and subscribing to support the our platform.

We encourage you to comment, ask questions, make suggestions, and share the content.

If you have any additional questions or need further clarification, feel free to ask.

To access the full problem and code, visit the LeetCode problem page.

We hope this guide has been informative and aids you in your coding journey.

Happy coding!