Watch 4 video solutions for Number of Valid Move Combinations On Chessboard, a hard level problem involving Array, String, Backtracking. This walkthrough by Huifeng Guan has 1,112 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is an 8 x 8 chessboard containing n pieces (rooks, queens, or bishops). You are given a string array pieces of length n, where pieces[i] describes the type (rook, queen, or bishop) of the ith piece. In addition, you are given a 2D integer array positions also of length n, where positions[i] = [ri, ci] indicates that the ith piece is currently at the 1-based coordinate (ri, ci) on the chessboard.
When making a move for a piece, you choose a destination square that the piece will travel toward and stop on.
(r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), or (r, c-1).(r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), (r, c-1), (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).(r, c) to the direction of (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).You must make a move for every piece on the board simultaneously. A move combination consists of all the moves performed on all the given pieces. Every second, each piece will instantaneously travel one square towards their destination if they are not already at it. All pieces start traveling at the 0th second. A move combination is invalid if, at a given time, two or more pieces occupy the same square.
Return the number of valid move combinations.
Notes:
Example 1:
Input: pieces = ["rook"], positions = [[1,1]] Output: 15 Explanation: The image above shows the possible squares the piece can move to.
Example 2:
Input: pieces = ["queen"], positions = [[1,1]] Output: 22 Explanation: The image above shows the possible squares the piece can move to.
Example 3:
Input: pieces = ["bishop"], positions = [[4,3]] Output: 12 Explanation: The image above shows the possible squares the piece can move to.
Constraints:
n == pieces.length n == positions.length1 <= n <= 4pieces only contains the strings "rook", "queen", and "bishop".1 <= ri, ci <= 8positions[i] is distinct.Problem Overview: You are given several chess pieces (rook, bishop, or queen) placed on an 8×8 board. Each piece may move in a valid direction and stop at any square along that path. The task is to count all combinations of moves such that pieces move simultaneously without ever occupying the same square at the same time.
Approach 1: Backtracking + Simulation (Exponential Time, O(k * 8^k) space)
This approach enumerates every possible movement choice for each piece using backtracking. For each piece, you pick a direction allowed by its type and a distance to travel. After assigning moves to all pieces, simulate the movement step-by-step to ensure no two pieces collide at any time step. The key insight is that collisions can occur mid‑movement, not just at final positions, so the simulation checks positions at every step. Backtracking works well because the number of pieces is small, and pruning invalid paths early significantly reduces the search space.
Approach 2: Dynamic Programming with State Simulation (O(states * moves), O(states) space)
This version models the board evolution across time. Each state represents the positions of all pieces at a specific step. Using array representations of coordinates, transitions simulate one movement step for each piece based on its chosen direction until it reaches its stopping square. Memoization stores already explored configurations to avoid recomputation. The technique behaves like a layered simulation where each time layer expands possible states while rejecting collisions. It blends ideas from simulation and dynamic programming to reduce repeated state exploration.
Recommended for interviews: The backtracking approach is what most interviewers expect. It directly models the problem: choose directions, choose distances, and simulate movement to validate collisions. Brute enumeration shows understanding of chess movement rules, while pruning and step-by-step collision checks demonstrate strong problem‑solving skills. The dynamic programming variant is useful when discussing optimization or avoiding repeated simulations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking + Move Simulation | O(k * directions^k * steps) | O(k * directions^k) | Best for interview solutions where the number of pieces is small and full enumeration with pruning is feasible |
| Dynamic Programming with State Tracking | O(states * moves) | O(states) | Useful when avoiding repeated simulations or analyzing board states across time steps |