遞歸錯誤

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和uncomment .place（）方法。

Answer 1

如果您在遞歸調用之外發現溢出，那表明計數器正在導致某些內容超出範圍。要麼是這樣，要麼是遞歸運行得太深，並且你的堆棧空間不夠用。看看在那之外使用的數組;我會建議打印出涉及的計數器的值以查看發生的情況。

如果我得到溢出錯誤，計數器通常是我開始的地方;特別是當我處理數組時。

希望這會有所幫助！