<p>There is an <code>8 x 8</code> chessboard containing <code>n</code> pieces (rooks, queens, or bishops). You are given a string array <code>pieces</code> of length <code>n</code>, where <code>pieces[i]</code> describes the type (rook, queen, or bishop) of the <code>i<sup>th</sup></code> piece. In addition, you are given a 2D integer array <code>positions</code> also of length <code>n</code>, where <code>positions[i] = [r<sub>i</sub>, c<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> piece is currently at the <strong>1-based</strong> coordinate <code>(r<sub>i</sub>, c<sub>i</sub>)</code> on the chessboard.</p>

<p>When making a <strong>move</strong> for a piece, you choose a <strong>destination</strong> square that the piece will travel toward and stop on.</p>

<ul>
	<li>A rook can only travel <strong>horizontally or vertically</strong> from <code>(r, c)</code> to the direction of <code>(r+1, c)</code>, <code>(r-1, c)</code>, <code>(r, c+1)</code>, or <code>(r, c-1)</code>.</li>
	<li>A queen can only travel <strong>horizontally, vertically, or diagonally</strong> from <code>(r, c)</code> to the direction of <code>(r+1, c)</code>, <code>(r-1, c)</code>, <code>(r, c+1)</code>, <code>(r, c-1)</code>, <code>(r+1, c+1)</code>, <code>(r+1, c-1)</code>, <code>(r-1, c+1)</code>, <code>(r-1, c-1)</code>.</li>
	<li>A bishop can only travel <strong>diagonally</strong> from <code>(r, c)</code> to the direction of <code>(r+1, c+1)</code>, <code>(r+1, c-1)</code>, <code>(r-1, c+1)</code>, <code>(r-1, c-1)</code>.</li>
</ul>

<p>You must make a <strong>move</strong> for every piece on the board simultaneously. A <strong>move combination</strong> consists of all the <strong>moves</strong> performed on all the given pieces. Every second, each piece will instantaneously travel <strong>one square</strong> towards their destination if they are not already at it. All pieces start traveling at the <code>0<sup>th</sup></code> second. A move combination is <strong>invalid</strong> if, at a given time, <strong>two or more</strong> pieces occupy the same square.</p>

<p>Return <em>the number of <strong>valid</strong> move combinations</em>​​​​​.</p>

<p><strong>Notes:</strong></p>

<ul>
	<li><strong>No two pieces</strong> will start in the<strong> same</strong> square.</li>
	<li>You may choose the square a piece is already on as its <strong>destination</strong>.</li>
	<li>If two pieces are <strong>directly adjacent</strong> to each other, it is valid for them to <strong>move past each other</strong> and swap positions in one second.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/23/a1.png" style="width: 215px; height: 215px;" />
<pre>
<strong>Input:</strong> pieces = [&quot;rook&quot;], positions = [[1,1]]
<strong>Output:</strong> 15
<strong>Explanation:</strong> The image above shows the possible squares the piece can move to.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/23/a2.png" style="width: 215px; height: 215px;" />
<pre>
<strong>Input:</strong> pieces = [&quot;queen&quot;], positions = [[1,1]]
<strong>Output:</strong> 22
<strong>Explanation:</strong> The image above shows the possible squares the piece can move to.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/23/a3.png" style="width: 214px; height: 215px;" />
<pre>
<strong>Input:</strong> pieces = [&quot;bishop&quot;], positions = [[4,3]]
<strong>Output:</strong> 12
<strong>Explanation:</strong> The image above shows the possible squares the piece can move to.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == pieces.length </code></li>
	<li><code>n == positions.length</code></li>
	<li><code>1 &lt;= n &lt;= 4</code></li>
	<li><code>pieces</code> only contains the strings <code>&quot;rook&quot;</code>, <code>&quot;queen&quot;</code>, and <code>&quot;bishop&quot;</code>.</li>
	<li>There will be at most one queen on the chessboard.</li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 8</code></li>
	<li>Each <code>positions[i]</code> is distinct.</li>
</ul>

class Solution:
    def countCombinations(self, piece_types, piece_positions):
        # Directions for movement: (None for no movement, Rook, Bishop)
        movement_directions = (
            (),
            ((-1, 0), (1, 0), (0, -1), (0, 1)),  # Rook can move vertically or horizontally
            ((-1, -1), (1, -1), (-1, 1), (1, 1))  # Bishop can move diagonally
        )
        
        # Mapping of piece types to their identifiers
        # Rook -> 1, Bishop -> 2, Queen -> 3
        piece_mapping = {"rook": 1, "bishop": 2, "queen": 3}
        
        # Get the total number of pieces to be placed on the board
        num_pieces = len(piece_types)
        
        # Maximum bitmask value for an 8-bit representation (0b11111111)
        max_mask = (1 << 8) - 1  
        
        # Initialize the attack_mask for an 8x8 board
        # Each cell starts with the maximum mask, indicating that all positions are available
        attack_mask = [[max_mask] * 9 for _ in range(9)]
        
        # Depth-First Search (DFS) function to count valid combinations
        def dfs(current_piece_index):
            # Base case: If all pieces are placed, return 1 valid combination found
            if current_piece_index == num_pieces:
                return 1
            
            # Get the current piece type and its starting position
            piece_type, (start_x, start_y) = piece_types[current_piece_index], piece_positions[current_piece_index]
            combination_count = 0  # Initialize the count of valid combinations
            
            # Allow the piece to stay at its original position
            if attack_mask[start_x][start_y] == max_mask:  
                # Temporarily mark the original position as occupied
                original_mask = attack_mask[start_x][start_y]
                attack_mask[start_x][start_y] = 0  # Set the position to occupied (no available moves)
                
                # Recursively count combinations for the next piece
                combination_count += dfs(current_piece_index + 1)
                
                # Restore the position for future calculations
                attack_mask[start_x][start_y] = original_mask
            
            # Check possible moves based on the piece type
            # The piece can move in the directions specified for its type (rook or bishop)
            for dx, dy in movement_directions[piece_mapping[piece_type] & 1] + movement_directions[piece_mapping[piece_type] & 2]:
                current_x, current_y, b = start_x + dx, start_y + dy, 1  # Start moving in the specified direction
                
                # Continue moving in the direction until hitting the edge of the board or an occupied square
                while 0 < current_x < 9 and 0 < current_y < 9 and (attack_mask[current_x][current_y] >> b & 1):
                    # Mark the square as attacked (occupied) by toggling the bit
                    attack_mask[current_x][current_y] ^= (1 << b)  
                    
                    # Check if the piece can continue moving further
                    if (attack_mask[current_x][current_y] >> (b + 1)) == (max_mask >> (b + 1)):
                        temporary_mask = attack_mask[current_x][current_y]  # Save the current state
                        attack_mask[current_x][current_y] &= (1 << b) - 1  # Restore attacked squares to available
                        
                        # Recursively count combinations for the next piece
                        combination_count += dfs(current_piece_index + 1)
                        
                        # Restore the state of the square after counting
                        attack_mask[current_x][current_y] = temporary_mask
                    
                    # Move to the next square in the same direction
                    current_x, current_y, b = current_x + dx, current_y + dy, b + 1
            
                # Restore the attacked squares after finishing the exploration in one direction
                while b > 1:
                    # Move back to restore the state of the squares
                    attack_mask[(current_x := current_x - dx)][(current_y := current_y - dy)] |= (1 << (b := b - 1))
            
            return combination_count  # Return the total count of combinations found in this path
        
        # Start DFS from the first piece and return the total combinations found
        return dfs(0)
16700