Recursion/Backtracking/Java

8 queens problem solution in Java:

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

public class NQueens {


    ///////////////////////////////////////////////////
    // main
    //
    public static void main(String[] args) {
        SolutionSaver s = new SolutionSaver();
        Board b = new Board(8);
        explore(b,0);
		  System.out.printf("Found %d solutions\n ", SolutionSaver.nSolutions() );
    }
    //
    ///////////////////////////////////////////////////


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

        if(col >= b.size() ) {

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

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

		} else {

            // The legalRows() method is a little bit of magic.
            // It returns an array of valid rows on which to place the col^th queen.
            for(Integer row : b.legalRows(col) ) { // important question: is this called each time in the loop?
                                                   // (do i need to make a copy outside the loop?)
                b.place(row,col);
                explore(b,col+1);
                b.remove(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.

    int board_size;                 // Size of our problem

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

    public int size(){
        return this.board_size;
    }

    public String toString() {
        return Arrays.toString(this.queens);
    }

    public void place(int row, int col) {
        if( col < this.queens.length && row < this.occupiedrows.length ) {
            this.queens[col] = row;
            this.occupiedrows[row] = 1;
        }
    }

    public void remove(int row, int col) {
        if( col < this.queens.length && row < this.occupiedrows.length ) {
            this.queens[col] = 0;
            this.occupiedrows[row] = 0;
        }
    }

    public LinkedList<Integer> legalRows( int col ) {

        LinkedList<Integer> legalList = new LinkedList<Integer>();

        // 1. Mark invalid squares on diagonals 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[size()];

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

            // We're trying to place the next queen on col.
            // Find which squares on col are on the diagonal of this queen,
            // and mark them as imposisble.

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

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

        }

        for (int row = 0; row < size(); row++) {

            // If this row is legal, add it to the list
            boolean legal = diag[row]==0 && this.occupiedrows[row]==0;
            if(legal) {
                legalList.add(row);
            }

        }

        return legalList;
    }
}


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();
    }
}