回溯法解决n后问题

参考教材：算法设计与分析（第3版）王晓东编著清华大学出版社

问题的解空间

用回溯法解问题时，明确定义问题的解空间。问题的解空间至少应包含问题的一个（最优）解。
定义了问题的解空间后，还应将解空间很好地组织起来，使得能用回溯法方便地搜索整个解空间。通常将解空间组织成树或图的形式。

回溯法的基本思想

确定了解空间的组织结构后，回溯法从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始节点成为活节点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点成为新的活节点，并成为当前扩展节点。如果在当前扩展节处不能再向纵深方向移动，则当前扩展节点就成为死节点。此时，应往回移动（回溯）至最近的活节点处，并使这个活节点成为当前扩展节点。回溯法以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中已无活节点时为止。

剪枝函数

回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高搜索效率。其一是用语数函数在扩展节点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。

回溯法解题的3个步骤

针对所给问题，定义问题的解空间。
确定易于搜索的解空间结构。
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

n后问题

在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

算法

递归回溯

代码：

public class NQueen1 {
static int n; // 皇后个数
static int[] x; // 当前解
static long sum; // 当前找到的可行方案数

public static long nQueen(int nn) {
        n = nn;
        sum = 0;
        x = new int[n + 1];
for (int i = 0; i <= n; i++)
            x[i] = 0;
        backtrack(1);
return sum;
    }

private static boolean place(int k) {// 判断皇后是否能放入k列
for (int j = 1; j < k; j++) { // 与前k-1个皇后的位置比较
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k])) // 同对角线或同列
return false;
        }
return true;
    }

private static void backtrack(int t) {
if (t > n) {
            sum++;
for (int i = 1; i <= n; i++)
// 输出当前方案
                System.out.printf("%5d", x[i]);
            System.out.println();
        } else
for (int i = 1; i <= n; i++) {
                x[t] = i; // 把第t个皇后依次放入n个格子，看是否可行
if (place(t)) // 可行就继续放第t+1个皇后
                    backtrack(t + 1);
            }
    }

// 测试
public static void main(String[] args) {
        System.out.println("5皇后问题方案可行数为:" + nQueen(5));
    }
}

非递归迭代回溯

代码：

public class NQueen2 {// n后问题的递归回溯算法
static int n; // 皇后个数
static int[] x; // 当前解
static long sum; // 当前找到的可行方案数

public static long nQueen(int nn) {
        n = nn;
        sum = 0;
        x = new int[n + 1];
for (int i = 0; i <= n; i++)
            x[i] = 0;
        backtrack();
return sum;
    }

private static boolean place(int k) {
for (int j = 1; j < k; j++) {
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
        }
return true;
    }

private static void backtrack() {
        x[1] = 0;
int k = 1;
while (k > 0) {
            x[k] += 1;
while ((x[k] <= n) && !(place(k)))
                x[k] += 1;
if (x[k] <= n) {
if (k == n) {
                    sum++;
for (int i = 1; i <= n; i++)
// 输出当前方案
                        System.out.printf("%5d", x[i]);
                    System.out.println();
                } else {
                    k++;
                    x[k] = 0;
                }
            } else
                k--;
        }
    }

// 测试
public static void main(String[] args) {
        System.out.println("5皇后问题方案可行数为:" + nQueen(5));
    }
}

输出结果（两种算法肯定是一样的）：

    1    3    5    2    4
    1    4    2    5    3
    2    4    1    3    5
    2    5    3    1    4
    3    1    4    2    5
    3    5    2    4    1
    4    1    3    5    2
    4    2    5    3    1
    5    2    4    1    3
    5    3    1    4    2
5皇后问题方案可行数为:10

秒客网