Solving the N queens problem using Java. Implementing a verb-based approach utilizing fast built-in data structures.

NQueens.java

import java.util.LinkedList;
import java.util.Arrays;

public class NQueens {

    public static final int SIZE = 11;

    ///////////////////////////////////////////////////
    // main
    //
    public static void main(String[] args) {
        long start = System.nanoTime();
        SolutionSaver s = new SolutionSaver();
        Board b = new Board(SIZE);
        explore(b,0);
        long end = System.nanoTime();
        long duration = end - start;
        System.out.printf("Found %d solutions\n ", SolutionSaver.nSolutions() );
        System.out.printf("Elapsed time %03f s\n ", (duration/1E9) );
    }
    //
    ///////////////////////////////////////////////////


    /// Placing queens, column-by-column; place the queen in column col.
    public static void explore(Board b, int col) {

        if(col >= SIZE ) {

            // We have reached the end.
            // No conflicts so far means no conflicts period.

            // Save solution in a static class, no instantiation overhead
            SolutionSaver.saveSolution( b.toString() );

		} else {

            int[] attacked = b.getDiagAttacked(col);
            int[] occupied = b.getOccupied(col);

            for(int row=0; row<SIZE; row++) {
                if(occupied[row]!=1 && attacked[row]!=1) {
                    b.choose(row,col);
                    explore(b,col+1);
                    b.unchoose(row,col);
                }
            }
        }// done with base/recursive cases
    }

}

class Board {

    int[] queens;                   // Array to store where queens have been placed.
                                    // The queens array has a length of board_size.
                                    // Each element stores an integer between 1 and N.
                                    // That indicates the row/column.

    int[] occupiedrows;             // Array to mark occupied rows.
                                    // This is how we check for horizontal attacks.

    public static int board_size;

    public Board(int size) {
        this.board_size = size;
        this.queens = new int[size];
        this.occupiedrows = new int[size];
    }

    /**
     * Get String representation of queen positions.
     * This prints 8 numbers, corresponding to 8 columns.
     * Each number is an integer, 1..(board_size-1), indicating
     * the row of the queen on that particular column.
     * All queens on first row would be 0 0 0 0 0 0 0 0
     */
    public String toString() {
        return Arrays.toString(this.queens);
    }

    /// Make the choice of putting a queen on row, col
    public void choose(int row, int col) {
        if( col < this.queens.length && row < this.occupiedrows.length ) {
            this.queens[col] = row;
            this.occupiedrows[row] = 1;
        }
    }

    /// Unmake the choice of putting a queen on row, col
    public void unchoose(int row, int col) {
        if( col < this.queens.length && row < this.occupiedrows.length ) {
            this.queens[col] = 0;
            this.occupiedrows[row] = 0;
        }
    }

    /// Get a list of occupied rows
    public int[] getOccupied(int col) {
        return this.occupiedrows;
    }

    /// Get a list of attacked diagonals
    public int[] getDiagAttacked( int col ) {

        // 1. Mark invalid squares on diagoonals of already-placed queens
        //
        // 2. For this column, loop over each row where it's legal to place a queen,
        //    and run backtracking on that choice. Then unmake the choice and keep going.

        // Store invalid rows on other queens' diagonals
        int[] diag = new int[this.board_size];

        // Loop over all of the queens already placed (col-1)
        for(int k = 0; k <= (col-1); k++ ) {

            // We're gonig to place the next queen on col.
            // Find which squares are on diagonals of queen k,
            // and mark them as impossible.

            // Lower right diag
            int ix1 = this.queens[k] + col - k;
            if(ix1 >= 0 && ix1 < this.board_size ) {
                diag[ix1] = 1;
            }

            // Upper right diag
            int ix2 = this.queens[k] - col + k;
            if(ix2 >= 0 && ix2 < this.board_size ) {
                diag[ix2] = 1;
            }

        }

        return diag;
    }
}


class SolutionSaver {
    private static LinkedList<String> solutions;

    public SolutionSaver() {
        SolutionSaver.solutions = new LinkedList<String>();
    }

    public static void saveSolution(String serialized) {
        SolutionSaver.solutions.add(serialized);
    }

    public static void printSolutions() {
        int c = 0;
        for( String sol : solutions ) {
            System.out.printf("Solution %d: %s \n", c, sol);
        }
    }
    public static int nSolutions() {
        return solutions.size();
    }
}

prof_java.sh

#!/bin/sh
#
# Profile the N queens problem using Java Iteractive Profiler and HPROF
# JIP: http://jiprof.sourceforge.net/
# HPROF: https://docs.oracle.com/javase/7/docs/technotes/samples/hprof.html
#
# Also see http://charlesreid1.com/wiki/Java/Profiling
#
# JIP (TLDR): download JIP source and look for profile/profile.jar
# HPROF (TLDR): built in to Java

export PATH2JIP="${HOME}/Downloads/jip-src-1.2"

for N in 8 9 10 11 12 13 14
do

    echo "**************************************"
    echo "Profiling $N queens problem with Java..."

    # Update N
    /usr/local/bin/sed -i "s/SIZE = [0-9]\{1,\}/SIZE = ${N}/g" NQueens.java

    # Compile
    javac NQueens.java

    echo " - - - - - - - - - - - - - - - - - - - - -"
    echo "Profiling $N queens with JIP..."

    java -javaagent:${PATH2JIP}/profile/profile.jar NQueens

    mv profile.txt profile_${N}queens.txt
    tail -n30 profile_${N}queens.txt

    echo " - - - - - - - - - - - - - - - - - - - - -"
    echo "Profiling $N queens with HPROF..."

    #java -agentlib:hprof NQueens
    java -agentlib:hprof=verbose=n NQueens
    #java -agentlib:hprof=cpu=samples NQueens

    mv java.hprof.txt hprof_${N}queens.txt
    tail -n30 hprof_${N}queens.txt
done

run_nqueens_java.sh

#!/bin/sh

export OUT="timeout_nqueens_java.out"
touch ${OUT}
cat /dev/null > ${OUT}

for N in 8 9 10 11 12 13 14 15
do
    echo "**************************************" >> ${OUT}
    echo "Running $N queens problem with Java..." >> ${OUT}

    # Update N
    /usr/local/bin/sed -i "s/SIZE = [0-9]\{1,\}/SIZE = ${N}/g" NQueens.java

    # Compile
    javac Nqueens.java

    # Semicolon is important here
    echo "Running..."
    { time java NQueens >> ${OUT}; } 2>> ${OUT}
    echo "Done."

    echo "" >> ${OUT}

done

timeout_nqueens_java.out

**************************************
Running 8 queens problem with Java...
Found 92 solutions
 Elapsed time 0.003628 s

real	0m0.241s
user	0m0.158s
sys	0m0.052s

**************************************
Running 9 queens problem with Java...
Found 352 solutions
 Elapsed time 0.006709 s

real	0m0.201s
user	0m0.169s
sys	0m0.052s

**************************************
Running 10 queens problem with Java...
Found 724 solutions
 Elapsed time 0.017473 s

real	0m0.232s
user	0m0.197s
sys	0m0.054s

**************************************
Running 11 queens problem with Java...
Found 2680 solutions
 Elapsed time 0.061291 s

real	0m0.282s
user	0m0.270s
sys	0m0.068s

**************************************
Running 12 queens problem with Java...
Found 14200 solutions
 Elapsed time 0.240463 s

real	0m0.440s
user	0m0.480s
sys	0m0.088s

**************************************
Running 13 queens problem with Java...
Found 73712 solutions
 Elapsed time 1.113491 s

real	0m1.336s
user	0m1.328s
sys	0m0.163s

**************************************
Running 14 queens problem with Java...
Found 365596 solutions
 Elapsed time 6.557336 s

real	0m6.816s
user	0m6.977s
sys	0m0.452s

**************************************
Running 15 queens problem with Java...
Found 2279184 solutions
 Elapsed time 42.619426 s

real	0m42.937s
user	0m46.697s
sys	0m0.923s