2056. Number of Valid Move Combinations On Chessboard LeetCode Solution
In this guide, you will get 2056. Number of Valid Move Combinations On Chessboard LeetCode Solution with the best time and space complexity. The solution to Number of Valid Move Combinations On Chessboard problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Valid Move Combinations On Chessboard
There is an 8 x 8 chessboard containing n pieces (rooks, queens, or bishops). You are given a string array pieces of length n, where pieces[i] describes the type (rook, queen, or bishop) of the ith piece. In addition, you are given a 2D integer array positions also of length n, where positions[i] = [ri, ci] indicates that the ith piece is currently at the 1-based coordinate (ri, ci) on the chessboard.
When making a move for a piece, you choose a destination square that the piece will travel toward and stop on.
A rook can only travel horizontally or vertically from (r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), or (r, c-1).
A queen can only travel horizontally, vertically, or diagonally from (r, c) to the direction of (r+1, c), (r-1, c), (r, c+1), (r, c-1), (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).
A bishop can only travel diagonally from (r, c) to the direction of (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1).
You must make a move for every piece on the board simultaneously. A move combination consists of all the moves performed on all the given pieces. Every second, each piece will instantaneously travel one square towards their destination if they are not already at it. All pieces start traveling at the 0th second. A move combination is invalid if, at a given time, two or more pieces occupy the same square.
Return the number of valid move combinations.
Notes:
No two pieces will start in the same square.
You may choose the square a piece is already on as its destination.
If two pieces are directly adjacent to each other, it is valid for them to move past each other and swap positions in one second.
Input: pieces = [“rook”], positions = [[1,1]]
Output: 15
Explanation: The image above shows the possible squares the piece can move to.
Example 2:
Input: pieces = [“queen”], positions = [[1,1]]
Output: 22
Explanation: The image above shows the possible squares the piece can move to.
Example 3:
Input: pieces = [“bishop”], positions = [[4,3]]
Output: 12
Explanation: The image above shows the possible squares the piece can move to.
Constraints:
n == pieces.length
n == positions.length
1 <= n <= 4
pieces only contains the strings "rook", "queen", and "bishop".
There will be at most one queen on the chessboard.
1 <= ri, ci <= 8
Each positions[i] is distinct.
Complexity Analysis
Time Complexity: O(29^n)
Space Complexity: O(1)
2056. Number of Valid Move Combinations On Chessboard LeetCode Solution in C++
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();
}
}; /* code provided by PROGIEZ */
2056. Number of Valid Move Combinations On Chessboard LeetCode Solution in Java
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();
}
} // code provided by PROGIEZ
2056. Number of Valid Move Combinations On Chessboard LeetCode Solution in Python
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) # code by PROGIEZ
