# Using brute force to solve a hard problem

LC 2056. Number of Valid Move Combinations On Chessboard

This is a 4th hard problem of the LC biweekly 64 contest problem. As `1 <= n <= 4, we can solve it by brute force and process those four cases one by one.`

# Key ideas:

• n = 1: return all possible moves
• n = 2: for all possible moves (suppose we have a and b moves), check whether it is valid for a and b.
• n = 2: for all possible moves(suppose we have a, b, c 3 moves), check whether it is valid for (a, b), (a, c) and (b, c)
• n = 4: for all possible moves(suppose we have a, b, c, d 4 moves), check whether it is valid for (a, b), (a, c), (a, d), (b, c), (b, d), and (c, d)

It looks not that smart, however, it can be used as a baseline solution. Since it can get AC, actually, it change a hard problem to a relatively easier to be solved problem, although the code length is long.

# Reference Code

`using PII = pair<int, int>;class Solution {    public:    vector<pair<PII, int>> helper(string p, int i, int j){        // get all possible moves        vector<pair<PII, int>> ret;        ret.emplace_back(make_pair(i, j), 0);        vector<PII> dirs;        if (p == "rook"){            dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};        }        if (p == "queen"){            dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};        }        if (p == "bishop"){            dirs = {{1, 1}, {-1, -1}, {-1, 1}, {1, -1}};        }        for (auto [di, dj]: dirs){            for (int step = 1; step <= 8; ++step){                int r = i + step*di, c = j + step*dj;                if (r < 0 || r >=8 || c < 0 || c >= 8 )continue;                ret.emplace_back(make_pair(di, dj), step);}        }        return ret;}bool valid(int r1, int c1, int di1, int dj1, int step1, int r2, int c2, int di2, int dj2, int step2){        int s1 = -1, s2 = -1;        // check whether they will occupy the same cell.        while (!(s1 == step1 && s2 == step2)){            s1 = min(step1, s1 + 1);            s2 = min(step2, s2 + 1);`            if (r1 + s1*di1 == r2 + s2*di2 &&  c1 + s1*dj1 == c2 + s2*dj2){                return false;            }        }        return true;    }    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {        const int n = pieces.size();        for (int i = 0; i < n; ++i){            positions[i][0]--;            positions[i][1]--;        }        vector<vector<PII>> states(n);        int ret = 0;        if (n == 1){            auto kk = helper(pieces[0], positions[0][0], positions[0][1]);            return kk.size();        }        if (n == 2){            string p1 = pieces[0], p2 = pieces[1];            int r1 = positions[0][0], c1 = positions[0][1];            int r2 = positions[1][0], c2 = positions[1][1];            auto a = helper(p1, r1, c1);            auto b = helper(p2, r2, c2);            for (auto [didj1, step1]: a){                for (auto [didj2, step2]: b){                    auto [di1, dj1] = didj1;                    auto [di2, dj2] = didj2;                    ret += valid(r1, c1, di1, dj1, step1, r2, c2, di2, dj2, step2);                }            }        }        if (n == 3){            string p1 = pieces[0], p2 = pieces[1], p3= pieces[2];            int r1 = positions[0][0], c1 = positions[0][1];            int r2 = positions[1][0], c2 = positions[1][1];            int r3 = positions[2][0], c3 = positions[2][1];            auto a = helper(p1, r1, c1);            auto b = helper(p2, r2, c2);            auto c = helper(p3, r3, c3);            for (auto [didj1, step1]: a){                for (auto [didj2, step2]: b)                    for (auto [didj3, step3]: c){                        auto [di1, dj1] = didj1;                        auto [di2, dj2] = didj2;                        auto [di3, dj3] = didj3;                        ret += valid(r1, c1, di1, dj1, step1, r2, c2, di2, dj2, step2) &&                            valid(r1, c1, di1, dj1, step1, r3, c3, di3, dj3, step3) &&                            valid(r2, c2, di2, dj2, step2, r3, c3, di3, dj3, step3);                    }            }}        if (n == 4){            string p1 = pieces[0], p2 = pieces[1], p3= pieces[2], p4= pieces[3];            int r1 = positions[0][0], c1 = positions[0][1];            int r2 = positions[1][0], c2 = positions[1][1];            int r3 = positions[2][0], c3 = positions[2][1];            int r4 = positions[3][0], c4 = positions[3][1];            auto a = helper(p1, r1, c1);            auto b = helper(p2, r2, c2);            auto c = helper(p3, r3, c3);            auto d = helper(p4, r4, c4);              for (auto [didj1, step1]: a){                for (auto [didj2, step2]: b)                    for (auto [didj3, step3]: c)                        for (auto [didj4, step4]: d){                            auto [di1, dj1] = didj1;                            auto [di2, dj2] = didj2;                            auto [di3, dj3] = didj3;                            auto [di4, dj4] = didj4;                            ret += valid(r1, c1, di1, dj1, step1, r2, c2, di2, dj2, step2) &&                                valid(r1, c1, di1, dj1, step1, r3, c3, di3, dj3, step3) &&                                 valid(r1, c1, di1, dj1, step1, r4, c4, di4, dj4, step4) &&                                valid(r2, c2, di2, dj2, step2, r3, c3, di3, dj3, step3) &&                                valid(r2, c2, di2, dj2, step2, r4, c4, di4, dj4, step4) &&                                valid(r3, c3, di3, dj3, step3, r4, c4, di4, dj4, step4);                        }            }}        return ret;}};`

# A general solution by using backtrack

We can also use the backtracking to solve the problem. Basic ideas:

• Put one chess at each step for each valid positions (new position will be the result of direction and moving steps).
• If we have n chess putted in the chess board, check whether it is a valid state and update res accordingly.

## Reference code

`using PII = pair<int, int>;unordered_map<string, vector<PII>> dirs = {    {"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}}}};class Solution {    public:    vector<string>pieces;    vector<vector<int>> positions;    int ret;    // check whether two chesses positions are valid    bool valid(int r1, int c1, int di1, int dj1, int step1, int r2, int c2, int di2, int dj2, int step2){        int s1 = -1, s2 = -1;        // check whether they will occupy the same cell.        while (!(s1 == step1 && s2 == step2)){            // if one chess reach the target position, then do not move.            s1 = min(step1, s1 + 1);            s2 = min(step2, s2 + 1);            if (r1 + s1*di1 == r2 + s2*di2 &&  c1 + s1*dj1 == c2 + s2*dj2){                return false;            }        }        return true;    }    bool all_valid(vector<pair<PII, int>> chess_positions){        if (chess_positions.size() <= 1) return true;        const int n = chess_positions.size();        for (int i = 0; i < n - 1; ++i){            for (int j = i + 1;j < n; ++j){                int r1 = positions[i][0],  c1 = positions[i][1], r2= positions[j][0],  c2 = positions[j][1];                auto [didj1, step1] = chess_positions[i];                auto [didj2, step2] = chess_positions[j];                auto [di1, dj1] = didj1;                auto [di2, dj2] = didj2;                if (!valid(r1, c1, di1, dj1, step1, r2, c2, di2, dj2, step2)){                    return false;                }            }        }        return true;    }    void backtrack( vector<pair<PII, int>>& chess_positions){        if (chess_positions.size() == pieces.size()){            ret += all_valid(chess_positions);            return;        }        // explore the next chess        int idx = chess_positions.size();        int i = positions[idx][0], j = positions[idx][1];        string chess = pieces[idx];        // stay         chess_positions.emplace_back(make_pair(0, 0), 0);        backtrack(chess_positions);        chess_positions.pop_back();        for (auto [di, dj]: dirs[chess]){            for (int step = 1; step <= 8; ++ step){                int r = i + step*di, c = j + step*dj;                               if (r < 0 || r >= 8 || c < 0 || c >= 8)break;                chess_positions.emplace_back(make_pair(di, dj), step);                backtrack(chess_positions);                chess_positions.pop_back();            }          }    }    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {        this -> pieces = pieces;        this -> positions = positions;        ret = 0;        const int n = pieces.size();        for (int i = 0; i < n; ++i){             this -> positions[i][0]--;             this -> positions[i][1]--;        }        vector<pair<PII, int>>chess_positions;        backtrack(chess_positions);        return ret;    }};`

Thanks for reading, more of my articles in different topics can be found here.

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi