33. N-Queens

N-Queues
国际象棋的皇后是可以向8个方向走的
所以在同一列（1）， 同一行（2），同一条斜线（3）上是不能出现两个皇后的
因为我们在同一列（1）不会出现两个皇后
所以我们可以通过一个一位数组纪录每一列的Q在哪一行
下标（index）为第几列，值为第几行
这也是一个DFS在我们放下第一个Q后
我们需要以第一个Q的位置为依据判断下一个Q的摆放位置

Is it a Valid Queen
判断依据 即另外两个条件：

1. 不在 同一行（2）（新的Q的值（数）不会与之前数组内的值（列数）相同）
2. 不在 同一条斜线（3）（新的Q的值与列数差（斜线）不会与之前数组内的相同）

public class Solution {
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    public List<List<String>> solveNQueens(int n) {
        // write your code here
        List<List<String>> res = new ArrayList<>();
       
        helper(n, 0, new int[n], res);
        return res;
    }
   
    private void helper(int n, int row, int[] columnForRow, List<List<String>> res) 
    { 
        if(row == n) 
        { 
            List<String> item = new ArrayList<>();; 
            for(int i=0;i<n;i++) 
            { 
                StringBuilder strRow = new StringBuilder(); 
                for(int j=0;j<n;j++) 
                { 
                    if(columnForRow[i]==j) 
                        strRow.append('Q'); 
                    else 
                        strRow.append('.'); 
                } 
                item.add(strRow.toString()); 
            } 
            res.add(item); 
            return; 
        } 
        for(int i=0;i<n;i++) 
        { 
            columnForRow[row] = i; 
            if(check(row,columnForRow)) 
            { 
                helper(n,row+1,columnForRow,res); 
            } 
        } 
    } 
    private boolean check(int row, int[] columnForRow) 
    { 
        for(int i=0;i<row;i++) 
        { 
            if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==row-i) 
                return false; 
        } 
        return true; 
    } 
}