Skip to content

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
91
class Solution {
 public:
  int countCombinations(vector<string>& pieces,
                        vector<vector<int>>& positions) {
    const int n = pieces.size();
    unordered_set<unsigned long long> ans;
    vector<vector<pair<int, int>>> combMoves;
    vector<pair<int, int>> board;

    getCombMoves(pieces, 0, {}, combMoves);

    for (const vector<int>& pos : positions)
      board.emplace_back(pos[0], pos[1]);

    for (const vector<pair<int, int>>& combMove : combMoves)
      dfs(board, n, combMove, (1 << n) - 1, ans);

    return ans.size();
  }

 private:
  const unordered_map<string, vector<pair<int, int>>> 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<string>& pieces, int ithPiece,
                    vector<pair<int, int>>&& path,
                    vector<vector<pair<int, int>>>& combMoves) {
    if (ithPiece == pieces.size()) {
      combMoves.push_back(path);
      return;
    }

    for (const pair<int, int>& move : moves.at(pieces[ithPiece])) {
      path.push_back(move);
      getCombMoves(pieces, ithPiece + 1, std::move(path), combMoves);
      path.pop_back();
    }
  }

  void dfs(const vector<pair<int, int>>& board, int n,
           const vector<pair<int, int>>& combMove, int activeMask,
           unordered_set<unsigned long long>& ans) {
    if (activeMask == 0)
      return;
    ans.insert(hash(board));

    for (int nextActiveMask = 1; nextActiveMask < 1 << n; ++nextActiveMask) {
      if ((activeMask & nextActiveMask) != nextActiveMask)
        continue;

      // Make sure to copy the board
      auto nextBoard(board);

      // Move 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;
        }

      // Check no two or more pieces occupy the same square
      if (getUniqueSize(nextBoard) < n)
        continue;

      // Check if all in boundary
      if (all_of(begin(nextBoard), end(nextBoard), [](const auto& piece) {
            const int x = piece.first;
            const int y = piece.second;
            return 1 <= x && x <= 8 && 1 <= y && y <= 8;
          }))
        dfs(nextBoard, n, combMove, nextActiveMask, ans);
    }
  }

  unsigned long long hash(const vector<pair<int, int>>& board) {
    unsigned long long hashed;
    for (const auto& [x, y] : board)
      hashed = (hashed * 64) + (x - 1 << 3) + (y - 1);
    return hashed;
  }

  int getUniqueSize(const vector<pair<int, int>>& board) {
    unordered_set<int> 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<Long> 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<List<int[]>> combMoves = new ArrayList<>();

    getCombMoves(pieces, 0, new ArrayList<>(), combMoves);

    for (List<int[]> combMove : combMoves)
      dfs(positions, n, combMove, (1 << n) - 1, ans);

    return ans.size();
  }

  private Map<String, int[][]> moves = new HashMap<>();

  private void getCombMoves(String[] pieces, int ithPiece, List<int[]> path,
                            List<List<int[]>> 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<int[]> combMove, int activeMask, Set<Long> ans) {
    if (activeMask == 0)
      return;
    ans.add(hash(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 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];
        }

      // Check no two or more pieces occupy the same square
      if (getUniqueSize(nextBoard) < n)
        continue;

      // Check if all in 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 hash(int[][] board) {
    long hashed = 0;
    for (int[] pos : board)
      hashed = (hashed * 64) + (pos[0] - 1 << 3) + (pos[1] - 1);
    return hashed;
  }

  private int getUniqueSize(int[][] board) {
    Set<Integer> 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 hash(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(hash(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 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]

        # Check no two or more pieces occupy the same square
        if len(set(hash(nextBoard))) < n:
          continue

        # Check if all in 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)