# Queens2.java

Below is the syntax highlighted version of Queens2.java from §2.3 Recursion.

```/******************************************************************************
*  Compilation:  javac Queens2.java
*  Execution:    java Queens2 n
*
*  Solve the n queens problem by enumerating all n! permutations,
*  pruning off useless branches. Solves n = 30 in a reasonable amount
*  of time.
*
*  % java Queens2 3
*
*  % java Queens2 4
*  * * Q *
*  Q * * *
*  * * * Q
*  * Q * *
*
******************************************************************************/

public class Queens2 {

/***************************************************************************
* Prints n-by-n placement of queens in ASCII.
***************************************************************************/
public static void printQueens(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i] == j) StdOut.print("Q ");
else           StdOut.print("* ");
}
StdOut.println();
}
StdOut.println();
}

/***************************************************************************
* Solve the n queens problem by brute force.
***************************************************************************/
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

// try all n! permutations, but prune useless ones
public static void enumerate(int[] a, boolean[] diag1, boolean[] diag2, int k) {
int n = a.length;

// found one, so print out and stop
if (k == 0) {
printQueens(a);
// System.exit(0);
}

for (int i = 0; i < k; i++) {
swap(a, i, k-1);
int j = k-1;

// if placement of new queen is ok, then enumerate
if (!diag1[j + a[j]] && !diag2[n + j - a[j]]) {
diag1[j + a[j]] = true;
diag2[n + j - a[j]] = true;
enumerate(a, diag1, diag2, k-1);
diag1[j + a[j]] = false;
diag2[n + j - a[j]] = false;
}
swap(a, i, k-1);
}
}

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int[] a         = new int[n];         // a[i] = row of queen in ith column
boolean[] diag1 = new boolean[2*n];   // is ith top diagonal occupied?
boolean[] diag2 = new boolean[2*n];   // is ith bottom diagonal occupied?
for (int i = 0; i < n; i++)
a[i] = i;
enumerate(a, diag1, diag2, n);
}

}
```