Facebook Pixel

2056. Number of Valid Move Combinations On Chessboard

HardArrayStringBacktrackingSimulation
Leetcode Link

Problem Description

You have an 8 x 8 chessboard with n chess pieces on it. Each piece is either a rook, queen, or bishop. You're given:

  • pieces[i]: a string array describing the type of each piece
  • positions[i] = [ri, ci]: the starting position of the i-th piece (using 1-based coordinates)

You need to count how many valid move combinations exist where all pieces move simultaneously.

Movement Rules:

  • Rook: moves horizontally or vertically (4 directions)
  • Queen: moves horizontally, vertically, or diagonally (8 directions)
  • Bishop: moves diagonally only (4 directions)

How Movement Works:

  1. You choose a destination square for each piece (can be its current position if it doesn't move)
  2. Starting at time 0, all pieces move simultaneously toward their destinations
  3. Each second, a piece moves exactly one square in its chosen direction
  4. A piece stops when it reaches its destination

Valid vs Invalid Combinations:

  • A combination is invalid if at any point in time, two or more pieces occupy the same square
  • A combination is valid if no two pieces ever occupy the same square during their movement

Special Rules:

  • No two pieces start at the same position
  • A piece can choose to stay at its current position (not move at all)
  • Two adjacent pieces can swap positions by moving past each other in one second

The goal is to count all possible valid move combinations where each piece either stays put or moves to a reachable destination following its movement rules, and no collisions occur during the simultaneous movement.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • No: While we have a chessboard grid, this problem is not about graph traversal with nodes and edges. Instead, it's about finding valid combinations of simultaneous piece movements.

Need to solve for kth smallest/largest?

  • No: We're counting all valid move combinations, not finding a specific kth element.

Involves Linked Lists?

  • No: The problem uses arrays to represent pieces and positions on a chessboard, not linked lists.

Does the problem have small constraints?

  • Yes: The problem explicitly states there are at most 4 pieces (n ≤ 4), and each piece has at most 8 possible directions to move. The total search space is manageable with these small constraints.

Brute force / Backtracking?

  • Yes: With small constraints and the need to explore all possible valid combinations, backtracking is the appropriate approach. We need to:
    • Try each possible move (or no move) for each piece
    • Check if the current combination is valid (no collisions)
    • Backtrack if invalid and try other combinations
    • Count all valid complete combinations

Conclusion: The flowchart correctly leads us to use a Backtracking approach. We recursively try all possible moves for each piece, validate that pieces don't collide during their simultaneous movement, and count the valid combinations. The small constraint of at most 4 pieces makes this exhaustive search feasible.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that with at most 4 pieces and each piece having at most 8 directional choices (plus the option to stay still), we can afford to explore all possible combinations exhaustively.

Think of this problem as making a decision tree. For each piece, we decide:

  1. Should it stay where it is?
  2. If it moves, which direction should it go?
  3. How far should it travel in that direction?

Since pieces move simultaneously, we need to track their positions over time. The critical observation is that collisions can happen in two ways:

  • Meeting at the same square: Two pieces arrive at the same position at the same time
  • One piece passing through another's stopping point: A piece continues moving through a square where another piece has already stopped

To handle this, we can use a time-based tracking system. For each piece, we record:

  • dist[i][x][y]: The time when piece i passes through position (x, y)
  • end[i]: Where and when piece i stops moving

The backtracking approach naturally fits because:

  1. We process pieces one by one (depth-first)
  2. For each piece, we try all valid moves
  3. Before committing to a move, we check if it creates any conflicts with previously placed pieces
  4. If valid, we recurse to the next piece
  5. If we successfully place all pieces without conflicts, we've found one valid combination
  6. We backtrack to explore other possibilities

The beauty of this approach is that by processing pieces sequentially and checking conflicts immediately, we can prune invalid branches early. When checking if piece i can make a certain move, we only need to verify it doesn't conflict with pieces 0 through i-1 that we've already placed.

This transforms a complex simultaneous movement problem into a simpler sequential decision problem where we validate each decision against previous ones.

Learn more about Backtracking patterns.

Solution Approach

The implementation uses DFS with backtracking to explore all possible move combinations. Let's walk through the key components:

1. Direction Setup

First, we define the possible directions for each piece type:

  • Rook: 4 directions (horizontal and vertical)
  • Bishop: 4 directions (diagonals only)
  • Queen: 8 directions (all of the above)

The get_dirs() function returns the appropriate direction vectors based on the piece type.

2. Core Data Structures

  • dist[i][x][y]: A 3D array tracking when piece i passes through position (x, y). Value is -1 if never visited, otherwise stores the time.
  • end[i]: Stores (x, y, t) representing where piece i stops and when it stops.
  • ans: Counter for valid combinations.

3. Validation Functions

checkStop(i, x, y, t): Checks if piece i can stop at position (x, y) at time t.

  • Returns True if all previously placed pieces (indices 0 to i-1) either don't pass through (x, y) or pass through it at a different time than t.
  • This ensures no collision at the stopping point.

checkPass(i, x, y, t): Checks if piece i can pass through position (x, y) at time t.

  • Returns False if any previous piece j also passes through at the same time (dist[j][x][y] == t)
  • Returns False if any previous piece j has stopped at (x, y) and its stop time is ≤ t
  • This prevents both simultaneous collisions and passing through occupied squares.

4. DFS Backtracking Process

The dfs(i) function processes piece i:

  1. Base Case: If i >= n, all pieces are successfully placed, increment ans.

  2. Option 1 - Stay Put:

    • Set dist[i][x][y] = 0 (piece at starting position at time 0)
    • Set end[i] = (x, y, 0) (stops immediately)
    • If checkStop() validates no conflicts, recurse to next piece

  3. Option 2 - Move in Each Valid Direction:

    • For each possible direction (dx, dy):
      • Reset dist[i] array
      • Simulate movement step by step:
        • Move to (nx, ny) at time nt
        • Check if position is on board and checkPass() allows passage
        • Mark dist[i][nx][ny] = nt
        • Try stopping here: set end[i] = (nx, ny, nt)
        • If checkStop() validates, recurse to next piece
        • Continue moving in same direction for next iteration

5. Main Execution

  • Initialize all data structures with board size 9 (using 1-based indexing)
  • Start DFS from piece 0
  • Return the total count of valid combinations

The algorithm cleverly handles the simultaneous movement problem by:

  • Processing pieces sequentially in the search
  • Recording time-stamped positions for validation
  • Using early pruning when conflicts are detected
  • Exploring all possibilities through backtracking

The time complexity is manageable due to the small constraint (at most 4 pieces), making this exhaustive search practical.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example with 2 pieces on a chessboard:

  • Piece 0: Rook at position (1, 1)
  • Piece 1: Bishop at position (2, 3)

Step 1: Process Piece 0 (Rook)

The DFS starts with piece 0. We have two main options:

Option A: Rook stays at (1, 1)

  • Set dist[0][1][1] = 0 (rook is at its start position at time 0)
  • Set end[0] = (1, 1, 0) (stops immediately)
  • Check if this is valid with checkStop(0, 1, 1, 0) - passes since no previous pieces exist
  • Recurse to piece 1

Option B: Rook moves right to (1, 2)

  • Initialize movement: dist[0][1][1] = 0 (starting position)
  • At time 1: move to (1, 2), set dist[0][1][2] = 1
  • Check with checkPass(0, 1, 2, 1) - passes (no previous pieces)
  • Try stopping here: end[0] = (1, 2, 1)
  • Check with checkStop(0, 1, 2, 1) - passes
  • Recurse to piece 1

Step 2: Process Piece 1 (Bishop) - Following Option B above

Now piece 1 needs to be placed, with piece 0 having moved from (1, 1) to (1, 2).

Option A: Bishop stays at (2, 3)

  • Set dist[1][2][3] = 0
  • Set end[1] = (2, 3, 0)
  • Check with checkStop(1, 2, 3, 0):
    • Does piece 0 pass through (2, 3)? No (dist[0][2][3] = -1)
    • Valid! This is one valid combination

Option B: Bishop moves diagonally to (1, 2)

  • Initialize: dist[1][2][3] = 0
  • At time 1: move to (1, 2), try to set dist[1][1][2] = 1
  • Check with checkPass(1, 1, 2, 1):
    • Piece 0 passes through (1, 2) at time 1 (dist[0][1][2] = 1)
    • Collision detected! Both pieces at (1, 2) at time 1
    • This branch is pruned - invalid combination

Option C: Bishop moves diagonally to (3, 4)

  • Initialize: dist[1][2][3] = 0
  • At time 1: move to (3, 4), set dist[1][3][4] = 1
  • Check with checkPass(1, 3, 4, 1) - passes (piece 0 never goes there)
  • Try stopping: end[1] = (3, 4, 1)
  • Check with checkStop(1, 3, 4, 1) - passes
  • Valid! This is another valid combination

Step 3: Backtrack and Continue

The algorithm backtracks to explore all other possibilities:

  • Rook moves to (1, 3), (1, 4), etc. (continuing right)
  • Rook moves up to (2, 1), (3, 1), etc.
  • Rook moves down (if valid)
  • Rook moves left (if valid)

For each rook position, we then try all bishop moves, validating collisions at each step.

Key Observations from Example:

  1. Time-based collision detection: When both pieces tried to be at (1, 2) at time 1, the collision was immediately detected through the dist array comparison.

  2. Sequential processing with validation: Even though pieces move simultaneously in the problem, we process them sequentially in our search, validating each new piece against all previously placed pieces.

  3. Early pruning: Invalid moves are detected immediately (like the bishop collision), preventing exploration of invalid subtrees.

  4. Backtracking restoration: After exploring bishop placements for one rook position, we backtrack (resetting bishop's dist and end data) and try the next rook position.

The final answer would be the sum of all valid combinations found through this exhaustive search with pruning.

Solution Implementation

1from typing import List, Tuple
2
3# Direction vectors for different chess pieces
4ROOK_DIRECTIONS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
5BISHOP_DIRECTIONS = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
6QUEEN_DIRECTIONS = ROOK_DIRECTIONS + BISHOP_DIRECTIONS
7
8
9def get_directions(piece: str) -> List[Tuple[int, int]]:
10    """Get movement directions based on piece type."""
11    match piece[0]:
12        case "r":  # Rook
13            return ROOK_DIRECTIONS
14        case "b":  # Bishop
15            return BISHOP_DIRECTIONS
16        case _:    # Queen (default)
17            return QUEEN_DIRECTIONS
18
19
20class Solution:
21    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
22        """
23        Count all valid movement combinations where pieces don't collide.
24      
25        Args:
26            pieces: List of piece types ('rook', 'bishop', or 'queen')
27            positions: Starting positions of each piece [row, col]
28      
29        Returns:
30            Number of valid movement combinations
31        """
32      
33        def can_stop_at_position(piece_index: int, row: int, col: int, time: int) -> bool:
34            """
35            Check if a piece can stop at given position without collision.
36            A piece can stop if no previous piece passes through this position at or after this time.
37            """
38            for prev_piece in range(piece_index):
39                # Check if previous piece passes through this position at or after current time
40                if time_to_reach[prev_piece][row][col] >= time:
41                    return False
42            return True
43      
44        def can_pass_through_position(piece_index: int, row: int, col: int, time: int) -> bool:
45            """
46            Check if a piece can pass through given position at given time.
47            Cannot pass if:
48            1. Another piece is at this position at the same time
49            2. Another piece has stopped at this position before or at this time
50            """
51            for prev_piece in range(piece_index):
52                # Check if previous piece is at this position at the same time
53                if time_to_reach[prev_piece][row][col] == time:
54                    return False
55                # Check if previous piece has stopped at this position
56                stop_row, stop_col, stop_time = final_positions[prev_piece]
57                if stop_row == row and stop_col == col and stop_time <= time:
58                    return False
59            return True
60      
61        def explore_movements(piece_index: int) -> None:
62            """
63            Recursively explore all possible movements for pieces.
64            Uses DFS to try all valid movement combinations.
65            """
66            # Base case: all pieces have been assigned movements
67            if piece_index >= num_pieces:
68                nonlocal total_combinations
69                total_combinations += 1
70                return
71          
72            start_row, start_col = positions[piece_index]
73          
74            # Option 1: Piece doesn't move (stays at starting position)
75            time_to_reach[piece_index][:] = [[-1] * board_size for _ in range(board_size)]
76            time_to_reach[piece_index][start_row][start_col] = 0
77            final_positions[piece_index] = (start_row, start_col, 0)
78          
79            if can_stop_at_position(piece_index, start_row, start_col, 0):
80                explore_movements(piece_index + 1)
81          
82            # Option 2: Piece moves in one of its valid directions
83            valid_directions = get_directions(pieces[piece_index])
84          
85            for delta_row, delta_col in valid_directions:
86                # Reset time matrix for this piece
87                time_to_reach[piece_index][:] = [[-1] * board_size for _ in range(board_size)]
88                time_to_reach[piece_index][start_row][start_col] = 0
89              
90                # Try moving in this direction
91                current_row = start_row + delta_row
92                current_col = start_col + delta_col
93                current_time = 1
94              
95                # Continue moving in the same direction until hitting board edge or collision
96                while (1 <= current_row < board_size and 
97                       1 <= current_col < board_size and 
98                       can_pass_through_position(piece_index, current_row, current_col, current_time)):
99                  
100                    # Mark this position as reachable at current time
101                    time_to_reach[piece_index][current_row][current_col] = current_time
102                    final_positions[piece_index] = (current_row, current_col, current_time)
103                  
104                    # Try stopping at this position
105                    if can_stop_at_position(piece_index, current_row, current_col, current_time):
106                        explore_movements(piece_index + 1)
107                  
108                    # Move to next position in the same direction
109                    current_row += delta_row
110                    current_col += delta_col
111                    current_time += 1
112      
113        # Initialize variables
114        num_pieces = len(pieces)
115        board_size = 9  # Chess board is 8x8, but using 1-indexed (1-8)
116      
117        # time_to_reach[i][r][c] = time when piece i reaches position (r,c), -1 if never
118        time_to_reach = [[[-1] * board_size for _ in range(board_size)] for _ in range(num_pieces)]
119      
120        # final_positions[i] = (row, col, time) where piece i stops
121        final_positions = [(0, 0, 0) for _ in range(num_pieces)]
122      
123        # Counter for valid combinations
124        total_combinations = 0
125      
126        # Start DFS exploration
127        explore_movements(0)
128      
129        return total_combinations
130
1class Solution {
2    // Board dimensions and result counter
3    private int numPieces;
4    private static final int BOARD_SIZE = 9;
5    private int validCombinationsCount;
6  
7    // State tracking arrays
8    private int[][][] timeAtPosition;  // [piece][row][col] = time when piece is at position
9    private int[][] finalState;         // [piece] = {finalRow, finalCol, arrivalTime}
10  
11    // Input data
12    private String[] pieceTypes;
13    private int[][] startPositions;
14  
15    // Direction vectors for different piece types
16    private static final int[][] ROOK_DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
17    private static final int[][] BISHOP_DIRECTIONS = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
18    private static final int[][] QUEEN_DIRECTIONS = {
19        {1, 0}, {-1, 0}, {0, 1}, {0, -1},  // Rook moves
20        {1, 1}, {1, -1}, {-1, 1}, {-1, -1}  // Bishop moves
21    };
22
23    /**
24     * Counts all valid movement combinations for the given chess pieces
25     * @param pieces Array of piece types ("rook", "bishop", or "queen")
26     * @param positions Starting positions for each piece [row, col]
27     * @return Number of valid movement combinations
28     */
29    public int countCombinations(String[] pieces, int[][] positions) {
30        // Initialize instance variables
31        numPieces = pieces.length;
32        timeAtPosition = new int[numPieces][BOARD_SIZE][BOARD_SIZE];
33        finalState = new int[numPieces][3];
34        validCombinationsCount = 0;
35        this.pieceTypes = pieces;
36        this.startPositions = positions;
37
38        // Start depth-first search from first piece
39        explorePieceMoves(0);
40        return validCombinationsCount;
41    }
42
43    /**
44     * Recursively explores all valid moves for each piece using DFS
45     * @param pieceIndex Current piece being processed
46     */
47    private void explorePieceMoves(int pieceIndex) {
48        // Base case: all pieces have been assigned valid moves
49        if (pieceIndex >= numPieces) {
50            validCombinationsCount++;
51            return;
52        }
53
54        int startRow = startPositions[pieceIndex][0];
55        int startCol = startPositions[pieceIndex][1];
56      
57        // Option 1: Piece stays at starting position
58        clearTimeMatrix(pieceIndex);
59        timeAtPosition[pieceIndex][startRow][startCol] = 0;
60        finalState[pieceIndex] = new int[] {startRow, startCol, 0};
61      
62        if (isValidFinalPosition(pieceIndex, startRow, startCol, 0)) {
63            explorePieceMoves(pieceIndex + 1);
64        }
65
66        // Option 2: Piece moves in each valid direction
67        int[][] validDirections = getDirectionsForPiece(pieceTypes[pieceIndex]);
68      
69        for (int[] direction : validDirections) {
70            clearTimeMatrix(pieceIndex);
71            timeAtPosition[pieceIndex][startRow][startCol] = 0;
72          
73            int currentRow = startRow + direction[0];
74            int currentCol = startCol + direction[1];
75            int currentTime = 1;
76
77            // Continue moving in this direction while valid
78            while (isWithinBounds(currentRow, currentCol) && 
79                   canPassThrough(pieceIndex, currentRow, currentCol, currentTime)) {
80              
81                // Mark this position as visited at this time
82                timeAtPosition[pieceIndex][currentRow][currentCol] = currentTime;
83                finalState[pieceIndex] = new int[] {currentRow, currentCol, currentTime};
84              
85                // Try stopping at this position
86                if (isValidFinalPosition(pieceIndex, currentRow, currentCol, currentTime)) {
87                    explorePieceMoves(pieceIndex + 1);
88                }
89              
90                // Continue moving in same direction
91                currentRow += direction[0];
92                currentCol += direction[1];
93                currentTime++;
94            }
95        }
96    }
97
98    /**
99     * Resets the time matrix for a specific piece
100     * @param pieceIndex Index of the piece to reset
101     */
102    private void clearTimeMatrix(int pieceIndex) {
103        for (int row = 0; row < BOARD_SIZE; row++) {
104            for (int col = 0; col < BOARD_SIZE; col++) {
105                timeAtPosition[pieceIndex][row][col] = -1;
106            }
107        }
108    }
109
110    /**
111     * Checks if a piece can stop at given position without collision
112     * @param pieceIndex Current piece index
113     * @param row Target row
114     * @param col Target column
115     * @param time Time when piece stops
116     * @return true if position is valid for stopping
117     */
118    private boolean isValidFinalPosition(int pieceIndex, int row, int col, int time) {
119        // Check against all previously placed pieces
120        for (int previousPiece = 0; previousPiece < pieceIndex; previousPiece++) {
121            // If another piece is still moving through this position after our stop time
122            if (timeAtPosition[previousPiece][row][col] >= time) {
123                return false;
124            }
125        }
126        return true;
127    }
128
129    /**
130     * Checks if a piece can pass through given position during movement
131     * @param pieceIndex Current piece index
132     * @param row Current row
133     * @param col Current column  
134     * @param time Current time
135     * @return true if piece can pass through without collision
136     */
137    private boolean canPassThrough(int pieceIndex, int row, int col, int time) {
138        // Check against all previously placed pieces
139        for (int previousPiece = 0; previousPiece < pieceIndex; previousPiece++) {
140            // Check for collision at same time
141            if (timeAtPosition[previousPiece][row][col] == time) {
142                return false;
143            }
144            // Check if another piece has stopped here before we pass
145            if (finalState[previousPiece][0] == row && 
146                finalState[previousPiece][1] == col && 
147                finalState[previousPiece][2] <= time) {
148                return false;
149            }
150        }
151        return true;
152    }
153
154    /**
155     * Checks if position is within board boundaries
156     * @param row Row coordinate
157     * @param col Column coordinate
158     * @return true if position is valid
159     */
160    private boolean isWithinBounds(int row, int col) {
161        return row >= 1 && row < BOARD_SIZE && col >= 1 && col < BOARD_SIZE;
162    }
163
164    /**
165     * Returns movement directions based on piece type
166     * @param pieceType Type of chess piece
167     * @return Array of direction vectors
168     */
169    private int[][] getDirectionsForPiece(String pieceType) {
170        char firstChar = pieceType.charAt(0);
171        return switch (firstChar) {
172            case 'r' -> ROOK_DIRECTIONS;    // Rook moves horizontally/vertically
173            case 'b' -> BISHOP_DIRECTIONS;  // Bishop moves diagonally
174            default -> QUEEN_DIRECTIONS;    // Queen combines rook and bishop moves
175        };
176    }
177}
178
1class Solution {
2public:
3    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
4        int numPieces = pieces.size();
5        const int BOARD_SIZE = 9;  // Chess board is 8x8, using 1-indexed
6        int totalCombinations = 0;
7      
8        // Store the distance/time when each piece reaches each position
9        // dist[pieceIndex][row][col] = time when piece reaches (row, col), -1 if not visited
10        vector<vector<vector<int>>> distanceMap(numPieces, 
11            vector<vector<int>>(BOARD_SIZE, vector<int>(BOARD_SIZE, -1)));
12      
13        // Store ending position and time for each piece
14        // endPosition[pieceIndex] = {row, col, arrivalTime}
15        vector<vector<int>> endPosition(numPieces, vector<int>(3));
16      
17        // Direction vectors for different piece types
18        const int ROOK_DIRECTIONS[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19        const int BISHOP_DIRECTIONS[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
20        const int QUEEN_DIRECTIONS[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, 
21                                           {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
22      
23        // Reset distance map for a specific piece
24        auto resetDistanceForPiece = [&](int pieceIndex) {
25            for (int row = 0; row < BOARD_SIZE; row++) {
26                for (int col = 0; col < BOARD_SIZE; col++) {
27                    distanceMap[pieceIndex][row][col] = -1;
28                }
29            }
30        };
31      
32        // Check if piece can stop at position (x, y) at time t without collision
33        auto canStopAtPosition = [&](int currentPieceIndex, int x, int y, int stopTime) -> bool {
34            // Check collision with all previously placed pieces
35            for (int prevPieceIndex = 0; prevPieceIndex < currentPieceIndex; prevPieceIndex++) {
36                // If another piece occupies this position at or after stopTime, collision occurs
37                if (distanceMap[prevPieceIndex][x][y] >= stopTime) {
38                    return false;
39                }
40            }
41            return true;
42        };
43      
44        // Check if piece can pass through position (x, y) at time t without collision
45        auto canPassThroughPosition = [&](int currentPieceIndex, int x, int y, int passTime) -> bool {
46            for (int prevPieceIndex = 0; prevPieceIndex < currentPieceIndex; prevPieceIndex++) {
47                // Check if another piece is at this position at the same time
48                if (distanceMap[prevPieceIndex][x][y] == passTime) {
49                    return false;
50                }
51                // Check if another piece has stopped at this position before or at passTime
52                if (endPosition[prevPieceIndex][0] == x && 
53                    endPosition[prevPieceIndex][1] == y && 
54                    endPosition[prevPieceIndex][2] <= passTime) {
55                    return false;
56                }
57            }
58            return true;
59        };
60      
61        // Check if position is within board boundaries (1-indexed board)
62        auto isValidPosition = [&](int x, int y) -> bool {
63            return x >= 1 && x < BOARD_SIZE && y >= 1 && y < BOARD_SIZE;
64        };
65      
66        // Get direction vectors based on piece type
67        auto getDirectionVectors = [&](const string& pieceType) -> const int(*)[2] {
68            char firstChar = pieceType[0];
69            if (firstChar == 'r') {
70                return ROOK_DIRECTIONS;
71            }
72            if (firstChar == 'b') {
73                return BISHOP_DIRECTIONS;
74            }
75            return QUEEN_DIRECTIONS;  // Queen
76        };
77      
78        // DFS to try all possible moves for each piece
79        auto exploreMoves = [&](this auto&& exploreMoves, int pieceIndex) -> void {
80            // Base case: all pieces have been placed
81            if (pieceIndex >= numPieces) {
82                totalCombinations++;
83                return;
84            }
85          
86            int startX = positions[pieceIndex][0];
87            int startY = positions[pieceIndex][1];
88          
89            // Option 1: Piece stays at starting position
90            resetDistanceForPiece(pieceIndex);
91            distanceMap[pieceIndex][startX][startY] = 0;
92            endPosition[pieceIndex] = {startX, startY, 0};
93          
94            if (canStopAtPosition(pieceIndex, startX, startY, 0)) {
95                exploreMoves(pieceIndex + 1);
96            }
97          
98            // Option 2: Piece moves in one of its valid directions
99            const int(*directions)[2] = getDirectionVectors(pieces[pieceIndex]);
100            int numDirections = (pieces[pieceIndex][0] == 'q') ? 8 : 4;
101          
102            for (int dirIndex = 0; dirIndex < numDirections; dirIndex++) {
103                resetDistanceForPiece(pieceIndex);
104                distanceMap[pieceIndex][startX][startY] = 0;
105              
106                int nextX = startX + directions[dirIndex][0];
107                int nextY = startY + directions[dirIndex][1];
108                int timeStep = 1;
109              
110                // Move piece in chosen direction until blocked or out of bounds
111                while (isValidPosition(nextX, nextY) && 
112                       canPassThroughPosition(pieceIndex, nextX, nextY, timeStep)) {
113                  
114                    distanceMap[pieceIndex][nextX][nextY] = timeStep;
115                    endPosition[pieceIndex] = {nextX, nextY, timeStep};
116                  
117                    // Try stopping at this position
118                    if (canStopAtPosition(pieceIndex, nextX, nextY, timeStep)) {
119                        exploreMoves(pieceIndex + 1);
120                    }
121                  
122                    // Continue moving in same direction
123                    nextX += directions[dirIndex][0];
124                    nextY += directions[dirIndex][1];
125                    timeStep++;
126                }
127            }
128        };
129      
130        exploreMoves(0);
131        return totalCombinations;
132    }
133};
134
1// Direction vectors for rook movement (horizontal and vertical)
2const rookDirections: [number, number][] = [
3    [1, 0],   // right
4    [-1, 0],  // left
5    [0, 1],   // down
6    [0, -1],  // up
7];
8
9// Direction vectors for bishop movement (diagonal)
10const bishopDirections: [number, number][] = [
11    [1, 1],   // down-right
12    [1, -1],  // down-left
13    [-1, 1],  // up-right
14    [-1, -1], // up-left
15];
16
17// Direction vectors for queen movement (combination of rook and bishop)
18const queenDirections: [number, number][] = [...rookDirections, ...bishopDirections];
19
20/**
21 * Counts the number of valid movement combinations for chess pieces
22 * @param pieces - Array of piece types ('rook', 'bishop', or 'queen')
23 * @param positions - Array of initial positions [row, column] for each piece
24 * @returns Number of valid movement combinations
25 */
26function countCombinations(pieces: string[], positions: number[][]): number {
27    const pieceCount: number = pieces.length;
28    const boardSize: number = 9;
29    let validCombinationsCount: number = 0;
30
31    // 3D array to track when each piece occupies each position
32    // distanceMatrix[pieceIndex][row][column] = time when piece reaches that position
33    const distanceMatrix: number[][][] = Array.from({ length: pieceCount }, () =>
34        Array.from({ length: boardSize }, () => Array(boardSize).fill(-1))
35    );
36
37    // Array to store the ending position and time for each piece
38    // Format: [endRow, endColumn, endTime]
39    const endPositions: [number, number, number][] = Array(pieceCount).fill([0, 0, 0]);
40
41    /**
42     * Resets the distance matrix for a specific piece
43     * @param pieceIndex - Index of the piece to reset
44     */
45    const resetDistanceMatrix = (pieceIndex: number): void => {
46        for (let row = 0; row < boardSize; row++) {
47            for (let col = 0; col < boardSize; col++) {
48                distanceMatrix[pieceIndex][row][col] = -1;
49            }
50        }
51    };
52
53    /**
54     * Checks if a piece can stop at a specific position without collision
55     * @param currentPieceIndex - Index of the current piece
56     * @param row - Target row position
57     * @param col - Target column position
58     * @param time - Time when the piece reaches this position
59     * @returns True if the piece can stop here without collision
60     */
61    const canStopAtPosition = (currentPieceIndex: number, row: number, col: number, time: number): boolean => {
62        // Check against all previously placed pieces
63        for (let pieceIndex = 0; pieceIndex < currentPieceIndex; pieceIndex++) {
64            // If another piece occupies this position at or after this time, collision occurs
65            if (distanceMatrix[pieceIndex][row][col] >= time) {
66                return false;
67            }
68        }
69        return true;
70    };
71
72    /**
73     * Checks if a piece can pass through a position without collision
74     * @param currentPieceIndex - Index of the current piece
75     * @param row - Row position to check
76     * @param col - Column position to check
77     * @param time - Time when the piece passes through
78     * @returns True if the piece can pass through without collision
79     */
80    const canPassThroughPosition = (currentPieceIndex: number, row: number, col: number, time: number): boolean => {
81        // Check against all previously placed pieces
82        for (let pieceIndex = 0; pieceIndex < currentPieceIndex; pieceIndex++) {
83            // Check if another piece is at this position at the same time
84            if (distanceMatrix[pieceIndex][row][col] === time) {
85                return false;
86            }
87            // Check if another piece has stopped at this position before or at this time
88            if (endPositions[pieceIndex][0] === row && 
89                endPositions[pieceIndex][1] === col && 
90                endPositions[pieceIndex][2] <= time) {
91                return false;
92            }
93        }
94        return true;
95    };
96
97    /**
98     * Validates if a position is within the board boundaries
99     * @param row - Row position to validate
100     * @param col - Column position to validate
101     * @returns True if position is valid (1-indexed board)
102     */
103    const isValidPosition = (row: number, col: number): boolean => {
104        return row >= 1 && row < boardSize && col >= 1 && col < boardSize;
105    };
106
107    /**
108     * Gets the movement directions for a specific piece type
109     * @param pieceType - Type of the piece ('rook', 'bishop', or 'queen')
110     * @returns Array of direction vectors for the piece
111     */
112    const getMovementDirections = (pieceType: string): [number, number][] => {
113        switch (pieceType[0]) {
114            case 'r':
115                return rookDirections;
116            case 'b':
117                return bishopDirections;
118            default:
119                return queenDirections;
120        }
121    };
122
123    /**
124     * Depth-first search to explore all valid movement combinations
125     * @param pieceIndex - Current piece index being processed
126     */
127    const exploreCombinations = (pieceIndex: number): void => {
128        // Base case: all pieces have been placed successfully
129        if (pieceIndex >= pieceCount) {
130            validCombinationsCount++;
131            return;
132        }
133
134        const [startRow, startCol] = positions[pieceIndex];
135      
136        // Option 1: Piece doesn't move (stays at starting position)
137        resetDistanceMatrix(pieceIndex);
138        distanceMatrix[pieceIndex][startRow][startCol] = 0;
139        endPositions[pieceIndex] = [startRow, startCol, 0];
140
141        if (canStopAtPosition(pieceIndex, startRow, startCol, 0)) {
142            exploreCombinations(pieceIndex + 1);
143        }
144
145        // Option 2: Piece moves in one of its valid directions
146        const movementDirections = getMovementDirections(pieces[pieceIndex]);
147      
148        for (const [deltaRow, deltaCol] of movementDirections) {
149            resetDistanceMatrix(pieceIndex);
150            distanceMatrix[pieceIndex][startRow][startCol] = 0;
151          
152            let nextRow = startRow + deltaRow;
153            let nextCol = startCol + deltaCol;
154            let currentTime = 1;
155
156            // Continue moving in the chosen direction
157            while (isValidPosition(nextRow, nextCol) && 
158                   canPassThroughPosition(pieceIndex, nextRow, nextCol, currentTime)) {
159              
160                distanceMatrix[pieceIndex][nextRow][nextCol] = currentTime;
161                endPositions[pieceIndex] = [nextRow, nextCol, currentTime];
162              
163                // Check if piece can stop at this position
164                if (canStopAtPosition(pieceIndex, nextRow, nextCol, currentTime)) {
165                    exploreCombinations(pieceIndex + 1);
166                }
167              
168                // Move to next position in the same direction
169                nextRow += deltaRow;
170                nextCol += deltaCol;
171                currentTime++;
172            }
173        }
174    };
175
176    // Start the DFS from the first piece
177    exploreCombinations(0);
178  
179    return validCombinationsCount;
180}
181

Time and Space Complexity

Time Complexity: O((n × M)^n)

The algorithm uses DFS to explore all possible movement combinations for n pieces. For each piece at position i:

  • It first considers the case where the piece doesn't move (stays at initial position)
  • Then it explores all possible directions (up to 8 for queen, 4 for rook/bishop)
  • For each direction, it tries every possible stopping position within the board (up to M-1 positions where M=8 is the maximum distance a piece can travel on an 8×8 board)

At each recursion level i, the algorithm explores up to O(n × M) possibilities:

  • The factor n comes from checking conflicts with all previously placed pieces (in check_stop and check_pass functions)
  • The factor M comes from the maximum number of positions a piece can reach in one direction

Since there are n pieces total and we make decisions for each piece recursively, the total time complexity is O((n × M)^n).

Space Complexity: O(n × M²)

The space is dominated by:

  • dist: A 3D array of size n × M × M (where M=9 for 1-indexed 8×8 board), storing distance information for each piece's movement path - O(n × M²)
  • end: An array of size n storing end positions and times for each piece - O(n)
  • Recursion stack depth: At most n levels deep - O(n)

The dominant term is O(n × M²), which can be simplified to O(n × M) when considering M as the movement range rather than board dimension.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Collision Detection Between Moving Pieces

The Pitfall: A common mistake is only checking if two pieces occupy the same position at their final destinations, missing collisions that occur during movement. For example, if piece A moves from (1,1) to (1,3) and piece B moves from (1,3) to (1,1), they would collide at position (1,2) at time 1, even though their final positions don't overlap.

Solution: Track the exact time each piece passes through each position. Use a 3D array time_to_reach[piece][row][col] to store when each piece reaches each square. When validating movements, check if any two pieces have the same time value for the same position.

2. Mishandling Pieces That Don't Move

The Pitfall: Forgetting to properly handle the case where a piece chooses not to move at all. This can lead to:

  • Not marking the starting position as occupied at time 0
  • Incorrectly allowing other pieces to pass through a stationary piece's position
  • Missing valid combinations where some pieces stay put

Solution: Explicitly handle the stationary case by:

  • Setting time_to_reach[piece][start_row][start_col] = 0
  • Setting final_positions[piece] = (start_row, start_col, 0)
  • Ensuring the validation functions check for conflicts with stationary pieces

3. Off-by-One Errors with 1-Based Indexing

The Pitfall: The problem uses 1-based coordinates (1-8 for chess positions), but Python uses 0-based indexing. Mixing these can cause:

  • Array index out of bounds errors
  • Incorrect boundary checks (e.g., checking row < 8 instead of row < 9 when using 1-based)
  • Pieces moving off the board or not reaching edge squares

Solution:

  • Use a board size of 9 to accommodate 1-based indexing (indices 1-8)
  • Consistently check boundaries as 1 <= position < 9
  • Don't convert between 0-based and 1-based; stick with the input format

4. Incorrect Validation Order in Backtracking

The Pitfall: Checking collisions with pieces that haven't been placed yet, or not properly resetting state when backtracking. This can cause:

  • False positives where valid moves are rejected
  • Contaminated state from previous exploration branches

Solution:

  • Only validate against pieces with indices less than the current piece (already placed pieces)
  • Reset the time_to_reach array for the current piece before exploring each new direction
  • Ensure the validation functions only check range(piece_index) not range(num_pieces)

5. Confusing Pass-Through vs Stop Validation

The Pitfall: Using the same validation logic for both passing through a position and stopping at a position. The rules are different:

  • Passing through: Can't be at the same position at the same time as another piece
  • Stopping: Can't stop where another piece will pass through at any time >= stop time

Solution: Implement two separate validation functions:

  • can_pass_through_position(): Checks for simultaneous occupation and stopped pieces
  • can_stop_at_position(): Checks if any piece passes through at or after the stop time

This separation ensures the correct logic is applied for each scenario and makes the code more maintainable.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27
1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More