LeetCode 51. N-Queens

Leetcode : N-Queens
Diffculty：Hard

N皇后问题，对八皇后问题的扩展，典型的回溯法算法题。
具体八皇后问题可以参考八皇后问题详解(四种解法)

LeetCode 这道题的扩展在于，不只是扩展到N皇后的情形，还要求把每一个结果都返回。

由于棋盘是对称的，那么我们只需要求第一个皇后为起点，在棋盘左边的结果，那么对于中轴线对称以后，一定有一个在右边对称的结果。（此处要判断N的奇偶性）
具体做法：
1）我们可以建立一个二维数组，0表示未占用，1表示占用。
2）然后以y轴逐层向下找可以放皇后的位置，每到一层，就把x从0~len 找一遍。
3）checkPosition方法，只需要找左上，上，和右上 即可。（因为是从上往下找位置的，下面的找到的一定是满足上面已放置皇后的情况。）

下面上代码：

// 4ms - beats 91.99%
// 这里一定要注意奇偶判断，对于奇数情况，要对中间的那个位置在找一遍结果，并且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 表示是否对找到的结果进行镜像翻转。
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;
    }