#2056

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Number of Valid Move Combinations On Chessboard

Given a set of pieces on a chessboard, calculate the number of valid move combinations without overlap using backtracking and pruning.

array string backtracking simulation

Problem Statement

You are given an 8x8 chessboard with n pieces, each described by a string (rook, queen, or bishop) and their positions. The position of each piece is given in a 2D array, where each element represents a piece's current location on the chessboard.

For each piece, you must calculate all possible move combinations, where each move consists of the piece moving one square toward its destination. A valid combination occurs when no two pieces occupy the same square at any moment. Your task is to compute the number of such valid move combinations using backtracking with pruning.

Examples

Example 1

Input: pieces = ["rook"], positions = [[1,1]]

Output: 15

The image above shows the possible squares the piece can move to.

Example 2

Input: pieces = ["queen"], positions = [[1,1]]

Output: 22

The image above shows the possible squares the piece can move to.

Example 3

Input: pieces = ["bishop"], positions = [[4,3]]

Output: 12

The image above shows the possible squares the piece can move to.

Constraints

n == pieces.length
n == positions.length
1 <= n <= 4
pieces only contains the strings "rook", "queen", and "bishop".
There will be at most one queen on the chessboard.
1 <= ri, ci <= 8
Each positions[i] is distinct.

Solution Approach

Backtracking and Pruning

This problem is solved using backtracking to explore all possible move combinations for the pieces. Pruning is applied to eliminate invalid states early, such as when two pieces would occupy the same square. The backtracking process ensures we explore only viable paths.

Simulating Moves for Each Piece

Each piece has its own unique movement rules (e.g., rooks move horizontally/vertically, bishops diagonally). These rules are used to simulate all possible valid moves for each piece. By simulating the moves step by step, we check if a move combination is valid.

Combining Results and Counting Valid Combinations

Once all potential moves for the pieces are generated, we combine them into valid configurations and count how many of these are feasible. The final count of valid move combinations is the desired output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the number of possible move combinations and the backtracking depth. Since n (the number of pieces) is small (up to 4), the complexity is manageable even with exhaustive searches. Pruning reduces the number of unnecessary calculations, improving efficiency.

What Interviewers Usually Probe

The candidate demonstrates an understanding of backtracking and pruning techniques.
The candidate is able to efficiently simulate different chess piece moves and apply constraints to avoid overlap.
The candidate shows how to combine results from different pieces and compute the total number of valid combinations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to prune invalid paths early, leading to unnecessary calculations.
Overcomplicating the solution by not taking advantage of the small input size (n <= 4).
Failing to properly handle the unique movement rules for each type of piece (rook, bishop, queen).

Follow-up variants

Increasing the number of pieces to test how the solution scales.
Introducing more complex pieces with additional movement rules.
Adding time constraints to make the solution more efficient in a real-time chess simulation.

FAQ

How can backtracking be applied to the 'Number of Valid Move Combinations On Chessboard' problem?

Backtracking allows you to explore all possible move combinations for each piece while pruning invalid combinations early, ensuring the search remains efficient.

What are the movement rules for the chess pieces in this problem?

Rooks move horizontally or vertically, bishops move diagonally, and queens combine both rook and bishop movements.

How does pruning help in solving this problem?

Pruning eliminates invalid paths early in the backtracking process, such as when two pieces would overlap, significantly reducing the search space.

How do I combine the results of multiple pieces in this problem?

You simulate the moves for each piece individually, then combine the valid configurations where no pieces share the same square at any point in time.

Can this problem be solved without backtracking?

While it is possible to use brute force, backtracking with pruning is far more efficient, especially with the small input size (n <= 4).

terminal

Solution

Solution 1: DFS

The problem has at most $4$ pieces, and each piece can move in up to $8$ directions. We can consider using DFS to search all possible move combinations.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

rook_dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
bishop_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
queue_dirs = rook_dirs + bishop_dirs


def get_dirs(piece: str) -> List[Tuple[int, int]]:
    match piece[0]:
        case "r":
            return rook_dirs
        case "b":
            return bishop_dirs
        case _:
            return queue_dirs


class Solution:
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        def check_stop(i: int, x: int, y: int, t: int) -> bool:
            return all(dist[j][x][y] < t for j in range(i))

        def check_pass(i: int, x: int, y: int, t: int) -> bool:
            for j in range(i):
                if dist[j][x][y] == t:
                    return False
                if end[j][0] == x and end[j][1] == y and end[j][2] <= t:
                    return False
            return True

        def dfs(i: int) -> None:
            if i >= n:
                nonlocal ans
                ans += 1
                return
            x, y = positions[i]
            dist[i][:] = [[-1] * m for _ in range(m)]
            dist[i][x][y] = 0
            end[i] = (x, y, 0)
            if check_stop(i, x, y, 0):
                dfs(i + 1)
            dirs = get_dirs(pieces[i])
            for dx, dy in dirs:
                dist[i][:] = [[-1] * m for _ in range(m)]
                dist[i][x][y] = 0
                nx, ny, nt = x + dx, y + dy, 1
                while 1 <= nx < m and 1 <= ny < m and check_pass(i, nx, ny, nt):
                    dist[i][nx][ny] = nt
                    end[i] = (nx, ny, nt)
                    if check_stop(i, nx, ny, nt):
                        dfs(i + 1)
                    nx += dx
                    ny += dy
                    nt += 1

        n = len(pieces)
        m = 9
        dist = [[[-1] * m for _ in range(m)] for _ in range(n)]
        end = [(0, 0, 0) for _ in range(n)]
        ans = 0
        dfs(0)
        return ans

Continue Practicing

#2011 final value of variable after performing operations #2109 adding spaces to a string #1980 find unique binary string