回溯法解题思路:
- 针对所给问题，定义问题的解空间；
- 确定易于搜索的解空间结构；
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继 续探测，直到找到解或者走完所有路径为止。就这一点，回溯和所谓的DFS（深度优先搜索）是一样的。那现在的关键是，怎么实现搜索呢？回溯既然一般使用递 归来实现，那个这个递归调用该如何来写呢？我现在的理解就是，进行回溯搜索都会有一系列的步骤，每一步都会进行一些查找。而每一步的情况除了输入会不一样 之外，其他的情况都是一致的。这就刚好满足了递归调用的需求。通过把递归结束的条件设置到搜索的最后一步，就可以借用递归的特性来回溯了。因 为合法的递归调用总是要回到它的上一层调用的，那么在回溯搜索中，回到上一层调用就是回到了前一个步骤。当在当前步骤找不到一种符合条件情况时，那么后续 情况也就不用考虑了，所以就让递归调用返回上一层（也就是回到前一个步骤）找一个以前没有尝试过的情况继续进行。当然有时候为了能够正常的进行继续搜索， 需要恢复以前的调用环境。
public class Queue { //数组下标表示所在的行，数值代表所在的列 // 因此此时所有皇后不可能在同一行 private static final int COL=8; private static final int ROW=8; private static int[] arr = new int[ROW]; public static void main(String[] args) { queue(); } public static int queue() { int count = 0; int i = 0; while (true) { if (arr[i] < COL) { //判断该行的皇后是否和前行的皇后冲突 if (isConflict(arr, i)) { //如果冲突尝试下一个位置 arr[i]++; continue; } if (i >= COL-1) { //如果已经到最后一行，即找到一个解，计数器加1，并打印输出 count++; print(count); //继续尝试下一个位置 arr[COL-1]++; continue; } //没有冲突尝试下一行 i++; continue; } else { //皇后已近超出棋盘范围，将该行皇后复位 arr[i] = 0; //回退到上一行 i--; //运行结束 if (i < 0) { return count; } //尝试上一行皇后的下一个位置 arr[i]++; continue; } } } private static void init() { for (int i = 0; i < ROW; i++) { arr[i] = 0; } } //判断是否冲突，发生冲突的条件是： //1):两个皇后处于同一列即arr[i]==arr[j] //2):两个皇后位置的斜率的绝对值为1.即Math.abs(arr[i]-arr[j])==Math.abs(i-j); private static boolean isConflict(int arr[], int i) { for (int j = 0; j < i; j++) { if (arr[j] == arr[i] || Math.abs(arr[i] - arr[j]) == Math.abs(i - j)) return true; } return false; } private static void print(int count) { System.out.println("----------------" + count + "------------------"); for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (arr[i] == j) { System.out.print("Q "); } else { System.out.print("* "); } } System.out.println(); } System.out.println("------------------------------------"); }}