题目求n皇后问题的所有解。n个皇后摆放在n*n的棋盘格中使得横、竖和两个对角线方向均不会出现两个皇后。思路1采用剪枝减少不必要的计算2 快速判断不合法的情况a、竖向b、对角线1右上→左下c、对角线2左上→右下b、对角线1共有 2*n-1 个对角线其中同一对角线上 ij 的值相等因此可用 ij 来标识当前的对角线c、对角线2共有 2*n-1 个对角线其中同一对角线上 i-j 的值相等因此可用 i-jn-1 来标识当前的对角线代码如下package com.haobi; import java.util.ArrayList; import java.util.List; public class N_Queues { // res数组用来存储所有结果 private static ListString res new ArrayList(); // 记录纵方向上是否冲突 private static boolean col[]; // 记录对角线1方向上是否冲突 private static boolean dir1[]; // 记录对角线2方向上是否冲突 private static boolean dir2[]; public static void main(String[] args) { int Q 4; ListString list solveNQueens(Q); int countA 0; int countB 0; for(String s: list) { countA; if(countA % Q 0) { System.out.println(s); }else { System.out.print(s ); } //每一种结果输出完毕 if(countA % (Q*Q) 0) { countB; System.out.println(第countB种方案输出完毕); } } } public static ListString solveNQueens(int n){ res.clear(); //对col进行初始化 col new boolean[n]; //对dir1进行初始化 dir1 new boolean[2*n-1]; //对dir2进行初始化 dir2 new boolean[2*n-1]; //定义动态数组row,将结果存在动态数组中 ArrayListInteger row new ArrayList(); putQueue(n, 0, row); return res; } /** * 尝试在n皇后的问题中摆放第index行的皇后位置 * param n n皇后 * param index 第index行 * param row 结果存在row[]中 */ private static void putQueue(int n, int index, ArrayListInteger row) { if(index n) { String[][] board new String[n][n]; for(int i0;in;i) { board[i][row.get(i)] Q; } for(int i0;in;i) { for(int j0;jn;j) { if(board[i][j] null) { board[i][j] -; } res.add(board[i][j]); } } return; } for(int i0;in;i) { //尝试将第index行 if(!col[i] !dir1[indexi] !dir2[index-in-1]) {//如果均不冲突 row.add(i);//第index行元素摆放在第i个位置 col[i] true;//该列不能再有元素 dir1[indexi] true;//对角线1不能再有元素 dir2[index-in-1] true;//对角线2不能再有元素 //递归 putQueue(n, index1, row); //回溯 col[i] false; dir1[indexi] false; dir2[index-in-1] false; row.remove(row.size()-1); } } return; } }程序输出结果如下- Q - -- - - QQ - - -- - Q -第1种方案输出完毕- - Q -Q - - -- - - Q- Q - -第2种方案输出完毕