N Queens in C++ using vectors

I'm having trouble understanding backtracking, I can conceptually understand that we make a move, then if no solutions can be found out of it we try the next solution. With this in mind I'm trying to solve the N Queens problem, I'm finding out all the possible candidates that can be placed in the next row and then trying them one by one, if a candidate doesn't yield a solution, I pop it off and go with the next one. This is core of the code that I have come up with : ``` void n_queens(int n) { vector<int> queens = vector<int>(); backtrack(queens,0,n); } void backtrack(vector<int>& queens, int current_row, int N) { // check if the configuration is solved if(is_solution(queens, N)) { print_solution(queens,N); } else { // construct a vector of valid candidates vector<int> candidates = vector<int>(); if(construct_candidates(queens,current_row,N,candidates)) { for(int i=0; i < candidates.size(); ++i) { // Push this in the partial solution and move further queens.push_back(candidates[i]); backtrack(queens,current_row + 1,N); // If no feasible solution was found then we ought to remove this and try the next one queens.pop_back(); } } } } bool construct_candidates(const vector<int>& queens, int row, int N, vector<int>& candidates) { // Returns false if there are no possible candidates, we must follow a different // branch if this so happens for(int i=0; i<N; ++i) { if(is_safe_square(queens,row,i,N)) { // Add a valid candidate, this can be done since we pass candidates by reference candidates.push_back(i); } } return candidates.size() > 0; } ``` It doesn't print anything for any input that I give it. I tried running it through `gdb` but with no success, I think that is because there is a problem with my fundamental understanding of backtracking. I have read up about backtracking in a couple of books and also an online tutorial and I still feel hazy, it'd be nice if someone could give me ideas to approach this and help me understand this slightly unintuitive concept. The entire compilable source code is : ``` #include <iostream> #include <vector> #include <cmath> using namespace std; // The method prototypes void n_queens(int n); void backtrack(vector<int>&, int current_row, int N); bool construct_candidates(const vector<int>&, int row, int N, vector<int>&); bool is_safe_square(const vector<int>&, int row, int col, int N); bool is_solution(const vector<int>&, int N); void print_solution(const vector<int>&, int N); int main() { int n; cin>>n; n_queens(n); return 0; } void n_queens(int n) { vector<int> queens = vector<int>(); backtrack(queens,0,n); } void backtrack(vector<int>& queens, int current_row, int N) { // check if the configuration is solved if(is_solution(queens, N)) { print_solution(queens,N); } else { // construct a vector of valid candidates vector<int> candidates = vector<int>(); if(construct_candidates(queens,current_row,N,candidates)) { for(int i=0; i < candidates.size(); ++i) { // Push this in the partial solution and move further queens.push_back(candidates[i]); backtrack(queens,current_row + 1,N); // If no feasible solution was found then we ought to remove this and try the next one queens.pop_back(); } } } } bool construct_candidates(const vector<int>& queens, int row, int N, vector<int>& candidates) { // Returns false if there are no possible candidates, we must follow a different // branch if this so happens for(int i=0; i<N; ++i) { if(is_safe_square(queens,row,i,N)) { // Add a valid candidate, this can be done since we pass candidates by reference candidates.push_back(i); } } return candidates.size() > 0; } bool is_safe_square(const vector<int>& queens, int row, int col, int N) { for(int i=0; i<queens.size(); ++i) { // case when the queens are already placed in the same row or column if(queens[i] == row || queens[i] == col) return false; // case when there is a diagonal threat // remember! y = mx + c for a diagonal m = 1 therefore |x2 - x1| = |y2 - y1| if(abs(i - row) == abs(queens[i] - col)) return false; } //Returns true when no unsafe square is found //handles the case when there are no queens on the board trivially return true; } bool is_solution(const vector<int>& queens, int N) { return queens.size() == N; } void print_solution(const vector<int>& queens, int N) { for(int i=0; i<N; ++i) { for(int j=0; j<N; ++j) { if(queens[i] == j){ cout<<'Q'; } else { cout<<'_'; } } cout<<endl; } } ```