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.