Leetcode : N-Queens
Diffculty：Hard

N皇后問(wèn)題，對(duì)八皇后問(wèn)題的擴(kuò)展，典型的回溯法算法題。
具體八皇后問(wèn)題可以參考八皇后問(wèn)題詳解(四種解法)

LeetCode 這道題的擴(kuò)展在于，不只是擴(kuò)展到N皇后的情形，還要求把每一個(gè)結(jié)果都返回。

由于棋盤(pán)是對(duì)稱(chēng)的，那么我們只需要求第一個(gè)皇后為起點(diǎn)，在棋盤(pán)左邊的結(jié)果，那么對(duì)于中軸線(xiàn)對(duì)稱(chēng)以后，一定有一個(gè)在右邊對(duì)稱(chēng)的結(jié)果。（此處要判斷N的奇偶性）
具體做法：
1）我們可以建立一個(gè)二維數(shù)組，0表示未占用，1表示占用。
2）然后以y軸逐層向下找可以放皇后的位置，每到一層，就把x從0~len 找一遍。
3）checkPosition方法，只需要找左上，上，和右上 即可。（因?yàn)槭菑纳贤抡椅恢玫?，下面的找到的一定是滿(mǎn)足上面已放置皇后的情況。）

下面上代碼：

// 4ms - beats 91.99%
// 這里一定要注意奇偶判斷，對(duì)于奇數(shù)情況，要對(duì)中間的那個(gè)位置在找一遍結(jié)果，并且image=false
public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[][] cheese = new int[n][n];
        for(int i=0; i<n/2; i++){
            backtrack(cheese, result, 0, i, true);
        }
        if(n%2 == 1){
            backtrack(cheese, result, 0, n/2, false);
        }
        return result;
    }

// image 表示是否對(duì)找到的結(jié)果進(jìn)行鏡像翻轉(zhuǎn)。
private static void backtrack(int[][] cheese, List<List<String>> result, int y, int x, boolean image){
        cheese[y][x] = 1;
        if(y == cheese.length-1){
            addResult(cheese, result, image);
        }else{
            for(int i=0; i<cheese[0].length; i++){
                if(checkPosition(cheese, y+1, i)){
                    backtrack(cheese, result, y+1, i, image);
                }
            }
        }
        cheese[y][x] = 0;
    }


private static void addResult(int[][] cheese, List<List<String>> result, boolean image){
        List<String> list = new ArrayList<>(cheese.length);
        List<String> imageList = null;
        if(image){
            imageList = new ArrayList<>(cheese.length);
        }
        for(int i=0; i<cheese.length; i++){
            StringBuilder bu = new StringBuilder();
            for(int j=0; j<cheese[0].length; j++){
                if(cheese[i][j] == 1){
                    bu.append("Q");
                }else{
                    bu.append(".");
                }
            }
            list.add(bu.toString());
            if(image){
                imageList.add(bu.reverse().toString());
            }
        }
        result.add(list);
        if(image){
            result.add(imageList);
        }
    }

private static boolean checkPosition(int[][] cheese, int y, int x){
        int left=x, right=x;
        int len = cheese[0].length;
        boolean leftCheck, rightCheck, upCheck, result;
        for(int i=y-1; i>=0; i--){
            left -= 1;
            right +=1;
            leftCheck = left<0 ? true : cheese[i][left]==0;
            rightCheck = right>=len ? true : cheese[i][right]==0;
            upCheck = cheese[i][x]==0;
            result = leftCheck && rightCheck && upCheck;
            if(!result){
                return false;
            }
        }
        return true;
    }