代码随想录算法训练营第三十天|51. N皇后

|51. N皇后

public List<List<String>> solveNQueens(int n) {List<List<String>> res = new ArrayList<>();return null;}void backtracking1(int n, int row, int[] columns) {// 是否在所有n行里都摆放好了皇后?if (row == n) {count++;// 找到了新的摆放方法return;}// 尝试着将皇后放置在当前行中的每一列for (int col = 0; col < n; col++) {columns[row] = col;// 检查是否合法，如果合法就继续到下一行if (check(row, col, columns)) {backtracking1(n, row + 1, columns);}
// 如果不合法，就不要把皇后放在这列中 (回溯)columns[row] = -1;}}boolean check1(int row, int col, int[] columns) {for (int r = 0; r < row; r++) {if (columns[r] == col ||row - r == Math.abs(columns[r] - col)) {return false;}}return true;}public List<List<String>> solveNQueens(int n) {int[] queueMax = new int[n];List<List<String>> lists = new ArrayList<>();check(0, n, queueMax, lists);return lists;}public void check(int n, int max, int[] queueMax, List<List<String>> lists) {if (n == max) {print(queueMax, lists);return;}for (int i = 0; i < max; i++) {queueMax[n] = i;if (judge(n, queueMax)) {check(n + 1, max, queueMax, lists);}}}public void print(int[] queueMax, List<List<String>> lists) {List<String> stringList = new ArrayList<>();for (int i = 0; i < queueMax.length; i++) {String res = "";for (int j = 0; j < queueMax.length; j++) {if (j == queueMax[i]) {res = res.concat("Q");} else {res = res.concat(".");}}stringList.add(res);}lists.add(stringList);}public boolean judge(int n, int[] queueMax) {for (int i = 0; i < n; i++) {if (queueMax[i] == queueMax[n] || Math.abs(n - i) == Math.abs(queueMax[n] - queueMax[i])) {return false;}}return true;}