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