Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Number of Valid Move Combinations On Chessboard solution and explanation

HardArrayBacktrackingSimulationString9 min read48.7% acceptanceUpdated 9 Apr 2026
Asked atPayPalGoogle
Practise Number of Valid Move Combinations On Chessboard
48:12
【每日一题】LeetCode 2056. Number of Valid Move Combinations On ChessboardHuifeng Guan · 48:12 · 1K viewsWatch on YouTube
2 more videos on this problem
  1. 【每日一题】LeetCode 2056. Number of Valid Move Combinations On ChessboardHuifeng Guan · 48:12 · 1K views
  2. 2056. Number of Valid Move Combinations On Chessboard (Leetcode Hard)Programming Live with Larry · 34:25 · 1K views
  3. LeetCode 2056: Number of Valid Move Combinations On ChessboardAlitaCode · 30:54 · 36 views

The problem

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.

Example 1:

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.

Approach overview

Problem Overview: You are given several chess pieces (rook, bishop, or queen) placed on an 8×8 board. Each piece may move in a valid direction and stop at any square along that path. The task is to count all combinations of moves such that pieces move simultaneously without ever occupying the same square at the same time.

Approach 1: Backtracking + Simulation (Exponential Time, O(k * 8^k) space)

This approach enumerates every possible movement choice for each piece using backtracking. For each piece, you pick a direction allowed by its type and a distance to travel. After assigning moves to all pieces, simulate the movement step-by-step to ensure no two pieces collide at any time step. The key insight is that collisions can occur mid‑movement, not just at final positions, so the simulation checks positions at every step. Backtracking works well because the number of pieces is small, and pruning invalid paths early significantly reduces the search space.

Approach 2: Dynamic Programming with State Simulation (O(states * moves), O(states) space)

This version models the board evolution across time. Each state represents the positions of all pieces at a specific step. Using array representations of coordinates, transitions simulate one movement step for each piece based on its chosen direction until it reaches its stopping square. Memoization stores already explored configurations to avoid recomputation. The technique behaves like a layered simulation where each time layer expands possible states while rejecting collisions. It blends ideas from simulation and dynamic programming to reduce repeated state exploration.

Recommended for interviews: The backtracking approach is what most interviewers expect. It directly models the problem: choose directions, choose distances, and simulate movement to validate collisions. Brute enumeration shows understanding of chess movement rules, while pruning and step-by-step collision checks demonstrate strong problem‑solving skills. The dynamic programming variant is useful when discussing optimization or avoiding repeated simulations.

Approach 1: Backtracking Approach

This method involves generating all possible move combinations using backtracking. Each piece moves independently in all possible directions according to its type until it reaches its destination or collides with another piece. For each valid configuration where no two pieces land on the same square at the same time, count the valid move-set.

def get_directions(piece):
    if piece == "rook":
        return [(0, 1), (0, -1), (1, 0), (-1, 0)]
    elif piece == "queen":
        return [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    else:
        return [(1, 1), (1, -1), (-1, 1), (-1, -1)]


def backtrack(pieces, positions, index):
    if index == len(pieces):
        return 1

    r, c = positions[index]
    directions = get_directions(pieces[index])
    count = 0

    for dr, dc in directions:
        for steps in range(1, 9):
            nr, nc = r + steps * dr, c + steps * dc
            if 1 <= nr <= 8 and 1 <= nc <= 8:
                positions[index] = (nr, nc)
                count += backtrack(pieces, positions, index + 1)
            else:
                break

    positions[index] = (r, c)
    count += backtrack(pieces, positions, index + 1)

    return count


if __name__ == "__main__":
    pieces = ["bishop"]
    positions = [(4, 3)]
    result = backtrack(pieces, positions, 0)
    print("Valid move combinations:", result)
import java.util.*;

public class ChessMoveCombinations {
    static final List<int[]> bishopDirs = Arrays.asList(
            new int[]{1, 1}, new int[]{1, -1}, new int[]{-1, 1}, new int[]{-1, -1});
    static final List<int[]> rookDirs = Arrays.asList(
            new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0});
    static final List<int[]> queenDirs = Arrays.asList(
            new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0},
            new int[]{1, 1}, new int[]{1, -1}, new int[]{-1, 1}, new int[]{-1, -1});

    public static int countValidMoves(List<String> pieces, List<int[]> positions) {
        return backtrack(pieces, positions, 0);
    }

    private static int backtrack(List<String> pieces, List<int[]> positions, int index) {
        if (index == positions.size()) {
            return 1;
        }

        int r = positions.get(index)[0];
        int c = positions.get(index)[1];
        List<int[]> directions = getDirections(pieces.get(index));
        int count = 0;

        for (int[] dir : directions) {
            for (int step = 1; step <= 8; step++) {
                int nr = r + step * dir[0];
                int nc = c + step * dir[1];

                if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                    positions.set(index, new int[]{nr, nc});
                    count += backtrack(pieces, positions, index + 1);
                } else {
                    break;
                }
            }
        }

        positions.set(index, new int[]{r, c});
        count += backtrack(pieces, positions, index + 1);

        return count;
    }

    private static List<int[]> getDirections(String piece) {
        if (piece.equals("rook")) return rookDirs;
        if (piece.equals("queen")) return queenDirs;
        return bishopDirs;
    }

    public static void main(String[] args) {
        List<String> pieces = Arrays.asList("rook");
        List<int[]> positions = Arrays.asList(new int[]{1, 1});

        int result = countValidMoves(pieces, positions);
        System.out.println("Valid move combinations: " + result);
    }
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef pair<int, int> pi;

vector<pi> bishopDirs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
vector<pi> rookDirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pi> queenDirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

void backtrack(vector<string>& pieces, vector<pi>& positions, int index, int& count) {
    if (index == pieces.size()) {
        count++;
        return;
    }

    int r = positions[index].first;
    int c = positions[index].second;
    vector<pi> directions;
    if (pieces[index] == "rook")
        directions = rookDirs;
    else if (pieces[index] == "queen")
        directions = queenDirs;
    else
        directions = bishopDirs;

    for (auto [dr, dc] : directions) {
        for (int steps = 1; steps <= 8; steps++) {
            int nr = r + steps * dr;
            int nc = c + steps * dc;
            if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                positions[index] = {nr, nc};
                backtrack(pieces, positions, index + 1, count);
            } else {
                break;
            }
        }
    }

    positions[index] = {r, c};
    backtrack(pieces, positions, index + 1, count);
}

int main() {
    vector<string> pieces = {"bishop"};
    vector<pi> positions = {{4, 3}};

    int count = 0;
    backtrack(pieces, positions, 0, count);
    cout << "Valid move combinations: " << count << endl;
    return 0;
}
function getDirections(piece) {
    if (piece === "rook") {
        return [[0, 1], [0, -1], [1, 0], [-1, 0]];
    } else if (piece === "queen") {
        return [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
    } else {
        return [[1, 1], [1, -1], [-1, 1], [-1, -1]];
    }
}

function backtrack(pieces, positions, index) {
    if (index === pieces.length) return 1;

    let [r, c] = positions[index];
    const directions = getDirections(pieces[index]);
    let count = 0;

    directions.forEach(([dr, dc]) => {
        for (let steps = 1; steps <= 8; steps++) {
            const nr = r + steps * dr;
            const nc = c + steps * dc;

            if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                positions[index] = [nr, nc];
                count += backtrack(pieces, positions, index + 1);
            } else {
                break;
            }
        }
    });

    positions[index] = [r, c];
    count += backtrack(pieces, positions, index + 1);
    
    return count;
}

const pieces = ["bishop"];
const positions = [[4, 3]];
const result = backtrack(pieces, positions, 0);
console.log(`Valid move combinations: ${result}`);
#include <stdio.h>
#include <string.h>

// Function prototypes
typedef struct { int dx, dy; } Direction;

// Directions for bishop
Direction bishopDirections[] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

// Directions for rook
Direction rookDirections[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

// Directions for queen
Direction queenDirections[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

void backtrack(char* pieces[], int positions[][2], int n, int index, int count[]) {
    if (index == n) {
        count[0]++; // Found a valid combination
        return;
    }
    
    int r = positions[index][0];
    int c = positions[index][1];
    Direction* directions;
    int numDirections;
    if (strcmp(pieces[index], "rook") == 0) {
        directions = rookDirections;
        numDirections = sizeof(rookDirections) / sizeof(Direction);
    } else if (strcmp(pieces[index], "queen") == 0) {
        directions = queenDirections;
        numDirections = sizeof(queenDirections) / sizeof(Direction);
    } else { // bishop
        directions = bishopDirections;
        numDirections = sizeof(bishopDirections) / sizeof(Direction);
    }

    for (int dir = 0; dir < numDirections; dir++) {
        for (int steps = 1; steps <= 8; steps++) {
            int newR = r + steps * directions[dir].dx;
            int newC = c + steps * directions[dir].dy;
            if (newR >= 1 && newR <= 8 && newC >= 1 && newC <= 8) {
                positions[index][0] = newR;
                positions[index][1] = newC;
                backtrack(pieces, positions, n, index + 1, count);
            } else {
                break; // Out of bounds
            }
        }
    }

    // Reset to original position
    positions[index][0] = r;
    positions[index][1] = c;
    
    // Also count staying in the same place
    backtrack(pieces, positions, n, index + 1, count);
}

int main() {
    char* pieces[] = { "rook", "bishop" };
    int positions[][2] = { {1, 1}, {2, 2} };
    int n = 2;
    int count[1] = {0};
    
    backtrack(pieces, positions, n, 0, count);
    printf("Valid move combinations: %d\n", count[0]);
    return 0;
}
using System;
using System.Collections.Generic;

class ChessMoveCombinations {
    static List<(int, int)> bishopDirs = new List<(int, int)>
    {
        (1, 1), (1, -1), (-1, 1), (-1, -1)
    };
    static List<(int, int)> rookDirs = new List<(int, int)>
    {
        (0, 1), (0, -1), (1, 0), (-1, 0)
    };
    static List<(int, int)> queenDirs = new List<(int, int)>
    {
        (0, 1), (0, -1), (1, 0), (-1, 0),
        (1, 1), (1, -1), (-1, 1), (-1, -1)
    };

    static void Main() {
        List<string> pieces = new List<string> { "bishop" };
        List<(int, int)> positions = new List<(int, int)> { (4, 3) };

        int result = Backtrack(pieces, positions, 0);
        Console.WriteLine("Valid move combinations: " + result);
    }

    static int Backtrack(List<string> pieces, List<(int, int)> positions, int index) {
        if (index == positions.Count)
            return 1;

        int r = positions[index].Item1;
        int c = positions[index].Item2;
        List<(int, int)> directions = GetDirections(pieces[index]);
        int count = 0;

        foreach (var dir in directions) {
            for (int step = 1; step <= 8; step++) {
                int nr = r + step * dir.Item1;
                int nc = c + step * dir.Item2;

                if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                    positions[index] = (nr, nc);
                    count += Backtrack(pieces, positions, index + 1);
                } else {
                    break;
                }
            }
        }

        positions[index] = (r, c);
        count += Backtrack(pieces, positions, index + 1);

        return count;
    }

    static List<(int, int)> GetDirections(string piece) {
        if (piece == "rook") return rookDirs;
        if (piece == "queen") return queenDirs;
        return bishopDirs;
    }
}

In this Python implementation, each piece's possible moves are sequentially tried out using a recursive function that allows exploration of all valid moves within chessboard boundaries. Backtracking is used to evaluate all possible configurations of piece movements for legitimacy, culminating in a count of all valid combinations.

Complexity

The method's Time Complexity is O(8^n) with n pieces, while Space Complexity is O(n) from recursion breadth.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

A dynamic programming solution is possible by using a memoization technique to count valid move configurations. This approach calculates configurations for smaller subsets of moves and combines them to create complete solutions, avoiding redundant calculations.

def piece_directions(piece):
    directions = {
        "rook": [(0, 1), (0, -1), (1, 0), (-1, 0)],
        "bishop": [(1, 1), (1, -1), (-1, 1), (-1, -1)],
        "queen": [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    }
    return directions[piece]


def count_moves(pieces, positions, index, memo):
    if index == len(pieces):
        return 1

    piece = pieces[index]
    r, c = positions[index]
    if memo[index][r][c] != -1:
        return memo[index][r][c]

    count = 0
    for dr, dc in piece_directions(piece):
        for steps in range(BOARD_SIZE + 1):
            nr, nc = r + dr * steps, c + dc * steps
            if 1 <= nr <= BOARD_SIZE and 1 <= nc <= BOARD_SIZE:
                positions[index] = (nr, nc)
                count += count_moves(pieces, positions, index + 1, memo)
    positions[index] = (r, c)

    memo[index][r][c] = count
    return count


if __name__ == "__main__":
    BOARD_SIZE = 8
    pieces = ["queen", "rook"]
    positions = [(1, 1), (2, 2)]
    memo = [[[-1 for _ in range(BOARD_SIZE + 1)] for _ in range(BOARD_SIZE + 1)] for _ in range(len(pieces))]

    result = count_moves(pieces, positions, 0, memo)
    print("Valid move combinations:", result)
import java.util.*;

public class ChessMoves {
    static final int BOARD_SIZE = 8;
    static Map<String, List<int[]>> directions = new HashMap<>();
    static int[][][] memo;

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

    public static void main(String[] args) {
        List<String> pieces = Arrays.asList("rook", "bishop");
        int[][] positions = {{4, 3}, {5, 5}};
        memo = new int[pieces.size()][BOARD_SIZE + 1][BOARD_SIZE + 1];
        for (int[][] m : memo) for (int[] row : m) Arrays.fill(row, -1);

        int result = countMoves(pieces, positions, 0);
        System.out.println("Valid move combinations: " + result);
    }

    private static int countMoves(List<String> pieces, int[][] positions, int idx) {
        if (idx == pieces.size()) return 1;
        String piece = pieces.get(idx);
        int r = positions[idx][0], c = positions[idx][1];
        if (memo[idx][r][c] != -1) return memo[idx][r][c];

        int count = 0;
        for (int[] dir : directions.get(piece)) {
            for (int step = 0; step <= BOARD_SIZE; step++) {
                int nr = r + step * dir[0], nc = c + step * dir[1];
                if (nr >= 1 && nr <= BOARD_SIZE && nc >= 1 && nc <= BOARD_SIZE) {
                    positions[idx][0] = nr;
                    positions[idx][1] = nc;
                    count += countMoves(pieces, positions, idx + 1);
                }
            }
        }
        positions[idx][0] = r;
        positions[idx][1] = c;

        return memo[idx][r][c] = count;
    }
}
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define BOARD_SIZE 8
#define MAX_MOVES 4

int memo[MAX_MOVES][BOARD_SIZE + 1][BOARD_SIZE + 1];

vector<vector<pair<int, int>>> directions = {
    { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }, // Rook
    { {1, 1}, {1, -1}, {-1, 1}, {-1, -1} }, // Bishop
    { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} } // Queen
};

int pieceIndex(string piece) {
    if (piece == "rook") return 0;
    if (piece == "bishop") return 1;
    return 2;
}

int countMoves(vector<string>& pieces, vector<pair<int, int>>& positions, int index) {
    if (index == pieces.size()) return 1;

    int piece = pieceIndex(pieces[index]);
    int r = positions[index].first, c = positions[index].second;

    if (memo[index][r][c] != -1) return memo[index][r][c];

    int count = 0;
    for (auto dir : directions[piece]) {
        int dr = dir.first, dc = dir.second;
        for (int steps = 0; steps <= BOARD_SIZE; steps++) {
            int nr = r + steps * dr;
            int nc = c + steps * dc;

            if (nr >= 1 && nr <= BOARD_SIZE && nc >= 1 && nc <= BOARD_SIZE) {
                positions[index] = {nr, nc};
                count += countMoves(pieces, positions, index + 1);
            }
        }
    }
    positions[index] = {r, c};

    return memo[index][r][c] = count;
}

int main() {
    vector<string> pieces = { "queen" };
    vector<pair<int, int>> positions = { {1, 1} };

    memset(memo, -1, sizeof(memo));
    int result = countMoves(pieces, positions, 0);

    cout << "Valid move combinations: " << result << endl;
    return 0;
}
function getDirections(piece) {
    const directions = {
        "rook": [[0, 1], [0, -1], [1, 0], [-1, 0]],
        "bishop": [[1, 1], [1, -1], [-1, 1], [-1, -1]],
        "queen": [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
    };
    return directions[piece];
}

function countMoves(pieces, positions, index, memo) {
    if (index === pieces.length) return 1;

    let [r, c] = positions[index];

    if (memo[index][r][c] != null) return memo[index][r][c];

    let directions = getDirections(pieces[index]);
    let count = 0;

    for (let [dr, dc] of directions) {
        for (let steps = 0; steps <= 8; steps++) {
            let nr = r + dr * steps;
            let nc = c + dc * steps;
            if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                positions[index] = [nr, nc];
                count += countMoves(pieces, positions, index + 1, memo);
            }
        }
    }
    positions[index] = [r, c];
    memo[index][r][c] = count;
    return count;
}

const pieces = ["queen", "rook"];
const positions = [[1, 1], [2, 2]];
let memo = Array.from({ length: pieces.length }, () => Array.from({ length: 9 }, () => Array(9).fill(null)));

console.log(`Valid move combinations: ${countMoves(pieces, positions, 0, memo)}`);
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_N 4
#define BOARD_SIZE 8

int memo[MAX_N][BOARD_SIZE + 1][BOARD_SIZE + 1];

int directions[3][8][2] = {
    {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, // Rook
    {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, // Bishop
    {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}} // Queen
};

int pieceIndex(char* piece) {
    if (strcmp(piece, "rook") == 0) return 0;
    if (strcmp(piece, "bishop") == 0) return 1;
    return 2;
}

int countMoves(char* pieces[], int positions[][2], int n, int index) {
    if (index == n) return 1;
    int piece = pieceIndex(pieces[index]);
    int r = positions[index][0];
    int c = positions[index][1];
    if (memo[index][r][c] != -1) return memo[index][r][c];

    int count = 0;
    for (int dir = 0; dir < 8; dir++) {
        int dr = directions[piece][dir][0];
        int dc = directions[piece][dir][1];
        for (int steps = 0; steps <= BOARD_SIZE; steps++) {
            int nr = r + steps * dr;
            int nc = c + steps * dc;
            // Check bounds
            if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                positions[index][0] = nr;
                positions[index][1] = nc;
                count += countMoves(pieces, positions, n, index + 1);
            }
        }
    }

    // Reset to original position
    positions[index][0] = r;
    positions[index][1] = c;

    return memo[index][r][c] = count;
}

int main() {
    char* pieces[] = { "queen", "rook" };
    int positions[][2] = { {1, 1}, {2, 2} };
    int n = 2;
    memset(memo, -1, sizeof(memo));

    int result = countMoves(pieces, positions, n, 0);
    printf("Valid move combinations: %d\n", result);

    return 0;
}
using System;
using System.Collections.Generic;

class ChessDynProg {
    static Dictionary<string, List<(int, int)>> directions = new Dictionary<string, List<(int, int)>> {
        { "rook", new List<(int, int)> { (0, 1), (0, -1), (1, 0), (-1, 0) } },
        { "bishop", new List<(int, int)> { (1, 1), (1, -1), (-1, 1), (-1, -1) } },
        { "queen", new List<(int, int)> { (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1) } }
    };

    static int[,,] memo;

    static void Main() {
        var pieces = new List<string> { "rook", "bishop" };
        var positions = new List<(int, int)> { (4, 3), (5, 5) };
        memo = new int[pieces.Count, 9, 9];
        for (int i = 0; i < pieces.Count; i++)
            for (int j = 0; j <= 8; j++)
                for (int k = 0; k <= 8; k++)
                    memo[i, j, k] = -1;

        int result = CountMoves(pieces, positions, 0);
        Console.WriteLine($"Valid move combinations: {result}");
    }

    static int CountMoves(List<string> pieces, List<(int, int)> positions, int index) {
        if (index == pieces.Count) return 1;

        string piece = pieces[index];
        int r = positions[index].Item1, c = positions[index].Item2;

        if (memo[index, r, c] != -1) return memo[index, r, c];

        int count = 0;
        foreach (var dir in directions[piece]) {
            for (int steps = 0; steps <= 8; steps++) {
                int nr = r + steps * dir.Item1, nc = c + steps * dir.Item2;
                if (nr >= 1 && nr <= 8 && nc >= 1 && nc <= 8) {
                    positions[index] = (nr, nc);
                    count += CountMoves(pieces, positions, index + 1);
                }
            }
        }
        positions[index] = (r, c);

        return memo[index, r, c] = count;
    }
}

Python implementation functions by storing resolutions of various moves and uses them to generate possible configurations of all pieces effectively. Memoization ensures subproblems do not require repetitive calculation.

Complexity

By implementing memoization, the Time Complexity becomes O(M*N) and Space Complexity manages through efficient storage only using placement combinations rather than all paths.

Try this approach in the editor

Approach 3: DFS

The problem has at most 4 pieces, and each piece can move in up to 8 directions. We can consider using DFS to search all possible move combinations.

We enumerate each piece in order. For each piece, we can choose not to move or move according to the rules. We use an array dist[i] to record the movement of the i-th piece, where dist[i][x][y] represents the time when the i-th piece passes through the coordinate (x, y). We use an array end[i] to record the endpoint coordinates and time of the i-th piece. During the search, we need to determine whether the current piece can stop moving and whether it can continue moving in the current direction.

We define a method checkStop(i, x, y, t) to determine whether the i-th piece can stop at coordinate (x, y) at time t. If for all previous pieces j, dist[j][x][y] < t, then the i-th piece can stop moving.

Additionally, we define a method checkPass(i, x, y, t) to determine whether the i-th piece can pass through coordinate (x, y) at time t. If any other piece j also passes through coordinate (x, y) at time t, or if any other piece j stops at (x, y) and the time does not exceed t, then the i-th piece cannot pass through coordinate (x, y) at time t.

The time complexity is O((n times M)^n), and the space complexity is O(n times M). Here, n is the number of pieces, and M is the movement range of each piece.

const rookDirs: [number, number][] = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
];
const bishopDirs: [number, number][] = [
    [1, 1],
    [1, -1],
    [-1, 1],
    [-1, -1],
];
const queenDirs = [...rookDirs, ...bishopDirs];

function countCombinations(pieces: string[], positions: number[][]): number {
    const n = pieces.length;
    const m = 9;
    let ans = 0;

    const dist = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => Array(m).fill(-1)),
    );

    const end: [number, number, number][] = Array(n).fill([0, 0, 0]);

    const resetDist = (i: number) => {
        for (let j = 0; j < m; j++) {
            for (let k = 0; k < m; k++) {
                dist[i][j][k] = -1;
            }
        }
    };

    const checkStop = (i: number, x: number, y: number, t: number): boolean => {
        for (let j = 0; j < i; j++) {
            if (dist[j][x][y] >= t) {
                return false;
            }
        }
        return true;
    };

    const checkPass = (i: number, x: number, y: number, t: number): boolean => {
        for (let j = 0; j < i; j++) {
            if (dist[j][x][y] === t) {
                return false;
            }
            if (end[j][0] === x && end[j][1] === y && end[j][2] <= t) {
                return false;
            }
        }
        return true;
    };

    const isValid = (x: number, y: number): boolean => {
        return x >= 1 && x < m && y >= 1 && y < m;
    };

    const getDirs = (piece: string): [number, number][] => {
        switch (piece[0]) {
            case 'r':
                return rookDirs;
            case 'b':
                return bishopDirs;
            default:
                return queenDirs;
        }
    };

    const dfs = (i: number) => {
        if (i >= n) {
            ans++;
            return;
        }

        const [x, y] = positions[i];
        resetDist(i);
        dist[i][x][y] = 0;
        end[i] = [x, y, 0];

        if (checkStop(i, x, y, 0)) {
            dfs(i + 1);
        }

        const dirs = getDirs(pieces[i]);
        for (const [dx, dy] of dirs) {
            resetDist(i);
            dist[i][x][y] = 0;
            let nx = x + dx,
                ny = y + dy,
                nt = 1;

            while (isValid(nx, ny) && checkPass(i, nx, ny, nt)) {
                dist[i][nx][ny] = nt;
                end[i] = [nx, ny, nt];
                if (checkStop(i, nx, ny, nt)) {
                    dfs(i + 1);
                }
                nx += dx;
                ny += dy;
                nt++;
            }
        }
    };

    dfs(0);
    return ans;
}
func countCombinations(pieces []string, positions [][]int) (ans int) {
	n := len(pieces)
	m := 9
	dist := make([][][]int, n)
	for i := range dist {
		dist[i] = make([][]int, m)
		for j := range dist[i] {
			dist[i][j] = make([]int, m)
		}
	}

	end := make([][3]int, n)

	rookDirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	bishopDirs := [][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
	queenDirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}

	resetDist := func(i int) {
		for j := 0; j < m; j++ {
			for k := 0; k < m; k++ {
				dist[i][j][k] = -1
			}
		}
	}

	checkStop := func(i, x, y, t int) bool {
		for j := 0; j < i; j++ {
			if dist[j][x][y] >= t {
				return false
			}
		}
		return true
	}

	checkPass := func(i, x, y, t int) bool {
		for j := 0; j < i; j++ {
			if dist[j][x][y] == t {
				return false
			}
			if end[j][0] == x && end[j][1] == y && end[j][2] <= t {
				return false
			}
		}
		return true
	}

	isValid := func(x, y int) bool {
		return x >= 1 && x < m && y >= 1 && y < m
	}

	getDirs := func(piece string) [][2]int {
		switch piece[0] {
		case 'r':
			return rookDirs
		case 'b':
			return bishopDirs
		default:
			return queenDirs
		}
	}

	var dfs func(i int)
	dfs = func(i int) {
		if i >= n {
			ans++
			return
		}

		x, y := positions[i][0], positions[i][1]
		resetDist(i)
		dist[i][x][y] = 0
		end[i] = [3]int{x, y, 0}

		if checkStop(i, x, y, 0) {
			dfs(i + 1)
		}

		dirs := getDirs(pieces[i])
		for _, dir := range dirs {
			resetDist(i)
			dist[i][x][y] = 0
			nx, ny, nt := x+dir[0], y+dir[1], 1

			for isValid(nx, ny) && checkPass(i, nx, ny, nt) {
				dist[i][nx][ny] = nt
				end[i] = [3]int{nx, ny, nt}
				if checkStop(i, nx, ny, nt) {
					dfs(i + 1)
				}
				nx += dir[0]
				ny += dir[1]
				nt++
			}
		}
	}

	dfs(0)
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Backtracking Approach

The method's Time Complexity is O(8^n) with n pieces, while Space Complexity is O(n) from recursion breadth.

Dynamic Programming Approach

By implementing memoization, the Time Complexity becomes O(M*N) and Space Complexity manages through efficient storage only using placement combinations rather than all paths.

DFS–

Complexity analysis

ApproachTimeSpaceWhen to Use
Backtracking + Move SimulationO(k * directions^k * steps)O(k * directions^k)Best for interview solutions where the number of pieces is small and full enumeration with pruning is feasible
Dynamic Programming with State TrackingO(states * moves)O(states)Useful when avoiding repeated simulations or analyzing board states across time steps

Frequently asked questions

Is Number of Valid Move Combinations On Chessboard easy or hard?

Number of Valid Move Combinations On Chessboard is classified as a Hard problem. The challenge comes from modeling simultaneous movement and detecting collisions during intermediate steps, which requires careful simulation combined with backtracking search.

Number of Valid Move Combinations On Chessboard Python/Java solution

Python and Java implementations typically use recursive backtracking. For each piece, iterate through all valid directions and possible stopping distances, record the chosen move, and simulate movements step-by-step to ensure no two pieces share a square at the same time.

How to solve Number of Valid Move Combinations On Chessboard in O(n)?

A strict O(n) solution does not exist because the problem requires exploring combinations of directions and movement lengths for multiple pieces. The search space grows exponentially with the number of pieces. Efficient solutions rely on pruning invalid states early during backtracking or caching states using dynamic programming.

What is the best approach for Number of Valid Move Combinations On Chessboard?

Backtracking with step-by-step simulation is the most practical approach. Enumerate every direction and stopping distance for each piece, then simulate movements simultaneously to detect collisions at each time step. Because the number of pieces is small, this exhaustive search remains manageable while guaranteeing correctness.

Is Number of Valid Move Combinations On Chessboard asked at Google/Amazon/Meta?

Problems involving chess movement simulation, collision detection, and combinational search frequently appear in interviews at companies like Google, Amazon, and Meta. Variants test backtracking, board simulation, and constraint validation across multiple moving entities.

What data structure is used in Number of Valid Move Combinations On Chessboard?

Common implementations use arrays or coordinate lists to store piece positions and movement directions. Backtracking relies on recursion stacks, while simulation tracks positions over time using arrays or hash sets to detect collisions.

What is the time complexity of Number of Valid Move Combinations On Chessboard?

The typical backtracking solution runs in roughly O(k * directions^k * steps), where k is the number of pieces. Each piece can choose several directions and distances, and every candidate combination requires a simulation across movement steps. Space complexity is mainly recursion and state storage, around O(k * directions^k).

Comments

Now write it yourselfClose this page and solve Number of Valid Move Combinations On Chessboard in the editor, without looking.
Practise Number of Valid Move Combinations On Chessboard