<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:
        # n pieces: rooks/queens/bishops

        # pieces[i] is "rook" "queen" "bishop"
        # positions are 1-based, 1..8

        # n pieces

        # make a move for all pieces on the board simultaneously
        #    move combo is the set of n moves
        # every second each piece moves one square toward its destination
        # move combination is invalid if at any time 2+ pieces occupy the same square

        # return number of valid move combinations

        # dest can be origin
        # can move past each other, just can't be in the same posn at any second, e.g. QR -> RQ move thorugh is fine, but Q R -> x invalid where x is R and Q
        
        # super brute force:
        #    4 pieces max, all queens, 7*4 max for < 30 possible destinations
        #       all combos is 30**4 = 81e4
        # and then we can check if any pair will collide during the move

        # step 1: iterate over all possible destinations for each piece, such as (dir, dist) for each piece
        # step 2: filter for validity

        N = len(pieces)

        rook_dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        bishop_dirs = [(1, 1), (-1, 1), (1, -1), (-1, -1)]
        queen_dirs = rook_dirs + bishop_dirs
        dirs = {'bishop': bishop_dirs, 'rook': rook_dirs, 'queen': queen_dirs}

        def iterMoves(i: int) -> Iterator[tuple[tuple[int], int]]:
            ds = dirs[pieces[i]]

            r, c = positions[i]
            for dr, dc in ds:
                for dist in range(1, 8):
                    rr, cc = r+dr*dist, c+dc*dist
                    if not (1 <= rr <= 8 and 1 <= cc <= 8): break
                    yield (dr, dc), dist

            yield (dr, dc), 0 # the unique way to move 0

        def valid(combo) -> bool:
            """@param combo: for each piece in pieces a direction and distance"""

            # marks the locations of each piece at each time, returns False if there's a conflict
            T = max(t for _, t in combo) # last time a piece moves

            # for each piece compute its position for every time in 1..T (we know there are no conflicts at time 0)
            #    > if has the same position as any other piece at that time then return False
            #    > else append and move on
            # if we get to the end with no conflicts at any time then return True
            locs = [[] for _ in range(T+1)]
            for i, ((dr, dc), dist) in enumerate(combo):
                r, c = positions[i]
                for t in range(1, dist+1):
                    rr, cc = r+dr*t, c+dc*t
                    if (rr, cc) in locs[t]: return False # found conflict
                    locs[t].append((rr, cc))

                # piece no longer moves, but we still need to check for collisions
                # this loop uses the last (rr, cc)
                rr, cc = r+dr*dist, c+dc*dist # FIXED: if piece moves zero then rr, cc wasn't defined
                for t in range(dist+1, T+1):
                    if (rr, cc) in locs[t]: return False
                    locs[t].append((rr, cc))

            return True # no conflicts at any time

        # ways = 0
        # for combo in product(*[iterMoves(i) for i in range(N)]):
        #     ways += valid(combo)

        return sum(valid(combo) for combo in product(*(iterMoves(i) for i in range(N))))
16600