阅读 17

LeetCodeN皇后

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

上图为 8 皇后问题的一种解法。

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

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

示例:

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

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

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/n-…

解题思路

如果第i行的皇后在第j列,第s行皇后在第t列,即X[i] = j和X[s] = t,则只要i-j = s-t或者i+j = s+t,说明两个皇后在同一对角线上。 对两个等式进行变换后,得到结论:只要|i-s| = |j-t|(即i-s = X[i]-X[s]),则皇后在同一对角线上。对于所有的主对角线有 行号 + 列号 = 常数,对于所有的次对角线有 行号 - 列号 = 常数.

  1. 初始化信息,调用回溯函数
  2. 回溯函数,传入行值,循环列,判断能不能放皇后。不能跳出循环继续,能就将坐标记录(行,列)。继续判断是否满足所有条件,满足加入结果集,不满足继续调用回溯函数,当回溯函数走完,并且不符合条件,就删除(剪枝)刚刚加入的坐标。重新寻找符合条件的。
  3. 判断能否放皇后,从列,主对角线,副对角线是否都不存在。
  4. 加入数组,如果是符合的queens[]=[1,3,0,2],解读第一行第2列(0,1)后面是一样的。将能攻击的放入列,主对角线,副对角线。
  5. 如果有符合的结果就拼接字符串,加入结果集。
  6. 删除不符合的坐标。
int rows[];
// "hill" diagonals
int hills[];
// "dale" diagonals
int dales[];
int n;
// output
List<List<String>> outputs = new ArrayList();
// queens positions
int queens[];
// 3
public boolean isNotUnderAttack(int row, int col) {
    int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
    return (res == 0) ? true : false;
}
// 4
public void placeQueen(int row, int col) {
    queens[row] = col;
    rows[col] = 1;
    hills[row - col + 2 * n] = 1;  // "hill" diagonals
    dales[row + col] = 1;   //"dale" diagonals
}
// 6
public void removeQueen(int row, int col) {
    queens[row] = 0;
    rows[col] = 0;
    hills[row - col + 2 * n] = 0;
    dales[row + col] = 0;
}
// 5
public void addSolution() {
    List<String> solutions = new ArrayList<String>();
    for (int i = 0; i < n; ++i) {
        int col = queens[i];
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < col; ++j) sb.append(".");
        sb.append("Q");
        for(int j = 0; j < n - col - 1; ++j) sb.append(".");
        solutions.add(sb.toString());
    }
    outputs.add(solutions);
}
// 2
public void backtrack(int row) {
    for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            // if n queens are already placed
            if (row + 1 == n) addSolution();
                // if not proceed to place the rest
            else backtrack(row + 1);
            // backtrack
            removeQueen(row, col);
        }
    }
}
// 1
public List<List<String>> solveNQueens(int n) {
    this.n = n;
    rows = new int[n];
    hills = new int[4 * n - 1];
    dales = new int[2 * n - 1];
    queens = new int[n];

    backtrack(0);
    return outputs;
}
复制代码
关注下面的标签,发现更多相似文章
评论