每日一题：n queues

题目：在n阶棋盘上放n个皇后，皇后在横竖斜都不能重复。
分析：这是一道典型的回溯算法
算法：
1>如果当前的格子是可以放皇后执行2>不能放执行3>
2>往下一行找。
3>往下一列去找，如果这一行都没有，那么回溯到上一行找上一行的放皇后的下一列。

    
        public static List<List<String>> solveNQueens(int n) {
    
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = -1000;
            }
            int i = 0;
            int j = 0;
            List<List<String>> res = new ArrayList<>();
            while (i < n) {
                while (j < n) {
                    if (valid(a, i, j)) {
                        a[i] = j;
                        // 每次下一个都从第0列开始搜索。
                        j = 0;
                        break;
                    } else {
                        j++;
                    }
                }
    
                if (a[i] == -1000) {
                    if (i == 0) {
                        break;
                    } else {
                        --i;
                        j = a[i] + 1;
                        a[i] = -1000;
                        continue;
                    }
    
                }
                if (i == n - 1) {
                    res.add(transfer(a));
                    j = a[i] + 1;
                    a[i] = -1000;
                    continue;
                }
                ++i;
    
            }
            return res;
        }
    
        private static boolean valid(int[] a, int i, int j) {
        
            for (int k = 0; k < a.length; k++) {
                if (a[k] == j || Math.abs(a[k] - j) == Math.abs(k - i)) {
                    return false;
                }
            }
            return true;
        }
    
        private static List<String> transfer(int[] a) {
            int len = a.length;
            List<String> res = new ArrayList<>(len);
            StringBuffer sb = new StringBuffer(len);
            String mod = "";
            for (int i = 0; i < len - 1; i++) {
                sb.append('.');
            }
            mod = sb.toString();
            for (int i = 0; i < len; i++) {
                res.add(sb.insert(a[i], 'Q').toString());
                sb.setLength(0);
                sb.append(mod);
            }
            return res;
        }