LeetCode 2056 - Number of Valid Move Combinations On Chessboard

LeetCode Problem 2056

Difficulty: 🔴 Hard
Topics: Array, String, Backtracking, Simulation

Solution

Problem Understanding

The problem asks us to calculate the total number of valid move combinations for a small set of chess pieces (up to four) on an 8 x 8 chessboard. Each piece-rook, bishop, or queen-can move according to standard chess rules, but only along paths defined by the piece's movement. A move combination consists of assigning a destination square to every piece simultaneously, and a combination is valid if no two pieces occupy the same square at the same time while moving toward their respective destinations. Pieces move one square per second along a straight path to their destination, and collisions are only prohibited if two or more pieces occupy the same square at the same second. Pieces may swap positions directly in one second if they are adjacent.

The input consists of pieces, a list of strings describing the type of each piece, and positions, a list of [row, col] coordinates representing their starting positions. The output is a single integer representing the number of valid move combinations. The constraints limit n to at most 4, which suggests that even approaches with exponential complexity can be feasible. Key points include:

• Each piece can stay in its original square.
• No two pieces start in the same square.
• Only up to one queen exists.
• The chessboard is 8x8, so the number of possible moves per piece is bounded by 15 for rooks, 22 for queens, and 12 for bishops.

Important edge cases include pieces that could collide mid-path, pieces on the edge or corners of the board, and the possibility of a piece choosing to stay in place.

Approaches

The brute-force approach is to enumerate all possible destination squares for every piece, then simulate the movement step by step to check for collisions. This guarantees correctness but is computationally expensive. With 4 pieces, each having up to 22 possible moves (queen max), we could have up to 22^4 ≈ 234,256 combinations. Each combination requires simulating the moves second by second, which is manageable given the small number of pieces but not elegant.

The optimal approach leverages backtracking and precomputation. For each piece, precompute all possible destinations it can reach. Then, recursively choose a destination for each piece and simulate the movement in parallel. We prune invalid combinations early when a collision occurs at any second. The small constraints make this feasible, and it avoids redundant computation by stopping early for invalid partial combinations. Key insights include:

• Paths are linear, so positions at time t can be easily computed.
• Since n <= 4, checking all combinations is computationally acceptable.
• Pruning paths early drastically reduces unnecessary simulations.

Algorithm Walkthrough

1. Generate Moves: For each piece, calculate all reachable destinations according to its movement rules. Include the current position as a valid destination.
2. Simulate Moves: Define a helper to simulate one combination of destinations. Compute the trajectory of each piece, moving one square per second along a straight line path.
3. Collision Check: At each second, construct a set of occupied squares. If any square is occupied by two or more pieces, discard the combination.
4. Backtracking: Recursively select a destination for each piece. If a combination passes the collision check, increment the valid combination count.
5. Return Result: After exploring all combinations, return the total count.

Why it works: The algorithm ensures every possible combination of destinations is considered and checks for collisions at every step, guaranteeing correctness. Backtracking allows early pruning, reducing redundant simulations.

Python Solution

from typing import List, Tuple

class Solution:
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        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)]
        }
        
        def in_bounds(r: int, c: int) -> bool:
            return 1 <= r <= 8 and 1 <= c <= 8
        
        # Generate all reachable destinations for a piece
        def get_moves(piece: str, r: int, c: int) -> List[Tuple[int,int]]:
            moves = [(r,c)]
            for dr, dc in DIRECTIONS[piece]:
                nr, nc = r+dr, c+dc
                while in_bounds(nr, nc):
                    moves.append((nr, nc))
                    nr += dr
                    nc += dc
            return moves
        
        n = len(pieces)
        all_moves = [get_moves(pieces[i], positions[i][0], positions[i][1]) for i in range(n)]
        result = 0
        
        # Helper to compute positions at each second
        def path(start: Tuple[int,int], end: Tuple[int,int]) -> List[Tuple[int,int]]:
            r0, c0 = start
            r1, c1 = end
            dr = (r1 - r0) and ((r1 - r0)//abs(r1 - r0))
            dc = (c1 - c0) and ((c1 - c0)//abs(c1 - c0))
            path_positions = []
            r, c = r0, c0
            while (r, c) != (r1, c1):
                r += dr
                c += dc
                path_positions.append((r,c))
            return path_positions
        
        def dfs(idx: int, chosen: List[Tuple[int,int]]):
            nonlocal result
            if idx == n:
                # simulate moves
                positions_at_time = []
                max_len = 0
                piece_paths = []
                for i in range(n):
                    p_path = path(tuple(positions[i]), chosen[i])
                    piece_paths.append(p_path)
                    max_len = max(max_len, len(p_path))
                
                for t in range(max_len):
                    occupied = set()
                    for i in range(n):
                        pos = piece_paths[i][t] if t < len(piece_paths[i]) else chosen[i]
                        if pos in occupied:
                            return
                        occupied.add(pos)
                result += 1
                return
            
            for move in all_moves[idx]:
                dfs(idx+1, chosen + [move])
        
        dfs(0, [])
        return result

Explanation: We first generate all possible destinations for each piece using movement rules. The path function constructs the sequence of squares a piece will occupy. Using dfs, we recursively choose a destination for each piece and simulate moves to check collisions. Valid combinations increment the result.

Go Solution

func countCombinations(pieces []string, positions [][]int) int {
    directions := map[string][][]int{
        "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}},
    }

    inBounds := func(r, c int) bool {
        return r >= 1 && r <= 8 && c >= 1 && c <= 8
    }

    n := len(pieces)
    allMoves := make([][][]int, n)
    for i := 0; i < n; i++ {
        r, c := positions[i][0], positions[i][1]
        moves := [][]int{{r, c}}
        for _, d := range directions[pieces[i]] {
            nr, nc := r+d[0], c+d[1]
            for inBounds(nr, nc) {
                moves = append(moves, []int{nr, nc})
                nr += d[0]
                nc += d[1]
            }
        }
        allMoves[i] = moves
    }

    var path func(start, end []int) [][]int
    path = func(start, end []int) [][]int {
        r0, c0 := start[0], start[1]
        r1, c1 := end[0], end[1]
        dr, dc := 0, 0
        if r1 != r0 {
            if r1 > r0 {
                dr = 1
            } else {
                dr = -1
            }
        }
        if c1 != c0 {
            if c1 > c0 {
                dc = 1
            } else {
                dc = -1
            }
        }
        var positions [][]int
        r, c := r0, c0
        for r != r1 || c != c1 {
            r += dr
            c += dc
            positions = append(positions, []int{r, c})
        }
        return positions
    }

    var result int
    var dfs func(idx int,