title: N Queens in C++ using vectors
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>This is core of the code that I have come up with : </p>
  
  <pre><code>void n_queens(int n)
  {
    vector&lt;int&gt; queens = vector&lt;int&gt;();
    backtrack(queens,0,n);
  }
  
  void backtrack(vector&lt;int&gt;&amp; 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&lt;int&gt; candidates = vector&lt;int&gt;();
      if(construct_candidates(queens,current_row,N,candidates))
      {
        for(int i=0; i &lt; 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&lt;int&gt;&amp; queens, int row, int N, vector&lt;int&gt;&amp; candidates)
  {
    // Returns false if there are no possible candidates, we must follow a different
    // branch if this so happens
    for(int i=0; i&lt;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() &gt; 0;
  }
  </code></pre>
  
  <p>It doesn't print anything for any input that I give it. I tried running it through <code>gdb</code> but with no success, I think that is because there is a problem with my fundamental understanding of backtracking.</p>
  
  <p>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.</p>
  
  <p>The entire compilable source code is :</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;cmath&gt;
  
  using namespace std;
  
  // The method prototypes
  void n_queens(int n);
  void backtrack(vector&lt;int&gt;&amp;, int current_row, int N);
  bool construct_candidates(const vector&lt;int&gt;&amp;, int row, int N, vector&lt;int&gt;&amp;);
  bool is_safe_square(const vector&lt;int&gt;&amp;, int row, int col, int N);
  bool is_solution(const vector&lt;int&gt;&amp;, int N);
  void print_solution(const vector&lt;int&gt;&amp;, int N);
  
  int main()
  {
    int n;
    cin&gt;&gt;n;
    n_queens(n);
    return 0;
  }
  
  void n_queens(int n)
  {
    vector&lt;int&gt; queens = vector&lt;int&gt;();
    backtrack(queens,0,n);
  }
  
  void backtrack(vector&lt;int&gt;&amp; 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&lt;int&gt; candidates = vector&lt;int&gt;();
      if(construct_candidates(queens,current_row,N,candidates))
      {
        for(int i=0; i &lt; 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&lt;int&gt;&amp; queens, int row, int N, vector&lt;int&gt;&amp; candidates)
  {
    // Returns false if there are no possible candidates, we must follow a different
    // branch if this so happens
    for(int i=0; i&lt;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() &gt; 0;
  }
  
  bool is_safe_square(const vector&lt;int&gt;&amp; queens, int row, int col, int N)
  {
    for(int i=0; i&lt;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&lt;int&gt;&amp; queens, int N)
  {
    return queens.size() == N;
  }
  
  void print_solution(const vector&lt;int&gt;&amp; queens, int N)
  {
    for(int i=0; i&lt;N; ++i)
    {
      for(int j=0; j&lt;N; ++j)
      {
        if(queens[i] == j){ cout&lt;&lt;'Q'; }
        else { cout&lt;&lt;'_'; }
      }
      cout&lt;&lt;endl;
    }
  }
  </code></pre>