带你轻松拿捏N皇后问题

简介: 要求任何两个皇后不同行、不同列,也不在同一 条斜线上

image.png


第一题:只求摆法有多少种


N皇后问题是指在N*N的棋盘上要摆N个皇后,


要求任何两个皇后不同行、不同列,也不在同一 条斜线上


给定一个整数 n,返回 n 皇后的摆法有多少种。


n=1,返回1


n=2或3,2皇后和3皇后问题无论怎么摆都不行,返回0


n=8,返回 92


public static int num(int n) {
    if (n < 1) return 0;
    int[] record = new int[n];  // 用于记录下过的地方, record[x] = y 表示在 x 行时下的是第 y 列
    return process(record, 0);
}
/**
 * @param record  之前下过的位置
 * @param x  当前来到 x 行
 * @return
 */
public static int process(int[] record, int x) {
    if (x == record.length) return 1;  // 如果 n 个皇后都走完,那么说明找到了一种方法
    int res = 0;
    //尝试把 x 行的皇后放到 y 列
    for (int y = 0; y < record.length; y++) {
        if (isVaild(record, x, y)) {
            record[x] = y;
            res += process(record, x + 1);
        }
    }
    return res;
}
/**
 * @param record
 * @param x 当前所在行
 * @param y 当前所在列
 * @return
 */
public static boolean isVaild(int[] record, int x, int y) {
    for (int i = 0; i < x; i++) {
        // 如果与之前摆过的皇后在同一列 || 在同一斜线上
        if (record[i] == y || Math.abs(i - x) == Math.abs(record[i] - y)) {
            return false;
        }
    }
    return true;
}


上面这题看着我的注释是非常好理解的,如果还是不理解,可以将4传入,通过调试的方式跟着代码走一遍那就会很清楚了。


第二题


这题相比于上题变化不大,就是不要结果有多少种,而是返回一个 List<List>


其中里面的 List 存了其中一种摆法,例如:


image.png


用:'Q''.' 分别代表了皇后和空位


因为在上一题中我们是有记录 成功摆完所有皇后时皇后位置的,所以我们只要把之前记录代码的地方给去掉 并且把 record 转换为需要的结果那样表达就行了


LinkedList<List<String>> ans = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
    if (n < 1) return null;
    int[] record = new int[n];
    process(record, 0);
    return ans;
}
public void process(int[] record, int x) {
    if (x == record.length) {
        //对皇后摆放的位置处理为题目要的结果
        handleResult(record);
        return;
    }
    for (int y = 0; y < record.length; y++) {
        if (isVaild(record, x, y)) {
            record[x] = y;
            process(record, x + 1);
        }
    }
}
public boolean isVaild(int[] record, int x, int y) {
    for (int i = 0; i < x; i++) {
        if (record[i] == y || Math.abs(i - x) == Math.abs(record[i] - y)) {
            return false;
        }
    }
    return true;
}
public void handleResult(int[] record) {
    ArrayList<String> list = new ArrayList<>();
    StringBuilder builder = new StringBuilder();
    int row = record.length;  // 行数和列数都为record.length
    int col = record.length;  // 这里分开写只是为了方便理解就用两参数表示
    for (int i = 0; i < col; i++) { //先把棋盘中一行的内容全设为 “.”
        builder.append(".");
    }
    for (int i = 0; i < row; i++) {  // 通过 record 把每行皇后对应位置设置为 "Q"
        StringBuilder tmp = new StringBuilder(builder);
        tmp.replace(record[i], record[i] + 1, "Q");
        list.add(tmp.toString());
    }
    ans.add(list);
}


力扣题目链接:


第一题:leetcode.cn/problems/n-…

第二题:leetcode.cn/problems/n-…

相关文章
|
8月前
|
算法刷题(二十二):宝石与石头
算法刷题(二十二):宝石与石头
79 0
|
8月前
|
【随想】每日两题Day.10(实则一题)
【随想】每日两题Day.10(实则一题)
41 0
|
8月前
【随想】每日两题Day.3(实则一题)
【随想】每日两题Day.3
37 0
|
8月前
|
【随想】每日两题Day.20(实则一题)
【随想】每日两题Day.20(实则一题)
46 0
|
8月前
【随想】每日两题Day.16(实则一题)
【随想】每日两题Day.16(实则一题)
48 0
|
8月前
【随想】每日两题Day.5 (实则一题)
【随想】每日两题Day.5
36 0
算法练习第五天——有效数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
算法练习第五天——有效数独
穿颜色成对的袜子,追最新的剧:这群coder正帮视障者移走身上的大山
穿颜色成对的袜子,追最新的剧:这群coder正帮视障者移走身上的大山
123 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等