Беда с моим алгоритмом для решения проблемы

Question

Так что я относительно новичок в Java (в настоящее время я использую AP java в своей школе) и пытаюсь разработать рекурсивный алгоритм для решения n*n доски, и я чувствую, что я очень близок, но еще не совсем там. У меня есть все, что написано для обхода моего словаря, чтобы определить, являются ли буквы, которые я посылаю, словами или нет. Мой алгоритм состоит в том, чтобы начальная буква была (n,p) в моем массиве, отправлять эти кордикации другим способом, который будет идти в каждом направлении, чтобы найти все возможные комбинации. как только найдены все комбинации, начинающиеся с (n,p), я буду увеличивать p до тех пор, пока он не достигнет конца строки, тогда я увеличу n и снова начну p с 0. (Я прохожу только половину букв, потому что комбинации вперед и назад одинаковы)

Часть, с которой у меня возникли проблемы, - это рекурсивная последовательность, потому что, как только я перехожу на определенную позицию на доске, я хочу отметить ее, чтобы быть уверенной, что я никогда не перейду ее снова до конца последовательности. Это не полностью работает, и мне было интересно, если кто-нибудь может сказать мне, почему / помочь мне написать лучший алгоритм. заранее спасибо

public void AllLetters(int n, int p, int x, int y,String word, String MyLetteres[][]){
    int temp=0;
    int StartLetter =(int)(Math.pow(MyLetteres.length,2));
    while(temp<StartLetter)//runs through every letter
    {   
        if(temp==0)
            getPaths(p, n,x,y,word, MyLetteres);
        else if(temp%(MyLetteres.length-1)==temp){
            getPaths(p, n+1,x,y,word, MyLetteres);
        }
        else {
            getPaths(p+1, 0,x,y,word, MyLetteres);
        }
        if(temp==(StartLetter/2-1)){
            temp=StartLetter;
        }
        temp++;
    }

}


public void getPaths(int p, int n, int x, int y,String word, String MyLetteres[][]){
    if( x ==p-1 && y == n-1){//reach the (n,p) point
    System.out.print("");
    }else if( x >= MyLetteres.length || y >= MyLetteres.length||x < 0 || y < 0){//out of bounds
    return;
    }else {
        if(x+1<MyLetteres.length&&!MyLetteres[x+1][y].equals("0")){//up{
            word=word+""+MyLetteres[x+1][y];
            Check(word);//function that checks if it is a word
            reverse(word);//checks its a word backwards (for efficenicy)
            MyLetteres[x+1][y]="0";//marking that I've used this position
            System.out.print("1");//debugging purposes
            getPaths(n,p, x +1, y,word , MyLetteres);
        }
        if(x-1>0&&!MyLetteres[x-1][y].equals("0")){//down
            word=word+""+MyLetteres[x-1][y];
            Check(word);
            reverse(word);
            MyLetteres[x-1][y]="0";
            System.out.print("2");
            getPaths(n,p, x -1, y ,word, MyLetteres);
        }
        if(y+1<MyLetteres.length&&!MyLetteres[x][y+1].equals("0")){//right
            word=word+""+MyLetteres[x][y+1];
            Check(word);
            reverse(word);
            MyLetteres[x][y+1]="0";
            System.out.print("3");
            getPaths(n, p,x , y +1,word, MyLetteres);
        }
        if(y-1>0&&!MyLetteres[x][y-1].equals("0")){//left
            word=word+""+MyLetteres[x][y-1];
            Check(word);
            reverse(word);
            MyLetteres[x][y-1]="0";
            System.out.print("4");
            getPaths(n,p, x , y -1,word, MyLetteres);
        }
        if(x+1<MyLetteres.length&&y+1<MyLetteres.length&&!MyLetteres[x+1][y+1].equals("0")){//right, up
            word=word+""+MyLetteres[x+1][y+1];
            Check(word);
            reverse(word);
            MyLetteres[x+1][y+1]="0";
            System.out.print("5");
            getPaths(n,p, x +1, y +1,word, MyLetteres);
        }
        if(x-1>0&&y-1>0&&!MyLetteres[x-1][y-1].equals("0")){//down, left
            word=word+""+MyLetteres[x-1][y-1];
            Check(word);
            reverse(word);
            MyLetteres[x-1][y-1]="0";
            System.out.print("6");
            getPaths(n,p, x-1 , y -1,word, MyLetteres);
        }
        if(x-1>0&&y+1<MyLetteres.length&&!MyLetteres[x-1][y+1].equals("0")){//down, right
            word=word+""+MyLetteres[x-1][y+1];
            Check(word);
            reverse(word);
            MyLetteres[x-1][y+1]="0";
            System.out.print("7");
            getPaths(n,p, x+1, y-1, word,MyLetteres);
        }
        if(x+1<MyLetteres.length&&y-1>0&&!MyLetteres[x+1][y-1].equals("0")){//up, left
            word=word+""+MyLetteres[x+1][y-1];
            Check(word);
            reverse(word);
            MyLetteres[x+1][y-1]="0";
            System.out.print("8");
            getPaths(n, p,x-1 , y +1, word,MyLetteres);
        }
    }
}

Answer 1

Вы пишете 0 в MyLetteres чтобы рекурсия не зациклилась на себе. Но как только рекурсивный вызов вернулся, вам нужно восстановить исходное письмо, которое было в этой позиции. В противном случае поиск может просмотреть только каждую позицию по всем ветвям, которые он пробует.

(Кроме того, вы могли бы значительно упростить свой код, просматривая список смещений (x, y), а не располагая отдельным if утверждение для каждого)

Редактировать:

int[][] offsets = { {-1, -1}, {0, -1}, {1, -1}, 
                    {-1,  0},          {1,  0}, 
                    {-1,  1}, {0,  1}, {1,  1} };

for(int[] off : offsets) {
   nx = x + off[0];
   ny = y + off[1];
   if(nx < 0 || ny < 0 || nx >= MyLetteres.length || ny >= MyLetteres[nx].length) {
      continue;
   }
   String letter = MyLetteres[nx][ny];
   if(letter.equals("0")) {
      continue;
   }
   MyLetteres[nx][ny] = "0";
   Check(word + letter);
   reverse(word + letter);
   getPaths(n,p, nx, ny, word + letter, MyLetteres);
   MyLetteres[nx][ny] = letter;
}