# Number of Valid Move Combinations On Chessboard **Difficulty:** HARD [External](https://leetcode.com/problems/number-of-valid-move-combinations-on-chessboard) Canonical: https://scaleengineer.com/dsa/problems/number-of-valid-move-combinations-on-chessboard **Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking) **Data structures:** Array, String **Companies:** [PayPal](https://scaleengineer.com/companies/paypal) --- ## Problem 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:** ![](https://assets.glich.co/dsa/number-of-valid-move-combinations-on-chessboard/image0.png) **Input:** pieces = ["rook"], positions = [[1,1]] **Output:** 15 **Explanation:** The image above shows the possible squares the piece can move to. **Example 2:** ![](https://assets.glich.co/dsa/number-of-valid-move-combinations-on-chessboard/image1.png) **Input:** pieces = ["queen"], positions = [[1,1]] **Output:** 22 **Explanation:** The image above shows the possible squares the piece can move to. **Example 3:** ![](https://assets.glich.co/dsa/number-of-valid-move-combinations-on-chessboard/image2.png) **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.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. # Approaches ## Brute-Force Generation and Validation A straightforward approach that first generates all possible move combinations and then iterates through them to validate each one. **Time:** O(M * n^2 * d), where `M` is the total number of move combinations, `n` is the number of pieces, and `d` is the maximum travel distance on the board (which is 7). The complexity is dominated by validating every single combination. · **Space:** O(M * n). The primary memory cost is storing the list of all `M` combinations, where each combination stores `n` coordinates. This can easily lead to out-of-memory errors. **Pros:** Conceptually simple and easy to separate the logic for generation and validation. **Cons:** Extremely high space complexity, making it impractical for the given constraints.; Can be slow due to the overhead of creating and managing a large data structure for all combinations. ### Explanation This method breaks the problem into two main parts. First, we determine every possible destination for each piece. Then, we create the Cartesian product of these move sets to get a complete list of all move combinations. For example, if piece 1 has 15 moves and piece 2 has 22 moves, we generate all 15 * 22 = 330 combinations. After generating this list, we iterate through it. For each combination, we simulate the pieces' movements second by second. If at any point in time two pieces occupy the same square, the combination is marked invalid. If all pieces reach their destinations without any collisions along their paths, the combination is valid, and we increment our counter. While simple to understand, this approach is highly inefficient in terms of memory because it requires storing all combinations, which can be a very large number. ### Algorithm - For each piece `i`, generate a list of all its possible destination squares, `Moves_i`. - Generate the Cartesian product of `Moves_0, Moves_1, ..., Moves_{n-1}` to get a list of all move combinations. - Initialize `valid_count = 0`. - For each `combination` in the list of all move combinations: - If `is_valid(combination)` is true: - `valid_count++`. - Return `valid_count`. - The `is_valid` function simulates movement second by second and checks for collisions. ## Backtracking with Simulation An efficient approach that combines move generation and validation using recursion. It explores move combinations one by one, validating each full combination as it's found, thus avoiding the high memory usage of storing all combinations. **Time:** O(M * n^2 * d), where `M` is the total number of move combinations, `n` is the number of pieces, and `d` is the maximum travel distance (7). The time complexity is asymptotically the same as the brute-force approach, but it's the most efficient possible for this problem structure given the constraints. · **Space:** O(n * d). The space is dominated by the recursion stack depth (`O(n)`) and the auxiliary arrays used within the validation function (`O(n)`). Pre-calculating moves takes `O(n * max_moves)`, which is a constant factor. This is a significant improvement over the brute-force approach. **Pros:** Highly space-efficient, avoiding memory issues.; It is the most practical and performant solution for the given constraints. **Cons:** The time complexity remains exponential, which is inherent to the problem's combinatorial nature.; The code can be more complex to write and debug due to recursion. ### Explanation This method uses a backtracking algorithm to explore the search space of all possible move combinations. We define a recursive function that tries to assign a destination to one piece at a time. The function takes the index of the current piece to be moved as a parameter. It iterates through all possible destinations for that piece. For each choice, it makes a recursive call for the next piece. The base case for the recursion is when we have assigned destinations to all `n` pieces. At this point, we have a complete move combination. We then trigger a validation function. The validation function simulates the simultaneous movement of all pieces from their start positions to their chosen destinations, second by second. It calculates the maximum travel time required among all pieces and simulates up to that time. In each time step, it updates the positions of all pieces and checks for collisions (two or more pieces on the same square). If a collision is detected at any time, the combination is invalid. If the simulation completes without collisions, the combination is valid. By validating each combination as soon as it's generated and then backtracking, we avoid storing them, leading to a significant space optimization. ```java class Solution { private int n; private String[] pieces; private int[][] initialPositions; private List> possibleMoves; private final int[][] ROOK_DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private final int[][] BISHOP_DIRS = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; public int countCombinations(String[] pieces, int[][] positions) { this.n = pieces.length; this.pieces = pieces; this.initialPositions = new int[n][2]; for (int i = 0; i < n; i++) { this.initialPositions[i][0] = positions[i][0] - 1; this.initialPositions[i][1] = positions[i][1] - 1; } this.possibleMoves = new ArrayList<>(); for (int i = 0; i < n; i++) { possibleMoves.add(generateMoves(pieces[i], this.initialPositions[i])); } return backtrack(0, new int[n][2]); } private int backtrack(int pieceIndex, int[][] destinations) { if (pieceIndex == n) { return isCombinationValid(destinations) ? 1 : 0; } int count = 0; List movesForCurrentPiece = possibleMoves.get(pieceIndex); for (int[] dest : movesForCurrentPiece) { destinations[pieceIndex] = dest; count += backtrack(pieceIndex + 1, destinations); } return count; } private boolean isCombinationValid(int[][] destinations) { int[] travelTimes = new int[n]; int maxTime = 0; for (int i = 0; i < n; i++) { travelTimes[i] = Math.max(Math.abs(destinations[i][0] - initialPositions[i][0]), Math.abs(destinations[i][1] - initialPositions[i][1])); maxTime = Math.max(maxTime, travelTimes[i]); } if (maxTime == 0) return true; for (int t = 1; t <= maxTime; t++) { int[][] positionsAtT = new int[n][2]; for (int i = 0; i < n; i++) { if (t <= travelTimes[i]) { int pr = initialPositions[i][0]; int pc = initialPositions[i][1]; int dr = destinations[i][0]; int dc = destinations[i][1]; positionsAtT[i][0] = pr + t * Integer.signum(dr - pr); positionsAtT[i][1] = pc + t * Integer.signum(dc - pc); } else { positionsAtT[i][0] = destinations[i][0]; positionsAtT[i][1] = destinations[i][1]; } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (positionsAtT[i][0] == positionsAtT[j][0] && positionsAtT[i][1] == positionsAtT[j][1]) { return false; } } } } return true; } private List generateMoves(String piece, int[] pos) { List moves = new ArrayList<>(); int r = pos[0]; int c = pos[1]; moves.add(new int[]{r, c}); // Stay put if (piece.equals("rook") || piece.equals("queen")) { for (int[] dir : ROOK_DIRS) { for (int i = 1; i < 8; i++) { int nr = r + i * dir[0]; int nc = c + i * dir[1]; if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8) { moves.add(new int[]{nr, nc}); } else { break; } } } } if (piece.equals("bishop") || piece.equals("queen")) { for (int[] dir : BISHOP_DIRS) { for (int i = 1; i < 8; i++) { int nr = r + i * dir[0]; int nc = c + i * dir[1]; if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8) { moves.add(new int[]{nr, nc}); } else { break; } } } } return moves; } } ``` ### Algorithm - Pre-calculate all possible moves for each piece and store them. - Define a recursive function `backtrack(pieceIndex, destinations)`. - **Base Case**: If `pieceIndex` equals the number of pieces `n`, a full combination is formed in `destinations`. Call `isCombinationValid(destinations)`. Return 1 if valid, 0 otherwise. - **Recursive Step**: For the current `pieceIndex`: - Iterate through all its pre-calculated possible moves. - For each move, update `destinations[pieceIndex]`. - Make a recursive call `backtrack(pieceIndex + 1, destinations)`. - Sum the results from the recursive calls. - The `isCombinationValid` function simulates the moves over time and checks for collisions at each time step. # Solutions ### Java ```java class Solution { int n , m = 9 , ans ; int [][][] dist ; int [][] end ; String [] pieces ; int [][] positions ; int [][] rookDirs = { { 1 , 0 }, {- 1 , 0 }, { 0 , 1 }, { 0 , - 1 } }; int [][] bishopDirs = { { 1 , 1 }, { 1 , - 1 }, {- 1 , 1 }, {- 1 , - 1 } }; int [][] queenDirs = { { 1 , 0 }, {- 1 , 0 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 1 }, { 1 , - 1 }, {- 1 , 1 }, {- 1 , - 1 } }; public int countCombinations ( String [] pieces , int [][] positions ) { n = pieces . length ; dist = new int [ n ][ m ][ m ]; end = new int [ n ][ 3 ]; ans = 0 ; this . pieces = pieces ; this . positions = positions ; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= n ) { ans ++; return ; } int x = positions [ i ][ 0 ], y = positions [ i ][ 1 ]; resetDist ( i ); dist [ i ][ x ][ y ] = 0 ; end [ i ] = new int [] { x , y , 0 }; if ( checkStop ( i , x , y , 0 )) { dfs ( i + 1 ); } int [][] dirs = getDirs ( pieces [ i ]); for ( int [] dir : dirs ) { resetDist ( i ); dist [ i ][ x ][ y ] = 0 ; int nx = x + dir [ 0 ], ny = y + dir [ 1 ], nt = 1 ; while ( isValid ( nx , ny ) && checkPass ( i , nx , ny , nt )) { dist [ i ][ nx ][ ny ] = nt ; end [ i ] = new int [] { nx , ny , nt }; if ( checkStop ( i , nx , ny , nt )) { dfs ( i + 1 ); } nx += dir [ 0 ]; ny += dir [ 1 ]; nt ++; } } } private void resetDist ( int i ) { for ( int j = 0 ; j < m ; j ++) { for ( int k = 0 ; k < m ; k ++) { dist [ i ][ j ][ k ] = - 1 ; } } } private boolean checkStop ( int i , int x , int y , int t ) { for ( int j = 0 ; j < i ; j ++) { if ( dist [ j ][ x ][ y ] >= t ) { return false ; } } return true ; } private boolean checkPass ( int i , int x , int y , int t ) { for ( int j = 0 ; j < i ; j ++) { if ( dist [ j ][ x ][ y ] == t ) { return false ; } if ( end [ j ][ 0 ] == x && end [ j ][ 1 ] == y && end [ j ][ 2 ] <= t ) { return false ; } } return true ; } private boolean isValid ( int x , int y ) { return x >= 1 && x < m && y >= 1 && y < m ; } private int [][] getDirs ( String piece ) { char c = piece . charAt ( 0 ); return switch ( c ) { case 'r' -> rookDirs ; case 'b' -> bishopDirs ; default -> queenDirs ; }; } } ``` ### CPP ```cpp class Solution { public: int countCombinations(vector &pieces, vector> &positions) { int n = pieces.size(); const int m = 9; int ans = 0; vector>> dist( n, vector>(m, vector(m, -1))); vector> end(n, vector(3)); const int rookDirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; const int bishopDirs[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; const int queenDirs[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; auto resetDist = [&](int i) { for (int j = 0; j < m; j++) { for (int k = 0; k < m; k++) { dist[i][j][k] = -1; } } }; auto checkStop = [&](int i, int x, int y, int t) -> bool { for (int j = 0; j < i; j++) { if (dist[j][x][y] >= t) { return false; } } return true; }; auto checkPass = [&](int i, int x, int y, int t) -> bool { for (int j = 0; j < i; j++) { if (dist[j][x][y] == t) { return false; } if (end[j][0] == x && end[j][1] == y && end[j][2] <= t) { return false; } } return true; }; auto isValid = [&](int x, int y) -> bool { return x >= 1 && x < m && y >= 1 && y < m; }; auto getDirs = [&](const string &piece) -> const int (*)[2] { char c = piece[0]; if (c == 'r') { return rookDirs; } if (c == 'b') { return bishopDirs; } return queenDirs; }; auto dfs = [&](auto &&dfs, int i) -> void { if (i >= n) { ans++; return; } int x = positions[i][0], y = positions[i][1]; resetDist(i); dist[i][x][y] = 0; end[i] = {x, y, 0}; if (checkStop(i, x, y, 0)) { dfs(dfs, i + 1); } const int (*dirs)[2] = getDirs(pieces[i]); int dirsSize = (pieces[i][0] == 'q') ? 8 : 4; for (int d = 0; d < dirsSize; d++) { resetDist(i); dist[i][x][y] = 0; int nx = x + dirs[d][0], ny = y + dirs[d][1], nt = 1; while (isValid(nx, ny) && checkPass(i, nx, ny, nt)) { dist[i][nx][ny] = nt; end[i] = {nx, ny, nt}; if (checkStop(i, nx, ny, nt)) { dfs(dfs, i + 1); } nx += dirs[d][0]; ny += dirs[d][1]; nt++; } } }; dfs(dfs, 0); return ans; } }; ``` ### Python ```python 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 ```