[LeetCode] 51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

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 List> solveNQueens(int n) {
        List> res = new ArrayList>();
        if(0 == n)
            return res;
        
        int[][] board = new int[n][n];
        
        solveNQueensAux(board, n, 0, res);
        
        return res;
       
    }
}