Finding unique paths in a 5X5 grid

Question

We have a 5X5 grid with each grid labelled with a unique number. We are given 5 different pair of grids. The task that needs to performed is to find unique paths between all the 5 different pair of grids subject to following condition :

1. The entire 5X5 grid must be covered.
2. Paths must not overlap.

Consider for example the grids are numbered from 1-25. we are given any 5 different pair of grids as
1 22
4 17
5 18
9 13
20 23

The expected output is
1 6 11 16 21 22
4 3 2 7 12 17
5 10 15 14 19 18
9 8 13
20 25 24 23

we need to print the unique paths for each pair fulfilling above stated conditions.

here is the messy code i've developed so far but no where close to getting any closer to the solution.

static StringBuffer findpath(int[][] grid, int index[][]){
    StringBuffer s = new StringBuffer();
    int[][] paths = new int[5][5];
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            paths[i][j] = 0;
        }
    }
    for(int l=0;l<2;l++){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(index[l][0] == grid[i][j])
                    paths[i][j] = 1;
                if(index[l][1] == grid[i][j])
                    paths[i][j] = 1;
            }
        }

    }

    int x=0,y=0,target = 0;
    for(int l=0;l<2;l++){
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(index[l][0] == grid[i][j]){
                    x = i;
                    y = j;
                    target = index[l][1];
                }
            }
        }

    gridUtil(grid, x, y, target, paths,s);
        s.append(grid[x][y]);
        s.append("\n");
    }

    return s;

}
static boolean doesnotoverlap(int[][] paths, int x, int y){
    if(x>=0 && x<5 && y>=0 && y<5 && paths[x][y] == 0)
        return true;
    return false;
}
static void printpath(StringBuffer s){
    System.out.println(s);
}
static boolean gridUtil(int grid[][], int x, int y, int target, int paths[][],StringBuffer s){
    if(x<5 && y<5 && grid[x][y] == target)
    {   paths[x][y] = 1;
        s.append(target+" ");
        return true;
    }
        int in = 0;
        //System.out.println(gridUtil(grid, Math.abs(x+1), y, target, paths, s));
        if(doesnotoverlap(paths, x+1, y)){
            System.out.println("here1");
            paths[x][y] = 1;
            s.append(grid[x][y]+" ");
            in = s.indexOf(Integer.toString(grid[x][y]));
            if(gridUtil(grid, Math.abs(x+1), y, target, paths, s))
            return true;
        }
        if(doesnotoverlap(paths, x-1, y)){
            System.out.println("here");
            paths[x][y] = 1;
            s.append(grid[x][y]+" ");
            in = s.indexOf(Integer.toString(grid[x][y]));
            if(gridUtil(grid, Math.abs(x-1), y, target, paths, s))
            return true;
        }
        if(doesnotoverlap(paths, x, y+1)){
            paths[x][y] = 1;
            s.append(grid[x][y]+" ");
            in = s.indexOf(Integer.toString(grid[x][y]));
            if(gridUtil(grid, Math.abs(x),  Math.abs(y+1), target, paths, s))
            return true;
        }
        if(doesnotoverlap(paths, x, y-1)){
            paths[x][y] = 1;
            s.append(grid[x][y]+" ");
            in = s.indexOf(Integer.toString(grid[x][y]));
            if(gridUtil(grid, Math.abs(x),  Math.abs(y-1), target, paths, s))
            return true;
        }
        paths[x][y] = 0;
        //System.out.println(in);
        //s.deleteCharAt(in);
        return false;



}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[][] grid = new int[5][5];
    int[][] index = new int[5][2];
    int fill=0;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            fill = fill + 1;
            grid[i][j] = fill;
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            index[i][j] = sc.nextInt();

        }
    }


    StringBuffer s = findpath(grid, index);
    System.out.println(s);





}

}