Queens.java

/*************************************************************************
 *  Compilation:  javac Queens.java
 *  Execution:    java Queens 8
 *  
 *  Solve the 8 queens problem. Prints out all solutions.
 *
 *  Sample execution:
 *
 *      % 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 of permutation a[] has no two
    * queens on the same diagonal.
    ***********************************************************************/
    public static boolean checkDiagonals(int[] a) {
        int N = a.length;
        boolean[] diag1 = new boolean[2*N];
        boolean[] diag2 = new boolean[2*N];
        for (int i = 0; i < N; i++) {
            if (diag1[i + a[i]]) return false;
            else diag1[i + a[i]] = true;
            if (diag2[N + i - a[i]]) return false;
            else diag2[N + i - a[i]] = true;
        }
        return true;
    }

   /***********************************************************************
    * Print out 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) System.out.print("Q ");
                else           System.out.print("* ");
            }
            System.out.println();
        }  
        System.out.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
    public static void enumerate(int[] a, int n) {
        if (n == 0) {
            if (checkDiagonals(a)) printQueens(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            enumerate(a, n-1);
            swap(a, i, n-1);
        }
    }  


    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = i;
        enumerate(a, N);
    }

}