# 2056. Number of Valid Move Combinations On Chessboard¶

• Time: $O(29^n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 class Solution { public: int countCombinations(vector& pieces, vector>& positions) { const int n = pieces.size(); unordered_set ans; vector>> combMoves; vector> board; getCombMoves(pieces, 0, {}, combMoves); for (const vector& pos : positions) board.emplace_back(pos[0], pos[1]); for (const vector>& combMove : combMoves) dfs(board, n, combMove, (1 << n) - 1, ans); return ans.size(); } private: const unordered_map>> moves{ {"rook", {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}}, {"bishop", {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}}, {"queen", {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}}}; void getCombMoves(const vector& pieces, int ithPiece, vector>&& path, vector>>& combMoves) { if (ithPiece == pieces.size()) { combMoves.push_back(path); return; } for (const pair& move : moves.at(pieces[ithPiece])) { path.push_back(move); getCombMoves(pieces, ithPiece + 1, std::move(path), combMoves); path.pop_back(); } } void dfs(const vector>& board, int n, const vector>& combMove, int activeMask, unordered_set& ans) { if (activeMask == 0) return; ans.insert(getHash(board)); for (int nextActiveMask = 1; nextActiveMask < 1 << n; ++nextActiveMask) { if ((activeMask & nextActiveMask) != nextActiveMask) continue; // Make sure to copy the board. auto nextBoard(board); // Move the pieces that are active in this turn. for (int i = 0; i < n; ++i) if ((nextActiveMask >> i) & 1) { nextBoard[i].first += combMove[i].first; nextBoard[i].second += combMove[i].second; } // No two or more pieces occupy the same square. if (getUniqueSize(nextBoard) < n) continue; // Everything needs to be in the boundary. if (ranges::all_of(nextBoard, [](const auto& piece) { const auto& [x, y] = piece; return 1 <= x && x <= 8 && 1 <= y && y <= 8; })) dfs(nextBoard, n, combMove, nextActiveMask, ans); } } unsigned long long getHash(const vector>& board) { unsigned long long hash; for (const auto& [x, y] : board) hash = (hash * 64) + (x - 1 << 3) + (y - 1); return hash; } int getUniqueSize(const vector>& board) { unordered_set unique; for (const auto& [x, y] : board) unique.insert(x * 8 + y); return unique.size(); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 class Solution { public int countCombinations(String[] pieces, int[][] positions) { final int n = pieces.length; Set ans = new HashSet<>(); moves.put("rook", new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}); moves.put("bishop", new int[][] {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}); moves.put("queen", new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}); List> combMoves = new ArrayList<>(); getCombMoves(pieces, 0, new ArrayList<>(), combMoves); for (List combMove : combMoves) dfs(positions, n, combMove, (1 << n) - 1, ans); return ans.size(); } private Map moves = new HashMap<>(); private void getCombMoves(String[] pieces, int ithPiece, List path, List> combMoves) { if (ithPiece == pieces.length) { combMoves.add(new ArrayList<>(path)); return; } for (int[] move : moves.get(pieces[ithPiece])) { path.add(move); getCombMoves(pieces, ithPiece + 1, path, combMoves); path.remove(path.size() - 1); } } private void dfs(int[][] board, int n, List combMove, int activeMask, Set ans) { if (activeMask == 0) return; ans.add(getHash(board)); for (int nextActiveMask = 1; nextActiveMask < 1 << n; ++nextActiveMask) { if ((activeMask & nextActiveMask) != nextActiveMask) continue; // Make sure to copy the board. int[][] nextBoard = new int[n][]; for (int i = 0; i < n; ++i) nextBoard[i] = board[i].clone(); // Move the pieces that are active in this turn. for (int i = 0; i < n; ++i) if (((nextActiveMask >> i) & 1) == 1) { nextBoard[i][0] += combMove.get(i)[0]; nextBoard[i][1] += combMove.get(i)[1]; } // No two or more pieces occupy the same square. if (getUniqueSize(nextBoard) < n) continue; // Everything needs to be in the boundary. if (Arrays.stream(nextBoard).allMatch(p -> 1 <= p[0] && p[0] <= 8 && 1 <= p[1] && p[1] <= 8)) dfs(nextBoard, n, combMove, nextActiveMask, ans); } } private long getHash(int[][] board) { long hash = 0; for (int[] pos : board) hash = (hash * 64) + (pos[0] - 1 << 3) + (pos[1] - 1); return hash; } private int getUniqueSize(int[][] board) { Set unique = new HashSet<>(); for (int[] pos : board) unique.add(pos[0] * 8 + pos[1]); return unique.size(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution: def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int: n = len(pieces) moves = {"rook": [(1, 0), (-1, 0), (0, 1), (0, -1)], "bishop": [(1, 1), (1, -1), (-1, 1), (-1, -1)], "queen": [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]} ans = set() def getHash(board: List[List[int]]) -> Tuple: return tuple([tuple(pos) for pos in board]) def dfs(board: List[List[int]], combMove: List[Tuple[int, int]], activeMask: int) -> None: if activeMask == 0: return ans.add(getHash(board)) for nextActiveMask in range(1, 1 << n): if activeMask & nextActiveMask != nextActiveMask: continue # Make sure to copy the board. nextBoard = [pos.copy() for pos in board] # Move the pieces that are active in this turn. for i in range(n): if (nextActiveMask >> i) & 1: nextBoard[i][0] += combMove[i][0] nextBoard[i][1] += combMove[i][1] # No two or more pieces occupy the same square. if len(set(getHash(nextBoard))) < n: continue # Everything needs to be in the boundary. if all(1 <= x <= 8 and 1 <= y <= 8 for x, y in nextBoard): dfs(nextBoard, combMove, nextActiveMask) for combMove in product(*(moves[piece] for piece in pieces)): dfs(positions, combMove, (1 << n) - 1) return len(ans)