<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, pieces: List[str], positions: List[List[int]]) -> int:
        def generate_rook_moves(pos):
            moves = set()
            x, y = pos

            for i in range(1, 9):
                moves.add((x, i))
                moves.add((i, y))

            return list(moves)

        def generate_bishop_moves(pos):
            moves = set()
            x, y = pos

            for i in range(9):
                if x + i <= 8 and y + i <= 8:
                    moves.add((x + i, y + i))
                if x + i <= 8 and y - i > 0:
                    moves.add((x + i, y - i))
                if x - i > 0 and y - i > 0:
                    moves.add((x - i, y - i))
                if x - i > 0 and y + i <= 8:
                    moves.add((x - i, y + i))

            return list(moves)

        def generate_queen_moves(pos):
            return list(set(generate_bishop_moves(pos) + generate_rook_moves(pos)))

        def check_can_do(destinations):
            is_piece_at_destination = [False] * len(pieces)
            cur_poses = [list(pos) for pos in positions]

            while False in is_piece_at_destination:
                check_set = set()

                for piece in range(len(pieces)):
                    x, y = cur_poses[piece]
                    dx, dy = destinations[piece]
                    
                    if x == dx and y == dy:
                        is_piece_at_destination[piece] = True
                    else:
                        x += 1 if dx > x else 0 if x == dx else -1
                        y += 1 if dy > y else 0 if y == dy else -1
                        cur_poses[piece] = [x, y]

                    check_set.add((x, y))

                if len(check_set) < len(pieces):
                    return 0
            return 1

        def backtrack(cur_ind, destinations):
            if cur_ind == len(pieces):
                return check_can_do(destinations)
            res = 0
            for i in range(len(destinations_for_each_piece[cur_ind])):
                res += backtrack(cur_ind + 1, destinations + [destinations_for_each_piece[cur_ind][i]])
            return res

        destinations_for_each_piece = []

        for piece in range(len(pieces)):
            if pieces[piece][0] == "q":
                destinations_for_each_piece.append(generate_queen_moves(positions[piece]))
            elif pieces[piece][0] == "r":
                destinations_for_each_piece.append(generate_rook_moves(positions[piece]))
            else:
                destinations_for_each_piece.append(generate_bishop_moves(positions[piece]))

        return backtrack(0, [])
    '''
    def getRookNumComb(self):
        return 14

    def getBishopNumComb(self, r, c):
        topLeft = min(r, c) - 1
        bottomRight = 8 - max(r, c)
        topRight = min(r, 9-c) -1
        bottomLeft = 8 - max(r, 9-c) 
        return (topLeft + topRight + bottomRight + bottomLeft)
        
    def getQueenNumComb(self, r, c):
        return self.getBishopNumComb(r, c) + self.getRookNumComb()
        
    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:
        num_comb = 1

        for i, piece in enumerate(pieces):
            if piece == "rook":
                num_comb *= self.getRookNumComb() + 1
            elif piece == "queen":
                num_comb *= self.getQueenNumComb(positions[i][0], positions[i][1]) + 1
            elif piece == "bishop":
                num_comb *= self.getBishopNumComb(positions[i][0], positions[i][1]) + 1
        
        len_pieces = len(pieces)
        return num_comb - (len_pieces if len_pieces > 1 else 0)
    '''
16900