[LeetCode] 52. N-Queens II

Follow up for N-Queens problem.

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

Subscribe to see which companies asked this question

public class Solution {
    
    private boolean checkValid(int[][] board, int n, int x, int y){
        // check valid of a board placement.
        for(int i = 0; i < n; ++i){
            if(1 == board[i][y])
                return false;
            if(1 == board[x][i])
                return false;
            int off = y - i;
            if(x - off >= 0 && x - off < n && 1 == board[x - off][i])
                return false;
            if(x + off >= 0 && x + off < n && 1 == board[x + off][i])
                return false;
        }
        return true;
    }
    
    private void recordRes(int[][] board, int n, List> res){
        
        List sol = new ArrayList();
        for(int i = 0; i < n; ++i){
        StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; ++j){
                if(1 == board[i][j]){
                    sb.append('Q');
                }
                else{
                    sb.append('.');
                }
            }
        sol.add(sb.toString());
        }
        res.add(sol);
        return;
    }
    
    private void solveNQueensAux(int[][] board, int n, int col, List> res){
         for(int i = 0; i < n; ++i){
            if(checkValid(board, n, i, col)){
                /*
                board[i][col] = 1;
                if(col == n-1){
                    // record res
                    recordRes(board, n, res);
                    // Error: forgot to set the board back before return. Result in only one solution. 
                    board[i][col] = 0;
                    // there is only one solution for the last column.
                    return;
                }
                else{
                    solveNQueensAux(board, n, col+1, res);
                }
                board[i][col] = 0;
                */
                if(col == n-1){
                    board[i][col] = 1;
                    recordRes(board, n, res);
                    board[i][col] = 0;
                    return;
                }
                else{
                    // surrounding set and unset operation with recursive call is always a better idea.
                    board[i][col] = 1;
                    solveNQueensAux(board, n, col+1, res);
                    board[i][col] = 0;
                }
           
            }
         }
         
         return;
        
    }
    
    public int totalNQueens(int n) {
        List> res = new ArrayList>();
        if(0 == n)
            return 0;
        
        int[][] board = new int[n][n];
        
        solveNQueensAux(board, n, 0, res);
        
        return res.size();
       
    }
    
}