如何避免 N Rooks 问题中 n = 8 的 stackoverflow 错误

Question

我想解决 N Rooks 问题 N x N board 使用递归最大 N = 8。我的代码适用于 N = 2, 3, 4、5、6、7。但是当 N = 8 它给出了很多可能的结果，从 1 的第一行开始 0 0 0 0 0 0 0 然后给出 Whosebug 错误 ，然后检查从 0 的第一行开始的其他可能结果0 0 0.

我知道像 斐波那契数列、阶乘等一般递归，我可以追踪它们。然后我遇到了一种新的递归形式，称为回溯递归。然后我开始学习这种递归形式背后的逻辑，并阅读了一些伪代码算法。实际上，在我看来，这种递归形式比普通递归更难构造。

public class NRooks {
/**
 * In this code r = which row, c = which column.
 * lastY method just returns column c of last placed rook in
 * a given row r in order to remove it.
 * row.length, col.length, board.length have no special meaning. They all
 * equal to the dimension of board N.
 * main() method always initiates first row(r = 0). Therefore in main()
 * method r remains 0 and c changes as you can see in putRook(0, i). 
 * So solve() method always begins from second row(r = 1).
 */

private static int found = 0;
private static int[][] board;
private static int[] row;
private static int[] col;

public static void putRook(int r, int c) {
    board[r][c] = 1;
    row[r]  = 1;
    col[c]  = 1;
}

public static void removeRook(int r, int c) {
    board[r][c] = 0;
    row[r]  = 0;
    col[c]  = 0;
}

public static boolean isValid(int r, int c) {
    if (row[r] == 0 && col[c] == 0) return true;
    return false;
}

public static void showBoard() {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board.length; c++) {
            System.out.print(board[r][c] + " ");
        }
        System.out.println();
    }
    System.out.println();
}

public static int lastY(int r) {
    for (int j = 0; j < board.length; j++) {
        if (board[r][j] == 1) return j;
    }
    return -1;
}


public static boolean solve(int r, int c) {
    int last;

    if (r == 0) return false;

    if (r == col.length) {
        found++;
        /**
         * When I dont include below printline statement my code 
         * works fine until N = 7 then gives SO error.
         * But When I include this print statement in order
         * to print number of results my code works fine until
         * N = 6 then gives SO error
         */
        //System.out.println("Found: " + found);
        showBoard();
        r--;
        last = lastY(r);
        removeRook(r, last);
        c = last + 1;
    }

    for (int j = c; j < row.length; j++) {
        if (isValid(r, j)) {
            putRook(r, j);
            return solve(r + 1, 0);
        }
    }

    last = lastY(r - 1);
    removeRook(r - 1, last);
    return solve(r - 1, last + 1);
}

public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    board = new int[n][n];
    row = new int[n];
    col = new int[n];

    for (int i = 0; i < row.length; i++) {
        boolean finished; // not important
        putRook(0, i);
        finished = solve(1, 0);
        if (finished) System.out.println("============"); // ignore this too
    }
}
}

Whosebug 指向包含对 solve() 方法的递归调用的行。

注意： 我只知道C 类java 的语法和基本的数据抽象。我用我的Java这个水平写了这段代码。

我想自己解决这个问题和N皇后问题。因为在数学和算法上，这些问题的解决方案太多了。我现在对高级Java数据抽象不感兴趣。
我只想对上面的代码片段提出一些建议，例如

您的回溯算法效率不高。（如此直截了当）
你需要使用一些Java数据抽象的东西来有效地解决这个问题。
您需要使用另一种递归形式，例如 尾递归（我也听说过。）
.....

Answer 1

我无法测试你的代码，因为我没有你的一些方法，但是 int j = c 应该是 int j = r 吗？

for (int j = c; j < row.length; j++) {
    if (isValid(row, col, r, j)) {
        putRook(b, row, col, r, j);
        return solve(b, row, col, r + 1, 0);
    }
}

在此行中，您将 0 传递给 c，然后在 for 循环条件中声明 j=c，因此 j < row.length 每次都为真。我不知道你的 isValid() 是什么。

   return solve(b, row, col, r + 1, 0);

编辑：我现在看到在上面的 if 块中声明了 c，但是如果那个 if 块没有被执行，这之后应该是一个无限循环。也许检查 r == col.length 是否正确执行。

Answer 2

出现 Stack Overflow 错误的主要问题是递归的结构方式。在main方法中调用solve的那一刻，它一直递归得越来越深；事实上，它的所有调用都形成了一个包含数千次调用的深链。对于 n=7，有 3193 个嵌套调用（我添加了一个计数器来检查这个）。对于 n=8，它会在我的机器上溢出堆栈之前执行大约 5k 次递归调用 - 我猜默认情况下堆栈大小相当小。

因此，为了使其适用于更高的 n 值，您需要以一种不会将所有递归调用作为单个链执行的方式来重构递归。我可以争辩说您当前的解决方案并不是真正的回溯，因为它实际上从未回溯过。让我用一个更简单的问题来说明回溯意味着什么。假设您想以编程方式打印长度为 n=3（“000”到“111”）的所有二进制字符串，而不依赖于知道 n 的值。对此的实现可能是这样的：

def build_binary_string(current_prefix, chars_left):
  if chars_left == 0:
    print current_prefix
    return
  build_binary_string(current_prefix + 'a', chars_left - 1)
  build_binary_string(current_prefix + 'b', chars_left - 1)

build_binary_string("", 3)

有趣的事情（回溯！）发生在使用参数 ("00", 1) 调用 build_binary_string 的那一刻：

build_binary_string("000", 0) 被调用，立即打印“000”和 returns
我们回到 build_binary_string("00", 1) 函数调用，即将执行 build_binary_string(current_prefix + 'b', chars_left - 1)
build_binary_string("001", 0) 被调用，立即打印“001”和 returns

控制流从 build_binary_string("000", 0) 返回到 build_binary_string("00", 1) 并选择进行另一个函数调用的那一点是回溯。注意递归的深度从来没有超过3.

如何避免 N Rooks 问题中 n = 8 的 stackoverflow 错误

How to avoid stackoverflow error for n = 8 in N Rooks problem

java

algorithm

recursion

backtracking