Question9_9.java

import java.util.LinkedList;
import java.util.List;

/**
 * Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board
 * so that none of them share the same row, column or diagonal.
 * In this case, "diagonal" means all diagonals, not just the two that bisect the board.
 *  
 * Time  Complexity: O(n^2)
 * Space Complexity: O(n)
 */

public class Question9_9 {
    public List<int[]> arrangement(int n) {
        if (n <= 0) {
            return null;
        }
        
        List<int[]> arrangements = new LinkedList<int[]>();
        recArrangement(n, new int[n], 0, arrangements);
        
        return arrangements;
    }
    
    private void recArrangement(int n, int[] columns, int row, List<int[]> arrangements) {
        if (row >= n) {
            int[] arrangement = new int[n];
            System.arraycopy(columns, 0, arrangement, 0, n);
            arrangements.add(arrangement);
        }
        
        for (int col = 0; col < n; ++col) {
            if (isValidPos(col, row, columns)) {
                columns[row] = col;
                recArrangement(n, columns, row + 1, arrangements);
            }
        }
    }
    
    private boolean isValidPos(int col, int row, int[] columns) {
        // check row
        for (int i = 0; i < row; ++i) {
            if (columns[i] == col) {
                return false;
            }
        }
        
        // check diagonal
        for (int i = 0; i < row; ++i) {
            if (Math.abs(columns[i] - col) == (row - i)) {
                return false;
            }
        }
        
        return true;
    }
    

    
    public static void main(String[] args) {
        Question9_9 question9_9 = new Question9_9();
        List<int[]> arrangements = question9_9.arrangement(8);
        System.out.println(arrangements.size());
    }
}