LeetCode0025.N皇后

52.N皇后II

描述

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

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

实例

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

题解

贡献一个超时算法

写的时候有个大坑，就是对于二维数组而已，直接copy函数不管用，因为int[][]使用该函数之后，是创建了一个新的一维数组，里面的内容是原数组中每一维度的数组地址，最后指向的还是原始元素。另外这个版本的代码没有办法是相同放法但不同顺序也会计入结果，因此需要返回之前除以n!

public static int totalNQueens(int n) {
    Stack<int[][]> stack = new Stack<>();
    int[] counter = new int[1];
    getAllPoss(n,stack,1,counter);
    for (int i = n; i > 1; i--) {
        counter[0] /= i;
    }
    return counter[0];
}

public static void getAllPoss(int n, Stack<int[][]> stack, int index, int[] counter){
    if (index > n){
        counter[0]++;
        stack.pop();
        return;
    }

    int[][] nowState;
    int[][] lastState = new int[n][n];
    if (stack.empty()){
        nowState = new int[n][n];
    } else {
        lastState = stack.pop();
        stack.push(lastState);
        nowState = copy(lastState);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (nowState[i][j] == 0){
                changeState(nowState,n,i,j);
                stack.push(nowState);
                getAllPoss(n,stack,index+1,counter);
                nowState = copy(lastState);
            }
        }
    }
    if (!stack.empty()){
        stack.pop();
    }

}

public static void changeState(int[][] state,int n,int y,int x){
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == y)
                state[i][j] = 1;
            if (j == x)
                state[i][j] = 1;
            if ((i-y) == (j-x))
                state[i][j] = 1;
            if ((i-y) == (x-j))
                state[i][j] = 1;
        }
    }
    state[y][x] = 2;
}

public static int[][] copy(int[][] A){
    int[][] B = new int[A.length][A[0].length];

    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A[0].length; j++) {
            B[i][j] = A[i][j];
        }
    }
    return B;
}

考虑另一种方法。正常的思考方式是新建一个n*n的数组，根据其值是0或者1判断放置的位置。由于N皇后的限制，每行每列只能放置一颗。因此可以使用一个大小为n数组进行描述，每一个元素的值代表这一行中皇后的位置。

//index记录当前应该寻找第几列的可放置位置，state记录时用n+1个维度，就不用0开始转成1开始
public static void getAllPoss(int n, int index,Stack<int[]> stack,int[] lastState, int[] counter){
    if (index > n){
        counter[0]++;
        stack.pop();
        return;
    }
    int[] nowState = lastState.clone();
    int[] canPutPlace = canPut(n,index,nowState);

    for (int i = 1; i < n+1; i++) {
        if (canPutPlace[i] == 1){
            nowState[index] = i;//相当于复位+赋新值
            stack.push(nowState);
            getAllPoss(n,index+1,stack,nowState,counter);
        }
    }
    if (!stack.empty())
        stack.pop();
}

public static int[] canPut(int n,int index,int[] state){
    int[] canPutPlace = new int[n+1];
    for (int i = 1; i < n+1; i++) {
        canPutPlace[i] = 1;
    }
    for (int i = 1; i < index; i++) {
        int place = state[i];
        canPutPlace[place] = 0;

        place = state[i]+i-index;
        if ((place >= 1) && (place <= n))//避免在角落时，数组越界的情况
            canPutPlace[place] = 0;

        place = state[i]-i+index;
        if ((place >= 1) && (place <= n))//避免在角落时，数组越界的情况
            canPutPlace[place] = 0;
    }

    return canPutPlace;
}