title: Java NQueens Recursion and Enumeration Logic Explanation
body: <p>I am doing some practice exercises with recursion and came across the nQueens problem <a href="http://introcs.cs.princeton.edu/java/23recursion/Queens.java.html" rel="nofollow">here</a>.</p>
  
  <p>I am not sure whether I am misunderstanding what is happening with the recursion or not, but I don't understand how this code (below) is printing multiple solutions of the problem. </p>
  
  <p>For example, if I run the program with a 4 queen solution, it prints out:</p>
  
  <pre><code>* Q * * 
  * * * Q 
  Q * * * 
  * * Q * 
  
  * * Q * 
  Q * * * 
  * * * Q 
  * Q * * 
  </code></pre>
  
  <p>I am stepping through it too, and I still don't quite understand it.<br><br>
  Here is what I think is going on:
  <br>
  1. <strong>isConsistent</strong> is checking the logic/ whether it's safe to place a queen in the current spot or not<br>
  2. <strong>printQueens</strong> is printing the board<br>
  3. <strong>enumerate(int[] q, int n)</strong> is recursively placing the queens for ONE solution<br>
  4. (I would guess that) <strong>enumerate(int N)</strong> is what is enumerating through the multiple board solutions, but it is only called once. So, that can't be right. So, my next thought would be that it's just a method to call the recursive enumerate method. But then, that means that once the recursion is done finding the solution for the first board, it should stop. So, I'm back to my original question: </p>
  
  <p><em>How/where is it calculating multiple solutions for the board?</em></p>
  
  <p>I know it may be easy, but even with the debugger, I'm having trouble catching onto what is going on. If anyone could explain where it starts calculating the second solution for the board, I'd appreciate it.</p>
  
  <pre><code>/******************************************************************************
   *  Compilation:  javac Queens.java
   *  Execution:    java Queens N
   *  
   *  Solve the 8 queens problem using recursion and backtracing.
   *  Prints out all solutions.
   *
   *  Limitations: works for N &lt;= 25, but slows down considerably
   *  for larger N.
   *
   *  Remark: this program implicitly enumerates all N^N possible
   *  placements (instead of N!), but the backtracing prunes off
   *  most of them, so it's not necessarily worth the extra
   *  complication of enumerating only permutations.
   *
   *
   *  % java Queens 3
   *
   *  % java Queens 4
   *  * Q * * 
   *  * * * Q 
   *  Q * * * 
   *  * * Q * 
   *
   *  * * Q * 
   *  Q * * * 
   *  * * * Q 
   *  * Q * * 
   *
   *  % java Queens 8
   *  Q * * * * * * * 
   *  * * * * Q * * * 
   *  * * * * * * * Q 
   *  * * * * * Q * * 
   *  * * Q * * * * * 
   *  * * * * * * Q * 
   *  * Q * * * * * * 
   *  * * * Q * * * * 
   *
   *  ...
   *
   ******************************************************************************/
  
  public class Queens {
  
     /***************************************************************************
      * Return true if queen placement q[n] does not conflict with
      * other queens q[0] through q[n-1]
      ***************************************************************************/
      public static boolean isConsistent(int[] q, int n) {
          for (int i = 0; i &lt; n; i++) {
              if (q[i] == q[n])             return false;   // same column
              if ((q[i] - q[n]) == (n - i)) return false;   // same major diagonal
              if ((q[n] - q[i]) == (n - i)) return false;   // same minor diagonal
          }
          return true;
      }
  
     /***************************************************************************
      * Print out N-by-N placement of queens from permutation q in ASCII.
      ***************************************************************************/
      public static void printQueens(int[] q) {
          int N = q.length;
          for (int i = 0; i &lt; N; i++) {
              for (int j = 0; j &lt; N; j++) {
                  if (q[i] == j) StdOut.print("Q ");
                  else           StdOut.print("* ");
              }
              StdOut.println();
          }  
          StdOut.println();
      }
  
  
     /***************************************************************************
      *  Try all permutations using backtracking
      ***************************************************************************/
      public static void enumerate(int N) {
          int[] a = new int[N];
          enumerate(a, 0);
      }
  
      public static void enumerate(int[] q, int n) {
          int N = q.length;
          if (n == N) printQueens(q);
          else {
              for (int i = 0; i &lt; N; i++) {
                  q[n] = i;
                  if (isConsistent(q, n)) enumerate(q, n+1);
              }
          }
      }  
  
  
      public static void main(String[] args) {
          int N = Integer.parseInt(args[0]);
          enumerate(N);
      }
  
  }
  </code></pre>