时间戳

首页 > 解决方案 > 如何避免 N Rooks 问题中 n = 8 的 stackoverflow 错误

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

问题描述

我想使用最大N = 8的递归来解决N x N板上的N Rooks 问题。我的代码适用于N = 2 , 3 , 4 , 5 , 6 , 7。但是当N = 8它从1 0 0 0 0 0 0 0的第一行开始给出这么多可能的结果，然后在检查从0 1 0 0 0 0 0 0 0的第一行开始的其他可能结果之前给出stackoverflow 错误。

我知道一般递归，如fibonacci series，factorial等，我可以追踪它们。然后我遇到了一种新的递归形式，称为回溯递归。然后我开始学习这种递归形式背后的逻辑，并阅读了一些伪代码算法。实际上，这种形式的递归在我看来似乎比普通递归更难构建。

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
    }
}
}

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

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

我想自己解决这个问题和 N 个皇后问题。因为这些问题有很多解决方案，无论是数学上还是算法上。而且我现在对高级Java 数据抽象的东西不感兴趣。
我只想要一些关于我的代码片段的建议，例如

标签： javaalgorithmrecursionbacktracking

解决方案

出现 Stack Overflow 错误的主要问题是递归的结构方式。solve在方法中调用的时刻main，它不断地递归越来越深；事实上，它的所有调用都形成了一个数千次调用的深度链。对于 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)

build_binary_string有趣的事情（回溯！）发生在使用参数（“00”，1）调用的那一刻：

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

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

推荐阅读