java - Trouble with my algorithm to solve a boggle board -

java - Trouble with my algorithm to solve a boggle board -

so i'm relatively new java (i'm taking ap java @ school currently) , trying develop recursive algorithm solve n*n board , sense close not quite there yet. have written out traverse dictionary find if letters sending words or not etc. algorithm have starting letter (n,p) in array, send cordinates method go in every direction find possible combinations. 1 time combinations starting (n,p) have been found, increment p until got end of row increment n , start p 0 again. (i go through half letters because combinations same backwards , forwards)

the part have problem recursive sequence because 1 time go on position on board want mark create sure never go on 1 time again rest of sequence. doesn't work , wondering if tell me why/help me write improve algorithm. in advance

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 (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 checks if word reverse(word);//checks word backwards (for efficenicy) myletteres[x+1][y]="0";//marking i've used 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, 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); } } }

you write 0's myletteres maintain recursion looping on itself. 1 time recursive phone call has returned, need restore original letter in position. otherwise search can @ each position once, on branches tries.

(also, simplify code lot looping through list of (x, y) offsets rather having separate if statement each one)

edit:

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; }

java array-algorithms