LeetCode 51.N-Queens

51.N-Queens(N皇后)

题目：　

　　n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

　　给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

　　每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

　　示例:

　　输入: 4
　　输出: [
　　 [".Q..",  // 解法 1
　　  "...Q",
　　  "Q...",
　　  "..Q."],

　　 ["..Q.",  // 解法 2
　　  "Q...",
　　  "...Q",
 　　 ".Q.."]
　　]
　　解释: 4 皇后问题存在两个不同的解法。

思路：

　　

　　这题的思路和之前的N皇后II一样，都是运用回溯法，只是输出较难设置，还有一个重点，是其中存放答案的res，需要在每次计算前clear一下，要不然就无法ac。

　　N皇后II（https://www.cnblogs.com/blogxjc/p/10890322.html）。

代码：

    private static boolean col[];
    private static boolean line1[];
    private static boolean line2[];
    private static int answer[];
    private static List<List<String>> res = new LinkedList<>();
    
    public static List<List<String>> solveNQueens(int n) 
    {
        col = new boolean[n];
        line1 = new boolean[2 * n - 1];
        line2 = new boolean[2 * n - 1];
        answer = new int [n];
        res.clear();
        putQueen(n, 0);  
        return res;
    }
    
    private static void putQueen(int n, int index) 
    {
        if (index == n) 
        {
            List<String> item = new ArrayList<String>();
            for(int i = 0; i<answer.length; i++)
            {
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j<answer.length; j++)
                {
                    if(answer[i] != j)
                        sb.append('.');
                    else
                        sb.append('Q');
                }
                item.add(sb.toString());
            }
            res.add(item);
        }
            
      
        for (int i = 0; i < n; i++) 
        {
            if (!col[i] && !line1[i - index + n - 1] && !line2[i + index]) 
            {
                answer[index] = i;
                col[i] = true;
                line1[i - index + n - 1] = true;
                line2[i + index] = true;

                col[i] = false;
                line1[i - index + n - 1] = false;
                line2[i + index] = false;
            }
        }
    }