N-Queen Problem: Cannot figure out why my solution is not working

Question

I was having a go at the standard N-Queens problem for an upcoming interview. I have tried to dry run my code and it seems to work fine. I can't spot the error in my code.

I am traversing it column by column, and using backtracking to recur back from an incorrect path. Can anyone help me with why this doesn't give me the desired output (details below)?

Here's the problem statement

#include<bits/stdc++.h>
using namespace std;

void solve(vector<vector<int>> &ans, vector<int> &curr, int col, int n){
    if(col==n){
        ans.push_back(curr);
        return;
    }
    bool flag=false;
    
    for(int row=0; row<n; row++){
        if(col==0){
            curr.push_back(row);
            solve(ans, curr, col+1, n);
            curr.pop_back();
        }
        else{
            for(int i=0; i<curr.size(); i++){
                if((curr[i] == row) || (abs(row-curr[i]) == (col-i))){
                    flag=true;
                    break;
                }
            }
            if(flag)
                continue;
            curr.push_back(row);
            solve(ans, curr, col+1, n);
            curr.pop_back();
        }
    }
}

int main()
 {
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<vector<int>> ans;
        vector<int> curr;
        solve(ans, curr, 0, n);
        for (int i = 0; i < ans.size(); i++) {
            cout << "[";
            for (int j = 0; j < ans[i].size(); j++) 
                cout << ans[i][j]+1 << " "; 
            cout << "]";
        }
        cout << endl;
    }
    return 0;
}

A sample input would look like:

2
1
4

and the corresponding output would be:

[1 ]
[2 4 1 3 ] [3 1 4 2 ]

The compiler gives me an output (for my code):

[1 ]

Answer 1

The bool flag variable (used to check if placing a queen at (row, col) would intersect with any existing queens in curr) is currently being re-used across rows.

So, if you place the line bool flag=false; just above for(int i=0; i<curr.size(); i++){, it should produce the correct output for your test case.

Other notes:

1. It might be easier to create a separate function bool does_intersect(const vector<int>& cur, int row, int col) to check the queen intersection condition so that the bool flag variable isn't needed.
2. The if(col==0){ condition can be removed since it doesn't do anything that the else part cannot already handle.

Answer 2

This is a pretty simple way to solve the problem of the N-Queens using backtracking:

#include <bits/stdc++.h>
using namespace std;

int m[20][20];
bool ended = false;

void print(int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout<<(m[i][j] == -1? "O" : "-")<<" ";
        }
        cout<<endl;
    }
}

void fill(int val, int row, int col, int n){
    int d = 1;
    for(int i = col + 1; i < n; i++, d++){
        m[row][i] += val;
        if(row - d >= 0) m[row - d][i] += val;
        if(row + d < n)  m[row + d][i] += val;
    }
}

void solve(int n, int col = 0){
    if(ended) return;        
    if(col == n){ print(n); ended = true; return; }
    
    for(int i = 0; i < n; i++){
        if(m[i][col] == 0){
            m[i][col] = -1;
            fill(1, i, col, n);
            solve(n, col + 1);
            m[i][col] = 0;
            fill(-1, i, col, n);
        }
    }
}

int main(){
    memset(m, 0, sizeof(m));
    solve(8);                 //dimension of board    
    return 0;
}

The idea is to always look forward. Place a queen in a slot that is 0 in the matrix. After that, add 1 in all slots where she can move to. When you return from the backtracking, subtract 1 from the same slots you just added and continue trying.

Answer 3

This solution passes LeetCode's online judge for N Queens problem, and uses three flags to solve the problem:

#include <string>
#include <vector>

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> possibilities;
        std::vector<std::string> n_queens(n, std::string(n, '.'));
        std::vector<int> flag_col(n, 1);
        std::vector<int> flag_diag_a(2 * n - 1, 1);
        std::vector<int> flag_diag_b(2 * n - 1, 1);
        solveNQueens(possibilities, n_queens, flag_col, flag_diag_a, flag_diag_b, 0, n);
        return possibilities;
    }

private:
    void solveNQueens(std::vector<std::vector<std::string>>& possibilities,
                      std::vector<std::string>& n_queens,
                      std::vector<int>& flag_col, std::vector<int>& flag_diag_a, std::vector<int>& flag_diag_b,
                      int row, int& n) {
        if (row == n) {
            possibilities.push_back(n_queens);
            return;
        }

        for (int col = 0; col != n; col++) {
            if (flag_col[col] && flag_diag_a[row + col] && flag_diag_b[n - 1 + col - row]) {
                flag_col[col] = flag_diag_a[row + col] = flag_diag_b[n - 1 + col - row] = 0;
                n_queens[row][col] = 'Q';
                solveNQueens(possibilities, n_queens, flag_col, flag_diag_a, flag_diag_b, row + 1, n);
                n_queens[row][col] = '.';
                flag_col[col] = flag_diag_a[row + col] = flag_diag_b[n - 1 + col - row] = 1;
            }
        }
    }
};

For interview, you should not probably use:

#include<bits/stdc++.h>
using namespace std;

and make sure to write clean codes.

---

N Queens is a low frequency interview question. There are much better questions to be asked in the interviews (such as Number of Islands), probably you would not get N Queens. But, it's good to practice.