N Queens

An elegant implementation of N Queens in Java by Robert Sedgewick (Author of Algorithms in Java)

/*************************************************************************
*
*  Last updated: Wed Apr 4 07:07:00 EDT 2007.
*  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 <= 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 < 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 < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) System.out.print("Q ");
else           System.out.print("* ");
}
System.out.println();
}
System.out.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 < 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);
}

}
page revision: 2, last edited: 15 Jul 2008 20:26