java - java 骑士之旅

Question

每当我运行该程序而不是找到 Knights Tour 时，都会收到 StackOverflow 错误。知道是什么导致了这个错误，以及我如何改变我的代码以实际找到骑士之旅并摆脱这个错误。项目适用于我的 CS280 类(class)，预计周五截止，请帮忙。谢谢!!

public class KnightsTourDriver {
    public static void main (String[]args) {
        KnightsTour tour1 = new KnightsTour;
        tour1.findTour(1);
        tour1.displayTour();
    }
}  



import java.util.Arrays;
class KnightsTour
{

    static int the_board[][] = new int[8][8];
    int the_tour[][] = new int [8][8];
    int k,moves = 0;
    int x = 0, y = 0; 
    int z, j = 1;
    boolean tour_found, isSafe;

        //fills 2D array with 0's
        public KnightsTour()
        {
            for (int i = 0; i < 8; i++) 
                {
                 for (int r = 0; r < 8; r++) 
                    {
                            the_board[i][r] = 0;
                        }
                }
        }
        /*recursive method, checks how many moves were made if 16 were made tour finished, 
        else if not moves knight checks if the move is valid if not back tracks*/
        public void findTour(int q)
        {

            if(moves == 64)
                {
                    tour_found = true;
                }

            else 
                move(q); 

            if(isSafe == true)
                    {
                        findTour(q++);
                        moves++;
                    }
            else
                if(isSafe == false)
                    {
                        findTour(q*(-1));
                        moves--;
                    }
        }
        //used to keep prevent arrayindexoutofbounds error
        public boolean arrayInBounds(int x, int y)
        { 
        if(x < 8 && y < 8 && x >= 0 && y >= 0)
                {
                    return true;
                }
            else return false;
        }
        /*move method uses switch statement to decide which move the knight should make
        based on a case number, negative case numbers back track knight. if statement checks
        if the current array element is empty and the index is inbounds*/
        public void move(int a)
        {

            switch (a)
            {
               case 1:
                if(arrayInBounds(x+2, y+1) == true){
                   if(the_board[x+2][y+1] != 0){                          
                        the_board[x+2][y+1]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                    }
                else isSafe = false;
               case 2:
                if (arrayInBounds(x+1, y+2) == true){
                    if(the_board[x+1][y+2] != 0){               
                            the_board[x+1][y+2]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                }
                else isSafe = false;
               case 3:
                 if(arrayInBounds(x-1, y+2) == true){
                   if(the_board[x-1][y+2] != 0){           
                            the_board[x-1][y+2]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                 }
                else isSafe = false;
               case 4:
                if (arrayInBounds(x-2, y+1) == true){
                    if(the_board[x-2][y+1] != 0){           
                            the_board[x-2][y+1]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                }
                else isSafe = false;
               case 5:
                if(arrayInBounds(x-2, y-1) == true){
                    if(the_board[x-2][y-1] != 0){           
                            the_board[x-2][y-1]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                }
                else isSafe = false;
               case 6:
                if(arrayInBounds(x-1, y-2) == true){
                        if(the_board[x-1][y-2] != 0){                    
                            the_board[x-1][y-2]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
            }
                else isSafe = false;
               case 7:
                 if(arrayInBounds(x+1, y-2) == true){
                    if(the_board[x+1][y-2] != 0){          
                            the_board[x+1][y-2]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                 }
                 else isSafe = false;
               case 8:
                if(arrayInBounds(x+2, y-1) == true){
                 if(the_board[x+2][y-1] != 0){
                            the_board[x+2][y-1]=j;
                            j++;
                            break;
                        }
                        else isSafe = false;
                        break;
                }
                else isSafe = false;
               case -1:
                      j--;
                      tryNextMove(a);
                      break;
                    case -2:
                        j--;
                        tryNextMove(a);
                        break;
                    case -3:
                      j--;
                      tryNextMove(a);
                      break;
                    case -4:
                      j--;
                      tryNextMove(a);
                      break;
                  case -5:
                     j--;
                      tryNextMove(a);
                      break;
                    case -6:
                      j--;
                      tryNextMove(a);
                      break;
                    case -7:
                      j--;
                      tryNextMove(a);
                      break;
                   case -8:
                      j--;
                      tryNextMove(a);
                      break;
             }
        }
        public void tryNextMove(int m)
        {
            move(m++);
        }
        //for loop to display tour once found//         
        public void displayTour()
        {
            int v = 1;
            for (int i = 0; i < 8; i++) 
                {
                 for (int e = 0; e < 8; e++) 
                    {               
                                if(v % 8 == 0)
                                {
                                    System.out.print(the_board[i][e] + "\t");
                                    System.out.println("\n");
                                } 
                        else    
                            System.out.print(the_board[i][e] + "\t");
                            v++;                
                        }
                }
        }
}

Answer 1

如果您的算法确实需要大深度的递归调用，您可以在启动时向 JVM 传递一个参数以增加堆栈大小的限制:-Xss4m

当然，如果你的算法没有限制地递归，这只会延迟问题。