N-Queens II

Return the total number of distinct solutions.

Solution:

Create an array stores number from 0 to n - 1. The index and value pairs represent for index row and value column on the chess board. We use depth first search to solve this problem in recursion first, then convert it into a non-recursive version.

Code:

class DataType {
    int row;
    int col;
    public  DataType(int inRow, int inCol) {
        row = inRow;
        col = inCol;
    }
}

class Solution {

    private int sum = 0;

    public int totalNQueens(int n) {
        //nQueensRecursive(n);
        nQueensIterative(n);
        return sum;
    }

    //iterative solution
    private void nQueensIterative(int n) {
        int[] placed = new int[n];
        Stack<DataType> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (isValid(placed, 0, i)) {
                stack.push(new DataType(0, i));
            }
        }
        while (!stack.empty()) {
            DataType cur = stack.pop();
            int row = cur.row;
            int col = cur.col;
            placed[row] = col;
            if (row + 1 >= n) {
                sum++;
                continue;
            }
            for (int i = 0; i < n; i++) {
                if (isValid(placed, row + 1, i)) {
                    stack.push(new DataType(row + 1, i));
                }
            }
        }
    }

    //recursive solution
    private void nQueensRecursive(int n) {
        int[] placed = new int[n];
        placeQueen(placed, 0);
    }

    private void placeQueen(int[] placed, int row) {
        int n = placed.length;
        if (row >= n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(placed, row, i)) {
                placed[row] = i;
                placeQueen(placed, row + 1);
            }
        }
    }

    //since the we placed the queens from top to buttom, there are only three direction need to be checked. For example: 
    /*
    *   i, y - 1    |   y   |   i, y + 1
    *               | x, y  |
    *
    *   other scenarios will be checked by next x, y
    */
    private boolean isValid(int[] placed, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (col == placed[i]) {
                return false;
            }
            if (row - i == Math.abs(col - placed[i])) {
                return false;
            }
        }
        return true;
    }
};