Number of Valid Move Combinations On Chessboard - Solution & Explanation
Problem Statement
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.
- A rook can only travel horizontally or vertically from
(r, c)to the direction of(r+1, c),(r-1, c),(r, c+1), or(r, c-1). - A queen can only travel horizontally, vertically, or diagonally from
(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). - A bishop can only travel diagonally from
(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:
- No two pieces will start in the same square.
- You may choose the square a piece is already on as its destination.
- If two pieces are directly adjacent to each other, it is valid for them to move past each other and swap positions in one second.
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.lengthn == positions.length1 <= n <= 4piecesonly 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.
Approach Overview
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 1: Backtracking Approach
This method involves generating all possible move combinations using backtracking. Each piece moves independently in all possible directions according to its type until it reaches its destination or collides with another piece. For each valid configuration where no two pieces land on the same square at the same time, count the valid move-set.
The C program uses backtracking to explore all possible move sequences for pieces on a chessboard. For each piece, it identifies legal movement directions and iteratively tries each direction for various steps until it is outside the board or occupied by another piece.
The backtracking feature is employed by recursively calling the function to cover all moves for a piece before moving to the next piece. If a combination of such sequences leads to a move where no two pieces land on the same square simultaneously, it counts as a valid move-set.
Complexity
The time complexity of the solution is O(8^n), assuming a worst-case scenario of exploring all potential moves for n pieces. The space complexity is O(n) for recursive call stack usage.
Approach 2: Dynamic Programming Approach
A dynamic programming solution is possible by using a memoization technique to count valid move configurations. This approach calculates configurations for smaller subsets of moves and combines them to create complete solutions, avoiding redundant calculations.
The C program utilizes an array to cache results of computed configurations so they can be reused, preventing recalculation and expediting the process. Specific moves are stored with indexes in a direction array for accessibility while adding boundary checks and dynamic selection of configurations as its criteria.
Complexity
Time Complexity: This is O(M*N) where M is the number of moves and N is possible placements. Space Complexity is based on the memoization array size, effectively O(n*board size) which is reduced by efficient storing of results.
Approach 3: 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.
We enumerate each piece in order. For each piece, we can choose not to move or move according to the rules. We use an array dist[i] to record the movement of the i-th piece, where dist[i][x][y] represents the time when the i-th piece passes through the coordinate (x, y). We use an array end[i] to record the endpoint coordinates and time of the i-th piece. During the search, we need to determine whether the current piece can stop moving and whether it can continue moving in the current direction.
We define a method checkStop(i, x, y, t) to determine whether the i-th piece can stop at coordinate (x, y) at time t. If for all previous pieces j, dist[j][x][y] < t, then the i-th piece can stop moving.
Additionally, we define a method checkPass(i, x, y, t) to determine whether the i-th piece can pass through coordinate (x, y) at time t. If any other piece j also passes through coordinate (x, y) at time t, or if any other piece j stops at (x, y) and the time does not exceed t, then the i-th piece cannot pass through coordinate (x, y) at time t.
The time complexity is O((n times M)^n), and the space complexity is O(n times M). Here, n is the number of pieces, and M is the movement range of each piece.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | The time complexity of the solution is O(8^n), assuming a worst-case scenario of exploring all potential moves for n pieces. The space complexity is O(n) for recursive call stack usage. |
| Dynamic Programming Approach | Time Complexity: This is O(M*N) where M is the number of moves and N is possible placements. Space Complexity is based on the memoization array size, effectively O(n*board size) which is reduced by efficient storing of results. |
| DFS | — |
Detailed Complexity Analysis
| 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 |
Video Solution
【每日一题】LeetCode 2056. Number of Valid Move Combinations On Chessboard • Huifeng Guan • 1,117 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Number of Valid Move Combinations On Chessboard easy or hard?
Number of Valid Move Combinations On Chessboard Python/Java solution
How to solve Number of Valid Move Combinations On Chessboard in O(n)?
What is the best approach for Number of Valid Move Combinations On Chessboard?
Is Number of Valid Move Combinations On Chessboard asked at Google/Amazon/Meta?
What data structure is used in Number of Valid Move Combinations On Chessboard?
What is the time complexity of Number of Valid Move Combinations On Chessboard?
Ready to solve this problem?
Practice Number of Valid Move Combinations On Chessboard with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor