回溯法求解n皇后问题——递归实现

/** * 回溯法求解n皇后问题——递归实现 * * 过程描述 * 从第n(1, 2, ...)行开始，遍历当前行，找出当前行中所有可放置皇后的位置，并将其当作各个节点 * 若当前行中存在可放置皇后的位置，则根据"深度优先"的原则，从当前行中第一个节点开始继续遍历下一行， * 当行号大于皇后个数时，遍历结束，输出遍历结果 * * 若当前行中不存在可放置皇后的位置，则跳转至位于上一行的父节点，从父节点开始继续寻找可放置皇后的位置(回溯)； * */ public class N_Queens { private int n; // 皇后个数 private int[] x; // 当前解 private long sum; // 当前已找到的可行方案数 public N_Queens() { this.sum = 0; // 初始化方案数为0，当回溯到可行方案的时候，就自增1 this.n = 8; // 初始化皇后个数 this.x = new int[n + 1]; // x[i]表示皇后i放在棋盘的第i行的第x[i]列 } /** * * @param k——棋盘行号，棋盘中的第k行——t * @param j——棋盘列号，棋盘中的第j列 * ******************************************************************************* * * x[j]——皇后j放在第j行的x[j]列 * ******************************************************************************* * * x[j] == x[k]——两个皇后处在同一列 * * j = 1, x[j] = 2 * k = 2, x[k] = 2 * ******************************************************************************* * (Math.abs(k - j) == Math.abs(x[j] - x[k])——两个皇后处在同一行或同一斜线或同一反斜线 * * 两个皇后处在同一行 * j = 2, x[j] = 2 * k = 3, x[k] = 3 * * 两个皇后处在同一斜线 * j = 1, x[j] = 1 * k = 2, x[k] = 2 * * 两个皇后处在同一反斜线 * j = 2, x[j] = 1 * k = 1, x[k] = 2 * ******************************************************************************* * * @return */ public boolean place(int k) { for (int j = 1; j < k; j++) { // 这个主要是筛选符合皇后条件的解，因为皇后可以攻击与之同一行、同一列或同一斜线上的棋子 // 如果是与之同一行同一列或同一斜线上的棋子，返回false; // 如果不是与之同一行、同一列或同一斜线上的棋子，返回true; if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k])) { return false; } } return true; } /** * 回溯，完成主要的求解操作 * * @param t——回溯到的行数(棋盘行号：棋盘中的第t行) * @param n——皇后数目(棋盘行数，棋盘列数) */ public void backTrace(int t) { // 当t>n时，算法搜索到叶节点，得到一个新的n皇后互不攻击放置方案，方案数加1 // 当t<=n时，当前扩展的结点Z是解空间中的内部结点，该节点有x[i]=1, 2, ..., n共n个子结点， // 对于当前扩展结点Z的每一个子结点，由place()方法检测其可行性， // 并以"深度优先"的方式递归地对可行子树搜索，或剪去不可行子树 if (t > n) { sum++; // 方案数自增1 System.out.println("方案 " + sum); print(x); System.out.println("\n----------------\n"); } else { for (int i = 1; i <= n; i++) { //当t=1时，i=1, 2, 3, 4——即遍历t行的i列，检查是否有符合条件的(t, i)组合 x[t] = i; // 检查结点是否符合条件 if (place(t)) { backTrace(t + 1); // 递归调用 } } } } /** * 打印可行放置方案 * * @param a */ public void print(int[] a) { for (int i = 1; i < a.length; i++) { System.out.print("皇后" + i + "(" + i + ", " + a[i] + ") "); } } public static void main(String[] args) { N_Queens em = new N_Queens(); em.backTrace(1); // 从第1行开始回溯 System.out.println("详细方案如上所示，" + "可行个数为:" + em.sum); } }