题目链接：n-queens
import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.For example,There exist two distinct solutions to the 4-queens puzzle:[ [".Q..", // Solution 1"…Q","Q…","..Q."],["..Q.", // Solution 2"Q…","…Q",".Q.."]] * */public class NQueens {//9 / 9 test cases passed.//Status: Accepted//Runtime: 217 ms//Submitted: 0 minutes ago//回溯法//时间复杂度O(n!) 空间复杂度O(n)public int[] columns;//存储已放置的皇后占据的列， 0 未占， 1已占public int[] main_diag;//存储已放置的皇后占据的主对角线， 0 未占， 1已占public int[] anti_diag;//存储已放置的皇后占据的副对角线， 0 未占，， 1已占public String[] st_str;public List<String[]> nQueens = new ArrayList<String[]>();public void init(int n) {columns = new int[n];main_diag = new int[2 * n];anti_diag = new int[2 * n];Arrays.fill(columns, 0);Arrays.fill(main_diag, 0);Arrays.fill(anti_diag, 0);createString(n);}public void createString (int n) {st_str = new String[n];StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++) {sb.append(".");}for (int i = 0; i < n; i++) {sb.replace(i, i + 1, "Q");st_str[i] = sb.toString();sb.replace(i, i + 1, ".");}}public List<String[]> solveNQueens(int n) {//初始化各状态变量init(n);int[] C = new int[n];Arrays.fill(C, 0);dfs(C, 0);return nQueens;}public void dfs(int[] C, int row) {int N = C.length;//表示找到一个可行解if(row == N) {String[] nQueen = new String[N];for (int i = 0; i < N; i++) {nQueen[i] = st_str[C[i]];}nQueens.add(nQueen);return;}for (int i = 0; i < N; i++) {//如果不合法，这跳过当前循环if(!(columns[i] == 0&& main_diag[i + row] == 0&& anti_diag[N – i + row] == 0)) continue;//执行C[row] = i;columns[i] = 1;main_diag[i + row] = 1;anti_diag[N – i + row] = 1;dfs(C, row + 1);//撤销C[row] = 0;columns[i] = 0;main_diag[i + row] = 0;anti_diag[N – i + row] = 0;}}public static void main(String[] args) {NQueens queens = new NQueens();List<String[]> result = queens.solveNQueens(8);System.out.println(result.size());//for (int i = 0; i < result.size(); i++) {//for (int j = 0; j < result.get(i).length; j++) {//System.out.println(result.get(i)[j]);//}//System.out.println();//}}}
题目链接：n-queens-ii
import java.util.Arrays;/** * Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions. * */public class NQueensII {//9 / 9 test cases passed.//Status: Accepted//Runtime: 231 ms//Submitted: 0 minutes ago//回溯法//时间复杂度O(n!) 空间复杂度O(n)public int[] columns;//存储已放置的皇后占据的列， 0 未占， 1已占public int[] main_diag;//存储已放置的皇后占据的主对角线， 0 未占， 1已占public int[] anti_diag;//存储已放置的皇后占据的副对角线， 0 未占， 1已占public int total;public void init(int n) {columns = new int[n];main_diag = new int[2 * n];anti_diag = new int[2 * n];Arrays.fill(columns, 0);Arrays.fill(main_diag, 0);Arrays.fill(anti_diag, 0);total = 0;//计数}public int totalNQueens(int n) {//初始化各状态变量init(n);int[] C = new int[n];Arrays.fill(C, 0);dfs(C, 0);return total;}public void dfs(int[] C, int row) {int N = C.length;//表示找到一个可行解if(row == N) {total ++;return;}for (int i = 0; i < N; i++) {//如果不合法，这跳过当前循环if(!(columns[i] == 0&& main_diag[i + row] == 0&& anti_diag[N – i + row] == 0)) continue;//执行C[row] = i;columns[i] = 1;main_diag[i + row] = 1;anti_diag[N – i + row] = 1;dfs(C, row + 1);//撤销C[row] = 0;columns[i] = 0;main_diag[i + row] = 0;anti_diag[N – i + row] = 0;}}public static void main(String[] args) {NQueensII queens = new NQueensII();for (int i = 0; i < 16; i++) {System.out.println(i + "- 皇后有 " + queens.totalNQueens(i) + " 种解法");}}}//output//0- 皇后有 1 种解法//1- 皇后有 1 种解法//2- 皇后有 0 种解法//3- 皇后有 0 种解法//4- 皇后有 2 种解法//5- 皇后有 10 种解法//6- 皇后有 4 种解法//7- 皇后有 40 种解法//8- 皇后有 92 种解法//9- 皇后有 352 种解法//10- 皇后有 724 种解法//11- 皇后有 2680 种解法//12- 皇后有 14200 种解法//13- 皇后有 73712 种解法//14- 皇后有 365596 种解法//15- 皇后有 2279184 种解法
纵然走过那么多城市，对于未知的风景，还是好奇。
