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

Number of Valid Move Combinations On Chessboard

Number: 2166

Difficulty: Hard

Paid? No

Companies: PayPal

Problem Description

We are given an 8 x 8 chessboard with n pieces (rooks, queens, or bishops) placed at distinct 1-based coordinates. Each piece must make a move simultaneously toward a chosen destination square obeying its movement rules. Every second all pieces move one square along the pre-determined straight path toward their destination. A move combination is the set of chosen destinations for all pieces. A combination is invalid if at any second two or more pieces are in the same square (note that adjacent pieces may swap positions, so crossing paths is allowed if they never share a square at the same time). Return the number of valid move combinations.

Key Insights

  • Each piece has its own set of allowed destinations, determined by its movement rules (including staying in place).
  • For each move option we precompute the list (path) of squares that the piece traverses (from the starting square to the destination).
  • All pieces are moved simultaneously; simulation is done second by second until every piece has reached its destination.
  • Because n ≤ 4, we can use backtracking to generate every combination of destination selections and simulate their moves.
  • At every time step during simulation we check for collisions—if two or more pieces are in the same square, that combination is invalid.

Space and Time Complexity

Time Complexity: O(Choices^n * L) where Choices is the number of move options per piece (limited by board size) and L is the maximum length of the movement path (at most 8), with n ≤ 4. Space Complexity: O(n * ChoicePaths) due to storing the precomputed paths.

Solution

For each piece, generate a list of valid target positions and simulate the path to that target using the allowed directions. Store both the destination and the full step-by-step path (including the starting square). Then, using backtracking, select one move for each piece. For each move combination, simulate the simultaneous movement tick by tick (each tick represents one square movement for each piece) up to the maximum number of steps required by any piece. At each simulated tick, check if any two pieces occupy the same square. If not, count this combination as valid. This brute-force approach works due to the small constraint on n (n ≤ 4).

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with inline comments.

# Python code solution for Number of Valid Move Combinations On Chessboard

def numValidMoveCombinations(pieces, positions):
    # Define movement directions for each piece type.
    directions = {
        "rook": [(1, 0), (-1, 0), (0, 1), (0, -1)],
        "bishop": [(1, 1), (1, -1), (-1, 1), (-1, -1)],
        "queen": [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    }
    
    n = len(pieces)
    # Precompute all valid destination options and their paths for each piece.
    all_paths = []  # Each element is a list of tuples: (destination, path list)
    for idx, (piece, pos) in enumerate(zip(pieces, positions)):
        r, c = pos
        piece_paths = []
        # Option to stay on the same square.
        piece_paths.append(((r, c), [(r, c)]))
        for dr, dc in directions[piece]:
            nr, nc = r + dr, c + dc
            while 1 <= nr <= 8 and 1 <= nc <= 8:
                path = []  # Build path from starting pos to destination.
                cr, cc = r, c
                while (cr, cc) != (nr, nc):
                    path.append((cr, cc))
                    cr += dr
                    cc += dc
                path.append((nr, nc))
                piece_paths.append(((nr, nc), path))
                nr += dr
                nc += dc
        all_paths.append(piece_paths)

    valid_count = 0

    # Backtracking: choose one move option per piece.
    def backtrack(i, chosen_paths):
        nonlocal valid_count
        if i == n:
            # Determine simulation length (max path length among pieces).
            max_steps = max(len(path) for dest, path in chosen_paths)
            valid = True
            # Simulate each second.
            for t in range(max_steps):
                current_positions = {}
                for dest, path in chosen_paths:
                    # If piece has reached its destination, it remains there.
                    current = path[t] if t < len(path) else path[-1]
                    if current in current_positions:
                        valid = False  # Collision detected.
                        break
                    current_positions[current] = True
                if not valid:
                    break
            if valid:
                valid_count += 1
            return
        
        for dest, path in all_paths[i]:
            chosen_paths.append((dest, path))
            backtrack(i + 1, chosen_paths)
            chosen_paths.pop()

    backtrack(0, [])
    return valid_count

# Example usage of Python solution:
pieces = ["rook"]
positions = [[1, 1]]
print(numValidMoveCombinations(pieces, positions))  # Expected output: 15
← Back to All Questions