# Chessboard and Queens

## Problem Info

Chessboard and Queens to problem here

## My Work

#include <bits/stdc++.h>

using namespace std;

char tab;
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)
{
// one answer found
ans++;
return;
}
else
{
// no further possible answers
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 …

## Question

please help me to see if my implementation is corret?

Clearly not, as your program doesn’t solve the sample case. I’d recommend first trying to get your code to work on smaller board sizes (say, 2\times 2) or making sure you understand the backtracking code in Complete Search with Recursion. (And if the explanation is unclear, please suggest how it could be improved.)

you see the solution isn’t well explained , especially with regards to how to check if position x is valid to place a queen. I maybe try a 2*2 grid sounds a good idea

Fair enough, but the resources linked on that page (CPH and CP2) have better explanations.