为什么这种解决 8 个皇后问题的方法总是返回 0

Question

这是我的代码。

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;
}

我正在尝试解决 CSES“棋盘和皇后”问题。称为 il 的字符串向量表示不能包含任何皇后的正方形。

输入示例：

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

但是我的代码总是返回 0（令人惊讶的是 y 从来不是 7），我不明白为什么。你能帮帮我吗？

Answer 1

尝试添加回溯：

#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;
}