<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:
    BOARD_SIZE = 8
    
    def diag(self, r, c):
        # Return all diagonal indices except (r, c)
        # Diagonal indices has the same r - c
        inv = r - c
        result = []
        for ri in range(self.BOARD_SIZE):
            ci = ri - inv
            if 0 <= ci < self.BOARD_SIZE and ri != r:
                result.append((ri, ci))

        return result
    
    def reverseDiag(self, r, c):
        # Return all reverse diagonal indices except (r, c)
        # Reverse diagonal indices has the same r + c
        inv = r + c
        result = []
        for ri in range(self.BOARD_SIZE):
            ci = inv - ri
            if 0 <= ci < self.BOARD_SIZE and ri != r:
                result.append((ri, ci))

        return result
    
    def generatePossiblePositions(self, piece, start):
        # Generate list of possible positions for every figure
        rs, cs = start[0] - 1, start[1] - 1

        # Start position
        result = [(rs, cs)]

        # Straight
        if piece == "rook" or piece == "queen":
            result.extend([(r, cs) for r in range(self.BOARD_SIZE) if r != rs])
            result.extend([(rs, c) for c in range(self.BOARD_SIZE) if c != cs])

        # Diagonal
        if piece == "bishop" or piece == "queen":
            result.extend(self.diag(rs, cs))
            result.extend(self.reverseDiag(rs, cs))

        return result
    
    def collide(self, start1, end1, start2, end2):
        # Check if two figures will collide
        # Collision occures if: 
        #  - two figures have the same end points
        #  - one figure stands on the way of second one
        #
        # For this purpose let's model each step of two pieces 
        # and compare their positions at every time step.
        
        def steps(start, end):
            # Total steps that should be done
            return abs(end - start)

        def step(start, end):
            # Step direction -1, 0, 1
            if steps(start, end) == 0:
                return 0
            return (end - start) / steps(start, end)

        (rstart1, cstart1), (rend1, cend1) = start1, end1
        (rstart2, cstart2), (rend2, cend2) = start2, end2

        # Find step direction for each piece
        rstep1, cstep1 = step(rstart1, rend1), step(cstart1, cend1)
        rstep2, cstep2 = step(rstart2, rend2), step(cstart2, cend2)

        # Find maximum number of steps for each piece
        max_step1 = max(steps(rstart1, rend1), steps(cstart1, cend1))
        max_step2 = max(steps(rstart2, rend2), steps(cstart2, cend2))

        # Move pieces step by step and compare their positions
        for step_i in range(max(max_step1, max_step2) + 1):
            step_i1 = min(step_i, max_step1)
            r1 = rstart1 + step_i1 * rstep1
            c1 = cstart1 + step_i1 * cstep1

            step_i2 = min(step_i, max_step2)
            r2 = rstart2 + step_i2 * rstep2
            c2 = cstart2 + step_i2 * cstep2

            # If positions are the same then collision occures
            if r1 == r2 and c1 == c2:
                return True

        return False
    
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        if len(pieces) == 0:
            return 0

        n = len(pieces)
        
        # Make zero-indexed
        start_positions = [[r - 1, c - 1] for r, c in positions]
        
        # All possible positions
        possible_positions = [
            self.generatePossiblePositions(piece, start) 
            for piece, start in zip(pieces, positions)
        ]
        
        # Let's use DFS with backtracking
        # For that we will keep set of already occupied coordinates
        # and current positions of pieces
        occupied = set()
        current_positions = [None] * n  # None means that we didn't placed the piece
        
        def collision(start, end):
            # Helper to check if moving from start to end position will collide with someone
            for start2, end2 in zip(start_positions, current_positions):
                if end2 is not None and self.collide(start, end, start2, end2):
                    return True
            return False

        def dfs(piece_i=0):
            # All pieces are placed
            if piece_i == n:
                return 1

            result = 0
            for position in possible_positions[piece_i]:
                # If position already occupied of collides with other pieces then skip it
                if position in occupied or collision(start_positions[piece_i], position):
                    continue
                
                # Occupy the position
                occupied.add(position)
                current_positions[piece_i] = position
                
                # Run DFS for next piece
                result += dfs(piece_i + 1)
                
                # Release the position
                occupied.remove(position)
                current_positions[piece_i] = None
                
            return result

        return dfs()
17100