c++backtracking

Why this approach to 8 Queens problem always returns 0


Here is my code.

using namespace std;


int ans = 0;
string il[8]; //squares which cannot contain any queens


void quen(int x, int y, bool table1[15],bool table2[15], bool table3[8]){
    if(il[y][x]!='*'){
        if(table3[x]==0){
            if(table2[x+y]==0){
                if(table1[7-y+x]==0){
                    table1[7-y+x]=1;
                    table2[x+y]=1;
                    table3[x]=1;
                    
                    if(y==7){
                        ans++;
                        return;
                    }
                    else{
                        for (int i = 0; i<8; i++) {
                            quen(i, y+1, table1, table2, table3);
                        }
                    }
                }
                
            }
        }
    }
}

int main(){
    for (int i = 0; i<8; i++) {
        string str;
        cin>>str;
        il[i]=str;
    }
    bool table1[15]={0};
    bool table2[15]={0};
    bool table3[8]={0};
    for(int i = 0; i<8; i++){
        quen(i, 0, table1, table2, table3);
    }
    cout << ans << endl;
}

I'm trying to solve the CSES "Chessboard and Queens" problem. The vector of strings called il represents the squares which cannot contain any queens.

Example Input:

........
........
..*.....
........
........
.....**.
...*....
........

But my code always returns 0(surprisingly y is never 7) and I couldn't figure out why. Can you please help me.


Solution

  • Try adding backtracking:

    #include <iostream>
     
    using namespace std;
     
    int ans = 0;
    string il[8]; // squares which cannot contain any queens
     
    void quen(int x, int y, bool table1[15], bool table2[15], bool table3[8]) {
      if (il[y][x] != '*' && !table3[x] && !table2[x + y] && !table1[7 - y + x]) {
        table1[7 - y + x] = true;
        table2[x + y] = true;
        table3[x] = true;
        if (y == 7) {
          ans++;
        } else {
          for (int i = 0; i < 8; i++) {
            quen(i, y + 1, table1, table2, table3);
          }
        }
        table1[7 - y + x] = false;
        table2[x + y] = false;
        table3[x] = false;
      }
    }
     
    int main() {
      for (int i = 0; i < 8; i++) {
        string str;
        cin >> str;
        il[i] = str;
      }
      bool table1[15] = {0};
      bool table2[15] = {0};
      bool table3[8] = {0};
      for (int i = 0; i < 8; i++) {
        quen(i, 0, table1, table2, table3);
      }
      cout << ans << endl;
    }
    

    Note: There are many best practices that can be followed to improve the readability of this code.