Chessboard and Queens

Problem Info

Chessboard and Queens to problem here

My Work

#include <bits/stdc++.h>

using namespace std;

char tab[8][8];
int ans = 0;

bool isValid(int current , int tosee){

if(tab[current][tosee]=='*')
{
return false;
}

for(int i = 0 ; i < current ; i++)
{
if(tab[i][tosee]=='1')
{

return false;
}
}

for(int x = current , y = tosee ; x > 0 && y > 0 ; x-- , y--)
{
if(tab[x][y] == '1')
{

return false;
}
}

for(int x = current , y = tosee ; x > 0 && y > 0 ; x-- , y++)
{
if(tab[x][y] == '1')
{

return false;
}
}

return true;
}

void backtrack(int current_queen , int previous_pos){
if(current_queen >8 || current_queen < 0)
{
// if current queen is under or above 0 stop backtracking

if(current_queen > 8)
{
ans++;
return;
}
else
{
cout << ans;
exit(0);
}

}
else
{

for(int i  = 0 ; i < 8 ; i++)
{
// for each position in the ligne check if its a valid placement ( recusively )
if(isValid(current_queen,i))
{
tab[current_queen][i]='1';
previous_pos = i;
backtrack(current_queen+1 , previous_pos);

}
}
// backtracking to find new solutions
tab[current_queen][previous_pos] = '.';
backtrack(current_queen-1 , previous_pos);

}

}

int main()
{

for(int i = 0 ; i < 8 ;i++)
for(int j = 0 ; j < 8 ;j++)
cin >> tab[i][j];

backtrack(0 , 0);

return 0;
}



classical backtracking through all possible positions to place the queen.

What I’ve Tried

the logic that i am following is this :

1. Start in the leftmost column
2. If all queens are placed
return true
3. Try all rows in the current column.
Do following for every tried row.
a) If the queen can be placed safely in this row
then mark this [row, column] as part of the
solution and recursively check if placing
queen here leads to a solution.
b) If placing the queen in [row, column] leads to
a solution then return true.
c) If placing queen doesn’t lead to a solution then
unmark this [row, column] (Backtrack) and go to
step (a) to try other rows.
4. If all rows have been tried and nothing worked,
return false to trigger backtracking.

i think its my understading or implementation of backtracking that is off but i just can’t understand the tutorials on it …