java - min of knight's moves to get to a destination

Question

I'm trying to solve this challenge which is to get the min cost of Knight's moves from a source to a destination in a (8*8) chess board and I'm getting a case that not working … I guess I messed up somewhere and I cant figure that out.

see image here

the full code

import java.util.ArrayList;
import java.util.List;


public class Solution {
    static class Position{
        public int x;
        public int y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int solution(int src, int dest) {
        int min = 100000000;
        int depth = 0;
        Position source = new Position(0, 0), destination = new Position(0, 0);

        int [][] board = getBoard(src, dest, source, destination);
        
        if(arrived(source, destination)) return 0;
        
        return solve(board, source, destination, (depth), min);
    }
    public static int[][] getBoard(int src, int dest, Position source, Position destination) {
        int c = 0;
        int [][] board = new int[8][8];
         for(int i = 0; i < board.length; i++){
             for(int j = 0; j < board.length; j++){
                if(c == src) {
                    board[i][j] = 1;
                    source.x = i;
                    source.y = j;
                }else if(c == dest) {
                    board[i][j] = -1;
                    destination.x = i;
                    destination.y = j;
                }else {
                    board[i][j] = 0;
                }
                 c++;
             }
         }
         return board;
    }
    public static int solve(int[][] board, Position position, Position destination, int depth, int min){
       if(depth > min) {
           return depth;
       }
       
       for(Position p: sort(getPossibleMoves(board, position), destination)){
           if(arrived(p,destination)) {
               return depth + 1;
           }
           board[p.x][p.y] = depth +2;
           int cost = solve(board, p, destination, (depth + 1), min);
           board[p.x][p.y] = 0;
           if(cost < min){
               min = cost;
           }
       }
        return min;
    }
    public static List<Position> sort(List<Position> positions, Position dest) {
        Position temp;
        boolean sorted = false;
        while(!sorted) {
            sorted = true;
            for(int i = 0; i < positions.size() - 1; i++) {
                if(distance(positions.get(i), dest) > distance(positions.get(i+1), dest)) {
                    temp = positions.get(i);
                    positions.set(i, positions.get(i+1));
                    positions.set(i+1, temp);
                    sorted = false;
                }
            }
        }
        return positions;
    }
    public static double distance(Position a, Position b) {
        if(a.x == b.x && a.y == b.y) return 0;
        return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
    }
    public static boolean arrived(Position src, Position dest) {
        return src.x == dest.x && src.y == dest.y;
    }
    public static List<Position> getPossibleMoves(int [][] board, Position current){
        int [][] moves  = {{1,2}, {2,1}, {-1,2}, {1,-2}, {-2,1}, {2,-1}, {-1,-2}, {-2,-1}};
        List<Position> positions = new ArrayList();
        for(int i = 0; i < moves.length; i++) {
            int x = current.x + moves[i][0];
            int y = current.y + moves[i][1];
            if(x >= 0 && y >= 0 && x < board.length && y < board.length && board[x][y] <= 0)
                positions.add(new Position(x, y));
        }
        
        return positions;
    }
    public static void main(String [] args) {
        System.out.println(solution(0, 1));

    }
}

so here is my approach :
we start from a position and we try all the possible moves (sorted by the nearest) till we find the destination and then do some kind of backtracking to see if there's a better way to get there at a low cost and return the minimum.
some rules I've set :

• the board is represented by a matrix of integers ( full of zeros if empty)
• the source is represented by 1
• the destination is represented by -1
• wherever the knight goes its going to be marked by an integer representing the cost (the start is 1 the second move will be 2 , third 3 and so on …)

let me break the code a little bit down to make it easier

• we start from the function solution public static int solution(int src, int dest) which will initialize the board, set the source and destinatin positions, and return the cost using the solve(board, source, destination, (depth), min) function
• the function public static int[][] getBoard(int src, int dest, Position source, Position destination) take the board, position … look trough all possible moves ( unmarked positions and sorted by the nearest) for that position and call recursively with a new position until it found the destination or the depth (witch is the cost) is bigger then the minimum that we already have
• the function public static List<Position> getPossibleMoves(int [][] board, Position current) will return the 8 possible moves for knight from a position but only those who are not out of the board and are also unvisited ( unvisited will be 0 or -1 for the destination )
• the function public static List<Position> sort(List<Position> positions, Position dest) will sort the possible moves by the nearest to the destination ( let's prioritize the nearest one)

please if you can help me figure out what's wrong or if you have another approach I'd really appreciate !

question from:https://stackoverflow.com/questions/66050099/min-of-knights-moves-to-get-to-a-destination

Answer 1

Waitting for answers