51. N-Queens Leetcode Java

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.."]
]

Solution:

Recursion: Recursively try to place the queeen in each row, only one queen in each row, use a Integer array column[] to track the column of the queen in each row. Determine if the current trial is valid by check column[], from row 1 to current row, no two rows can have the same column (vertically), j-k!=col[k]-i(k is the previous row number, i is the current number ,j is the current column number, col[k] is the column number of the queen in row k; diagonal check) j-k!=i-col[k](anti-diagonal check) and by default, horizontally is always valid because each row can only have one queen.

base case/ terminating case:

if(row>n){...}
Recursion step: 
current trial: column[row-1]=j;
recursion to next row: if(isValid(column,j,row-1)) helper(res,row+1,n,column);
backtrack to current row; j++; assign column[row-1] to next trial value; 

 public List<String[]> solveNQueens(int n) {  
    List<String[]> res= new ArrayList<String[]>();  
    if(n==0) return res;  
    helper(res,1,n,new int[n]);  
    return res;  
   }  
   public void helper(List<String[]> res, int row, int n, int[] column){  
     if(row>n){  
       String[] items=new String[n];  
       for(int i=0;i<n;i++){  
         StringBuilder sb=new StringBuilder();  
         for(int j=0;j<n;j++){  
           if(column[i]!=j) sb.append('.');  
           else sb.append('Q');  
         }  
         items[i]=sb.toString();  
       }  
       res.add(items);  
       return;  
     }  
     for(int j=0;j<n;j++){  
       column[row-1]=j;  
       if(isValid(column,j,row-1)) helper(res,row+1,n,column);  
     }  
   }  
   public boolean isValid(int[] column,int j, int i){  
     for(int k=0;k<i;k++){  
       if(column[k]==j || j-i== column[k]-k || j+i==column[k]+k) return false;  
     }  
     return true;  
   }