CODEWITHSUNDEEP
c++
ianspivey11
ianspivey11

Reputation: 43

N queens solution is incorrect and im not sure why

So I am solving the N queens problem, where you have to find the number of possible solutions to have a number N queens on an NxN chess board without them being able to attack each other. I am doing it using recursive backtracking. I have implemented my solution in code already, but for some reason I am not getting the correct number of solutions, and I can't figure out why.

Here is my code:

#include <iostream>
#include <vector>

using namespace std;

int numSolutions=0;

//Uses recursion to count how many solutions there are for
//placing n queens on an nxn chess board
bool isSafe(vector<vector<int>>board, int row, int col){
    //checks column for queens
    for(int i=0; i<row; i++){
        if(board[i][col]==1){
            return false;
        }
    }
    
    //checks right diagonal for queens(\)
    for(int i=row, x=col; i>= 0 && x>=0; i--, x--){
        if(board[i][x]==1){
            return false;
        }
    }
    
    //checks left diagonal for queens(/)
    for(int i=row, x=col; i>= 0 && x>=0; i--, x++){
        if(board[i][x]==1){
            return false;
        }
    }
    
    //returns true once all conditions are met for queen to be safe
    return true;
}



void nQueensSolution(vector<vector<int>>board, int row, int n){
    //base case, adds to number of solutions if queens are placed successfully
    if(row==n){
        numSolutions++;
        return;
    }
    
    //places a queen in the square if it is safe
    for(int i=0; i<n; i++){
        if(isSafe(board, row, i)==true){
            board[row][i]=1;
            
            //recurring function to move onto next row to find solution
            nQueensSolution(board, row+1, n);
            
            //backtrack to try the other squares in current row
            board[row][i]=0;
        }
    }
    
}

int nQueens(int n)
{
    //Implement int nQueens(int n)
    //Feel free to implement any recursive helper functions
    vector<vector<int>>board(n, vector<int>(n));
    int row=0;
    nQueensSolution(board, row, n);
    return numSolutions;
}

int main()
{
    cout << "1: " << nQueens(1) << endl;
    numSolutions=0;
    cout << "2: " << nQueens(2) << endl;
    numSolutions=0;
    cout << "3: " << nQueens(3) << endl;
    numSolutions=0;
    cout << "4: " << nQueens(4) << endl;
    numSolutions=0;
    cout << "5: " << nQueens(5) << endl;
    numSolutions=0;
    cout << "6: " << nQueens(6) << endl;
    numSolutions=0;
    cout << "7: " << nQueens(7) << endl;
    numSolutions=0;
    cout << "8: " << nQueens(8) << endl;
    numSolutions=0;
    cout << "9: " << nQueens(9) << endl;
    numSolutions=0;
    cout << "10: " << nQueens(10) << endl;
    numSolutions=0;
    cout << "11: " << nQueens(11) << endl;
    numSolutions=0;
    cout << "12: " << nQueens(12) << endl;
    return 0;
}

and here is the output

1: 1
2: 0
3: 0
4: 2
5: 10
6: 3
7: 39
8: 87
9: 291
10: 514
11: 2380
12: 11073

The number of solutions for every n after 5 is incorrect.

The correct solutions (expected output) is:

1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
11: 2680
12: 14200

So obviously somewhere I messed up and solutions that are valid are not being counted and I can't figure out where the issue is.

A note about my code: the reasoning to have both a nQueens and nQueensSolution function is that for my assignment the function definition of nQueens had to stay as it is, so I used an extra function to make it easier to code.

Upvotes: 2

Views: 391

Answers (2)

vikram
vikram

Reputation: 364

I know the question has been answered. Just making another point. Couldn't stop myself

You could have written you main as below :)

int main()
{
    for(int i=1; i<=12; ++i) {
        std::cout << i << ": " << nQueens(i) << std::endl;
        numSolutions = 0;
    }
}

And don't use global variables.

Upvotes: 0

magmine
magmine

Reputation: 162

Your problem is with the isSafe function where you are not checking fully the diagonals:

bool isSafe(vector<vector<int>>board, int row, int col){
//checks column for queens

int n = board.size();

for(int i=0; i<row; i++){
    if(board[i][col]==1){
        return false;
    }
}

//checks right diagonal for queens(\)
for(int i=row, x=col; i>= 0 && x>=0; i--, x--){
    if(board[i][x]==1){
        return false;
    }
}

for(int i=row, x=col; i < n && x<n; i++, x++){
    if(board[i][x]==1){
        return false;
    }
}


//checks left diagonal for queens(/)
for(int i=row, x=col; i< n && x>=0; i++, x--){
    if(board[i][x]==1){
        return false;
    }
}


for(int i=row, x=col; i>= 0 && x< n; i--, x++){
    if(board[i][x]==1){
        return false;
    }
}

//returns true once all conditions are met for queen to be safe
return true;
}

Upvotes: 2

Related Questions