Chessboard and Queens

Debugging Help
#1

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)
    {
        // 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?

#2

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

#3

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

#4

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