52. N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solution

public class Solution {
    int count =0;
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i=0; i< n;i++){
            for(int j=0; j< n; j++){
                board[i][j] = '.';
            }
        }

        bt(board, 0, n);
        return count;
    }


    private void bt(char[][] board, int row, int n){
        if(row == n){
            count++;
            return;
        }

        for(int col=0; col < n; col++){
            if(isValid(board, row, col)){ // if is not valid, then there is no solution added.
                board[row][col] = 'Q';
                bt(board, row+1, n);
                board[row][col] = '.';
            }
        }

    }

    private boolean isValid(char[][] board, int row, int col){
        for(int i= row-1; i >=0; i--){
            if(board[i][col] == 'Q' )return false;
        }
        for(int i=row-1, j=col-1; i >=0 && j>=0; i--,j--){
            if(board[i][j] == 'Q') return false;
        }


        for(int i=row-1, j=col+1; i>=0 && j<board.length; i--,j++){
            if(board[i][j] == 'Q') return false;
        }

        return true;
    }
}

to improve solution, you don't need to save the entire board to get the result, you only need to remember the index of queens in each row.

public class Solution {
    int count =0;
    public int totalNQueens(int n) {
        int[] board = new int[n];
        for(int i=0; i< n;i++){
            board[i] = -1;
        }

        bt(board, 0, n);
        return count;
    }


    private void bt(int[] board, int row, int n){
        if(row == n){
            count++;
            return;
        }

        for(int col=0; col < n; col++){
            if(isValid(board, row, col)){ // if is not valid, then there is no solution added.
                board[row] = col;
                bt(board, row+1, n);
                board[row] = -1;
            }
        }

    }

    private boolean isValid(int[] board, int row, int col){
        for(int i= 0; i <row; i++){
            if(board[i] == col || Math.abs(row -i) == Math.abs(col - board[i]) ) return false;
        }

        return true;
    }
}