Leetcode – Available Captures for Rook Solution in Python

Spread the love

Board games, like Chess, have been historically leveraged to create programming problems that assess one’s analytical and algorithmic problem-solving skills. Leetcode’s “Available Captures for Rook” is one such problem that challenges the participant to think within the confines of a chessboard and the movement of its pieces. In this article, we will delve deep into the problem, discussing its intricacies, and presenting a detailed solution in Python.

Table of Contents

  1. Problem Statement
  2. Understanding Chess and the Rook
  3. Strategy for Solving the Problem
  4. Python Implementation
  5. Time and Space Complexity Analysis
  6. Conclusion

1. Problem Statement

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, captures a black pawn by moving to the same square it occupies, or is blocked by a white bishop. A rook cannot move to a square occupied by white bishops. Return the number of pawns the rook can capture in one move.

Example:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3

2. Understanding Chess and the Rook

For those unfamiliar with chess, the rook is a piece that can move any number of squares along a rank or file, but cannot leap over other pieces. In this problem, the rook can capture only black pawns and its movement is blocked by white bishops. The challenge is to identify how many black pawns can be captured by the rook in its current position.

3. Strategy for Solving the Problem

To tackle this problem:

  1. Identify the Rook’s Position: Traverse the chessboard to find where the rook (‘R’) is located.
  2. Explore Four Directions from Rook’s Position: From the rook’s position, simulate its movement in all four cardinal directions (north, south, east, west) until one of the stopping conditions is met (either the edge of the board, a white bishop, or a black pawn).
  3. Count the Pawns: As we simulate the rook’s movement in each direction, if we encounter a pawn (‘p’), we increase our count of capturable pawns.

4. Python Implementation

def numRookCaptures(board):
    # Step 1: Find the position of the Rook
    for i in range(8):
        for j in range(8):
            if board[i][j] == 'R':
                x, y = i, j

    # Helper function to simulate Rook's movement in one direction
    def capture_count(dx, dy):
        i, j = x + dx, y + dy
        while 0 <= i < 8 and 0 <= j < 8:
            if board[i][j] == 'B':
                return 0
            if board[i][j] == 'p':
                return 1
            i += dx
            j += dy
        return 0

    # Step 2: Check all four directions
    return capture_count(-1, 0) + capture_count(1, 0) + capture_count(0, -1) + capture_count(0, 1)

5. Time and Space Complexity Analysis

  • Time Complexity: The solution involves traversing the chessboard to find the rook, which is O(1) since the board size is fixed at 8×8. The rook’s movement simulation in each direction is also O(1) for a similar reason. Thus, the overall time complexity is O(1).
  • Space Complexity: We use a constant amount of extra space to store the rook’s position and directions. Therefore, the space complexity is also O(1).

6. Conclusion

The “Available Captures for Rook” problem on Leetcode offers an engaging way to tackle the classical rules of chess in a programming environment. Though it might appear to be a simple search problem initially, the constraints make it a unique challenge. By breaking down the rook’s movements and understanding the rules of the game, we can effectively simulate its actions on the chessboard. This problem serves as a reminder of how real-world scenarios and games can be effectively transformed into intriguing coding challenges.

Leave a Reply