Excercise Your Coding Muscles

The Fabien Bergeret's solution looks pretty optimal to me. It uses a fail fast solution tree wich leaves are the solutions of the problem. My approach is similar but, having just read the Fork-Join article by Ricardo Zuastri, I tried to apply his lesson and build the algorithm in a parallel way. To accomplish that I had to rewrite the List so to avoid having to remove anything from it (or being forced to duplicate it). My solution is a reversed linked list where each successive element points back to its parent. It is both fast and memory efficient for our purpose (if you don't mind reading the list backwards).

The performances are really impacted by the outputting of data (using System.out.println()), so, commenting out the lines that actually performs the printing it seems that the parallel algorithm employs 60% of the time spent by the sinlge threaded algorithm so gaining a significant advantage (my test machine is equipped with 4 processors).

public class Solution {
    private AtomicInteger solutionNumber = new AtomicInteger(0);
    private Queue<String> output = new ConcurrentLinkedQueue<>();

    public static Solution findSolutions(final ForkJoinPool pool) {
        final Solution solution = new Solution();
        pool.invoke(new Step(solution));
        return solution;
    }

    public void addSolution(final Sequence sequence) {
        solutionNumber.incrementAndGet();
        // in a multithreaded environment System.out.println() blocks
        // so it must be avoided
        output.add(sequence.toString());
    }

    public int getSolutionNumber() {
        return solutionNumber.get();
    }

    public String getOutput() {
        final StringBuilder buf = new StringBuilder();
        for (String str: output) {
            buf.append(str).append('\n');
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        Solution solution = findSolutions(new ForkJoinPool());
        System.out.println(solution.getOutput());
        System.out.println("found " + solution.getSolutionNumber() + " solutions.");
    }
}

public class Step extends RecursiveAction {
    private static final long serialVersionUID = 1L;
    private final Sequence sequence;
    private final Solution solution;

    public Step(final Solution solution) {
        this(solution, new Sequence());
    }

    private Step(final Solution solution, final Sequence sequence) {
        this.solution = solution;
        this.sequence = sequence;
    }

    @Override
    protected void compute() {
        final int column = sequence.size();
        if (column == 8) {
            solution.addSolution(sequence);
        } else {
            final List<Step> solutions = new ArrayList<>(8);
            for (int row = 0; row < 8; row++) {
                final Queen queen = new Queen(row, column);
                if (sequence.isFriendlyWith(queen)) {
                    solutions.add(new Step(solution, sequence.add(queen)));
                }
            }
            invokeAll(solutions);
        }
    }

} 

/**
 * It's a reversed linked list with the characteristic that a new element
 * is always added to an existing list so avoiding having to copy the list.
 *
 * @author fra
 */
public class Sequence implements Iterable<Queen> {
    private final int size;
    private final Entry head;

    private static class Entry {
        final private Queen queen;
        final private Entry next;

        public Entry(final Queen queen, final Entry next) {
            this.queen = queen;
            this.next = next;
        }
    }

    public Sequence() {
        this(null, 0);
    }

    private Sequence(final Entry entry, final int size) {
        this.head = entry;
        this.size = size;
    }

    /** Returns a new list with the new element on top */
    public Sequence add(final Queen queen) {
        final Entry entry = new Entry(queen, head);
        return new Sequence(entry, size + 1);
    }

    public boolean isFriendlyWith(final Queen queen) {
        for (final Queen q: this) {
            if (q.attack(queen)) {
                return false;
            }
        }
        return true;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        final StringBuilder buf = new StringBuilder();
        for (final Queen q: this) {
            buf.append(q).append(' ');
        }
        return buf.toString();
    }

    /** The list is iterated in reverse order */
    @Override
    public Iterator<Queen> iterator() {
        return new Iterator<Queen>() {
            private Entry current = new Entry(null, head);

            @Override
            public boolean hasNext() {
                return current != null && current.next != null;
            }

            @Override
            public Queen next() {
                current = current.next;
                return current.queen;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("Not supported yet.");
            }
        };
    }

}

public class Queen {
    private final int row, column, diagonalLeft, diagonalRight;

    public Queen(final int row, final int column) {
        this.row = row;
        this.column = column;
        this.diagonalLeft = row + column;
        this.diagonalRight = row - column;
    }

    public boolean attack(final Queen queen) {
        return this.row == queen.row ||
                this.column == queen.column ||
                this.diagonalLeft == queen.diagonalLeft ||
                this.diagonalRight == queen.diagonalRight;
    }

    public int getColumn() {
        return column;
    }

    public int getRow() {
        return row;
    }

    @Override
    public String toString() {
        return "" + ((char)(row + '1')) + ((char)(column + 'a'));
    }
}

EDIT: sorry I forgot to use AtomicInteger instead of int in Solution because of the concurrency in accessing it.

EDIT 2: sorry again, in my performance test I didn't print out anything thus the big speed difference.

EDIT 3: (This isn't really my day), I forgot to add a class: Step.