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
class Solution {
 public:
  int countCombinations(vector<string>& pieces,
                        vector<vector<int>>& positions) {
    const int n = pieces.size();
    unordered_set<long long> hashedBoards;
    // Stores all possible move combinations for `pieces`. Each element is a
    // vector of moves, one for each piece in the input order. e.g., if pieces =
    // ["rook", "bishop"], one element might be [[1,0], [1,1]], representing a
    // rook moving right and a bishop moving diagonally up-right.
    vector<vector<pair<int, int>>> pieceMovesList;

    getPieceMovesList(pieces, 0, {}, pieceMovesList);

    for (const vector<pair<int, int>>& pieceMoves : pieceMovesList)
      dfs(positions, n, pieceMoves, (1 << n) - 1, hashedBoards);

    return hashedBoards.size();
  }

 private:
  const unordered_map<string, vector<pair<int, int>>> kPieceToMoves{
      {"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}}}};

  // Generates all possible combinations of moves.
  void getPieceMovesList(const vector<string>& pieces, int i,
                         vector<pair<int, int>>&& path,
                         vector<vector<pair<int, int>>>& pieceMovesList) {
    if (i == pieces.size()) {
      pieceMovesList.push_back(path);
      return;
    }
    for (const pair<int, int>& move : kPieceToMoves.at(pieces[i])) {
      path.push_back(move);
      getPieceMovesList(pieces, i + 1, std::move(path), pieceMovesList);
      path.pop_back();
    }
  }

  // Performs a depth-first search to explore all possible board states.
  void dfs(const vector<vector<int>>& board, int n,
           const vector<pair<int, int>>& pieceMoves, int activeMask,
           unordered_set<long long>& hashedBoards) {
    if (activeMask == 0)
      return;
    hashedBoards.insert(getHash(board));
    for (int nextActiveMask = 1; nextActiveMask < 1 << n; ++nextActiveMask) {
      if ((activeMask & nextActiveMask) != nextActiveMask)
        continue;

      // Copy the board.
      vector<vector<int>> nextBoard = board;

      // Move the pieces that are active in this turn.
      for (int i = 0; i < n; ++i)
        if (nextActiveMask >> i & 1) {
          nextBoard[i][0] += pieceMoves[i].first;
          nextBoard[i][1] += pieceMoves[i].second;
        }

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

      // Every piece needs to be in the boundary.
      if (ranges::all_of(nextBoard, [](const vector<int>& pos) {
        return 1 <= pos[0] && pos[0] <= 8 && 1 <= pos[1] && pos[1] <= 8;
      }))
        dfs(nextBoard, n, pieceMoves, nextActiveMask, hashedBoards);
    }
  }

  long long getHash(const vector<vector<int>>& board) {
    long long hash = 0;
    for (const vector<int>& pos : board)
      hash = (hash * 64) + ((pos[0] - 1) << 3) + (pos[1] - 1);
    return hash;
  }

  int getUniqueSize(const vector<vector<int>>& board) {
    unordered_set<int> unique;
    for (const vector<int>& pos : board)
      unique.insert(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
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(String[] pieces, int[][] positions) {
    final int n = pieces.length;
    Set<Long> hashedBoards = new HashSet<>();
    // Stores all possible move combinations for `pieces`. Each element is a
    // vector of moves, one for each piece in the input order. e.g., if pieces =
    // ["rook", "bishop"], one element might be [[1,0], [1,1]], representing a
    // rook moving right and a bishop moving diagonally up-right.
    List<List<int[]>> combMoves = new ArrayList<>();

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

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

    return hashedBoards.size();
  }

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

  static {
    kMoves.put("rook", new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}});
    kMoves.put("bishop", new int[][] {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}});
    kMoves.put("queen",
               new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}});
  }

  // Generates all possible combinations of moves for the given pieces.
  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 : kMoves.get(pieces[ithPiece])) {
      path.add(move);
      getCombMoves(pieces, ithPiece + 1, path, combMoves);
      path.remove(path.size() - 1);
    }
  }

  // Performs a depth-first search to explore all possible board states.
  private void dfs(int[][] board, int n, List<int[]> combMove, int activeMask,
                   Set<Long> hashedBoards) {
    if (activeMask == 0)
      return;
    hashedBoards.add(getHash(board));

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

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

      // Every piece 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, hashedBoards);
    }
  }

  // Generates a unique hash for the given board state.
  private long getHash(int[][] board) {
    long hash = 0;
    for (int[] pos : board)
      hash = (hash * 64) + (pos[0] - 1 << 3) + (pos[1] - 1);
    return hash;
  }

  // Counts the number of unique positions on the board occupied by the pieces.
  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
42
43
44
45
46
47
48
49
50
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)]}
    hashedBoards = set()

    def getHash(board: list[list[int]]) -> Tuple:
      return tuple([tuple(pos) for pos in board])

    def dfs(
        board: list[list[int]],
        pieceMoves: list[tuple[int, int]],
        activeMask: int,
    ) -> None:
      """Performs a depth-first search to explore all possible board states."""
      if activeMask == 0:
        return
      hashedBoards.add(getHash(board))

      for nextActiveMask in range(1, 1 << n):
        if activeMask & nextActiveMask != nextActiveMask:
          continue

        # 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] += pieceMoves[i][0]
            nextBoard[i][1] += pieceMoves[i][1]

        # No two or more pieces occupy the same square.
        if len(set(getHash(nextBoard))) < n:
          continue

        # Every piece needs to be in the boundary.
        if all(1 <= x <= 8 and 1 <= y <= 8 for x, y in nextBoard):
          dfs(nextBoard, pieceMoves, nextActiveMask)

    for pieceMoves in itertools.product(*(moves[piece] for piece in pieces)):
      dfs(positions, pieceMoves, (1 << n) - 1)

    return len(hashedBoards)