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.
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.