Connecting nodes in a matrix for a graph

Question

Hi I'm working on this little project which requires me to build a matrix in Java which resembles a chess board. I'm supposed to get the Knight to get from a point to another(In the way Knight moves). So I need to find the shortest way to get there in the end.

My problem is, I can't get to connect the edges to get to that point. I can find out if the vertex is a valid move but I can't seem to find a way to create nodes to get to that point. For Example,

0 XXXXX

1 XXXOX

2 XXXXX

3 XXKXX

4 XXXXX

5 XXXXX

I need to create nodes that connect K to O to find out shortest distance later. PS. I'll be okay with just hints of how to get there or just some tips. Don't really need the exact code. Thank you very much! I know it's a bad representation of matrix up there but spare me the critique please

meriton meriton · Accepted Answer · 2016-03-27T04:24:57

A classic Breadth-First-Search is probably the simplest approach:

class Location {
    int x;
    int y;

    List<Location> adjacent() {
        // TODO return list of locations reachable in a single step
    }
}

List<Location> findShortestPath(Location start, Location destination) {
    Location[][] previous = new Location[8][8];

    Deque<Location> queue = new ArrayDeque<>();
    queue.add(start);
    do {
        Location loc = queue.poll();
        for (Location n : loc.neighbors()) {
            if (previous[n.x][n.y] == null) {
                previous[n.x][n.y] = loc;
                queue.add(n);

                if (n.x == destination.x && n.y == destination.y) {
                    // we've found a way, let's reconstruct the list of steps
                    List<Location> path = new ArrayList<>();
                    for (Location l = n; l != start; l = previous[l.x][l.y]) {
                        path.add(l);
                    }
                    path.reverse();
                    return path;
                }
            }
        }
    } while (!queue.isEmpty());
    return null; // no path exists
}

This code enumerates all paths from the start location. Therefore, if there is a path to destination, it will find it. In addition, because paths are enumerated in order or ascending length, the first such path will be a shortest one.

Connecting nodes in a matrix for a graph

2 Answers