递归错误

Question

对于一个项目，我必须编写一个程序来递归地解决所有 92 个解决方案中的 8 Queens Puzzle。在递归地使 "main" 方法运行之前，该程序工作正常。奇怪的是它在与 "main" 方法的循环（包括在 toString 方法中）无关的点抛出错误。我试图在任何可能的地方放置递归调用，甚至我的导师也无法弄清楚。我还必须提到，将循环的递归调用移动到它通过错误的位置，并且程序与引发错误的解决方案不一致。

import java.util.Scanner;
    public class NonAttackingQueens {
        private Scanner scan = new Scanner(System.in);
        //Row
        private int r = 0;
        //Column
        private int c = 0;
        private int solution = 1;
        private int[] taken = {9,9,9,9,9,9,9,9};
        private int[][] board = {
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0}};

        public static void main(String[] args){
            NonAttackingQueens board = new NonAttackingQueens();
        }

        public NonAttackingQueens(){
            place();
        }

        //This is the main method that runs everything.
        private void place(){
            //There are only 92 solutions, and this stops it after the 92th iteration
            while (solution <= 92){
                //If r==8 then it has found a solution
                if (r == 8){
                    System.out.println(this);
                    r = 7;
                    //This forces the program to continue
                    //It removes the last queen tries to move it right one
                    backTrack(0);

                    //The Scanner is used to pause the program after every solution
                    //Just hit enter to continue
                    scan.nextLine();

                    //place();
                }
                else {
                    //If it is not a legal spot
                    if (poss()){
                        board[r][c] = 1;

                        //The taken array is the location of all the queens
                        //It works the same as a regular coordinate system
                        //but being an array is a little more difficult to read
                        /*
                         *   0 1 2 3 4 5 6 7
                         * 0 9 9 9 9 9 3 9 9
                         * 1 9 9 9 9 9 3 9 9
                         * 2 9 9 9 9 9 3 9 9
                         * 3 9 9 9 9 9 3 9 9
                         * 4 9 9 9 9 9 3 9 9
                         * 5 9 9 9 9 9 3 9 9
                         * 6 9 9 9 9 9 3 9 9         
                         * 7 9 9 9 9 9 3 9 9
                         * 
                         * {9,9,9,9,9,3,9,9}
                         * 
                         */
                        //The element of the array is equal to its column
                        //The value of the element is equal to its row
                        //So a queen in row 3 column 5 is equal
                        //is equal to taken[5]=3;
                        //Or the entire first solution would have to array equal
                        //{0,6,4,7,1,3,2,5}
                        taken[c] = r;

                        r++;
                        c = 0;

                        //place();
                    }
                    //Then find a new one
                    else {
                        findNext();
                        //This is how it would run recursively........
                        //If it did not give a stack overflow
                        //this.place();
                    }
                }
                place();
            }
        }

        //Tests if it is legal to move here
        private boolean poss(){
            if (c >= 8 || taken[c] != 9 || diag()) return false;

            else return true;
        }

        //Checks for any diagonal attacks
        //It's logic is opposite of the other two conditions in the .poss()
        private boolean diag(){
            int left = c;
            int right = c;
            int tmpR = r;

            boolean found = false;

            while (left >= 0 && tmpR >= 0){
                if (board[tmpR][left] == 1) {
                    found = true;
                }
                tmpR -= 1;
                left -= 1;
            }

            tmpR = r;

            //These worked intuitively
            //They go up one row then left or right one column
            //If it hits a 1 then there's a diagonal
            //If it hits -1 then there is not
            while (right <= 7 && tmpR >= 0 && found != true){
                if (board[tmpR][right] == 1){
                    found = true;
                }
                tmpR -= 1;
                right += 1;
            }
            return found;
        }

        //This literally keeps going right until it finds an opening or hits the right side
        //Then it does the back track method
        private void findNext(){
            //The last column did not work so it immediately goes to the next one
            c++;
            //100% recursive
            if (c < 8){
                //Tests if it is a legal spot
                if (poss()){
                    return;
                }
                //If not then go to the next column
                else findNext();
            }
            //If it hits the right side then it back tracks
            else {
                //Nothing on this row so immediately go to the one before
                r--;
                backTrack(0);
            }
        }

        private void backTrack(int x){
            if (x < taken.length){
                //This is the main reason why I have the taken array
                //It checks every array element until it finds the one equal to the
                //element that needs to be removed.
                //It changes that element to 9 and removes it from the board
                //It then makes c equal one more than the column it just removed the element from
                if (taken[x] == r){
                    taken[x] = 9;
                    board[r][x] = 0;
                    c = x + 1;
                    return;
                }
                else {
                    x++;
                    backTrack(x);
                }
            }

        }

        public String toString(){
            String result="Solution: "+solution+"\n";
            for (int i=0; i<board.length; i++){
                for (int j=0; j<board[i].length; j++){
                    result += board[i][j];
                }
                result += "\n";
            }
            solution++;
            return result;
        }
    }

要使其运行递归，请将 place 方法中的 while 更改为 if 并取消注释 .place() 方法。

Answer 1

如果您在递归调用之外遇到溢出，则表明计数器导致某些内容超出范围。要么，要么递归运行太深，这样你就运行出栈了 space。查看除此之外使用的数组；我建议打印出相关计数器的值以查看发生的情况。

如果我遇到溢出错误，计数器通常是我开始的地方；特别是当我处理数组时。

希望对您有所帮助！

递归错误

Error from Recursion

java

stack-overflow

recursion