第一题：只求摆法有多少种
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 存了其中一种摆法，例如：
用：'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); }
力扣题目链接：
