Ошибка из рекурсии

Question

Для проекта мне пришлось написать программу, которая рекурсивно решает 8 Queens Puzzle во всех 92 решениях. Программа работает нормально, пока вы не сделаете рекурсивно «основной» метод. Нечетная часть заключается в том, что она выдает ошибку в точке, не связанной с циклом «основного» метода (в том числе в методе 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; 
     } 
    } 

Для того, чтобы запустить его рекурсивным изменить время в методе место, чтобы если и раскомментируйте .Поместить() методы.

Answer 1

Если вы получаете переполнение за пределами рекурсивного вызова, это говорит о том, что счетчик вызывает что-то выходящее за пределы. Либо это, либо рекурсия работает слишком глубоко, и у вас заканчивается пространство стека. Посмотрите на массивы, используемые за пределами этого; Я бы предложил распечатать значения задействованных счетчиков, чтобы увидеть, где это происходит.

Если я когда-либо получаю ошибку переполнения, обычно меняются счетчики; особенно когда я имею дело с массивами.

Надеюсь, это поможет!