How to find a path in a matrix which must pass through some cells

Given a 2d matrix, I have a start cell, end cell, cells that must be visited and cells that cannot be visited.

What would be the optimal way to find a path that:

starts at the start cell
ends at the end cell
passes through all must visit cell
does not pass through any cell that cannot be visited
does not pass any cell twice
we can only move left, right, up and down

The matrix size can be at most 10x10.

For example:

S - start
E - end
0 - can visit
X - can not visit
M - must visit

S 0 0 M 0
0 0 0 X 0
0 M 0 0 0
0 X 0 0 0
0 0 0 0 E


One solution would be:

* 0 * * *
* 0 * X *
* * * 0 *
0 X 0 0 *
0 0 0 0 *

The path doesn't necessarily should be the shortest one, but it would be nice if it can be, and it can be calculated quiet fast.

Solution

You can model the grid with a class Grid that would have a width and a height, and a set of must locations a set of mustNot locations:

public class Grid {
    private final int width;
    private final int height;
    private final Set<Location> must = new HashSet<>();
    private final Set<Location> mustNot = new HashSet<>();

    public Grid(int width, int height,
            Collection<Location> must, Collection<Location> mustNot) {
        this.width = width;
        this.height = height;
        this.must.addAll(must);
        this.mustNot.addAll(mustNot);
    }

In that class, you would have a method solve that would take a start location and an end location, and would return the best path:

public PathNode solve(Location start, Location end) {
    ...
}

class Location looks like this:

public class Location {
    public final int row;
    public final int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 41 * hash + this.row;
        hash = 41 * hash + this.col;
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Location other = (Location) obj;
        if (this.row != other.row) {
            return false;
        }
        return this.col == other.col;
    }

    @Override
    public String toString() {
        return "(" + row + ", " + col + ')';
    }
}

Basically, it's a row and a col.

A path is a linked list of PathNodes:

public class PathNode {
    public final Location loc;
    public final PathNode link;

    public PathNode(Location loc, PathNode link) {
        this.loc = loc;
        this.link = link;
    }

    public boolean contains(Location loc) {
        PathNode n = this;
        while (n != null) {
            if (n.loc.equals(loc)) {
                return true;
            }
            n = n.link;
        }
        return false;
    }
}

I've added a contains method because of the condition that a path must not go through the same location twice.

Now, the algorithm is a breadth-first search:

public PathNode solve(Location start, Location end) {
    List<PathNode> paths = new ArrayList<>();
    if (validLoc(start.row, start.col) == null) {
        return null;
    }
    paths.add(new PathNode(start, null));
    for (int i = 0; i < paths.size(); ++i) {
        PathNode path = paths.get(i);
        Location loc = path.loc;
        if (loc.equals(end)) {
            // at the end point, we must still check the path goes through
            // all the 'must' cells
            if (allMustInPath(path)) {
                // found a path
                return path;
            }
        } else {
            addToPaths(path, left(loc), paths);
            addToPaths(path, right(loc), paths);
            addToPaths(path, up(loc), paths);
            addToPaths(path, down(loc), paths);
        }
    }
    return null;
}

We still need a few more methods:

private Location left(Location loc) {
    return validLoc(loc.row, loc.col-1);
}

private Location right(Location loc) {
    return validLoc(loc.row, loc.col+1);
}

private Location up(Location loc) {
    return validLoc(loc.row-1, loc.col);
}

private Location down(Location loc) {
    return validLoc(loc.row+1, loc.col);
}

private Location validLoc(int row, int col) {
    if (row >= 0 && row < height && col >= 0 && col < width) {
        Location loc = new Location(row, col);
        return mustNot.contains(loc) ? null : loc;
    }
    return null;
}

private boolean allMustInPath(PathNode path) {
    for (Location loc: must) {
        if (!path.contains(loc)) {
            return false;
        }
    }
    return true;
}

private void addToPaths(PathNode path, Location loc, List<PathNode> paths) {
    if (loc == null) {
        return;
    }
    loc = validLoc(loc.row, loc.col);
    if (loc != null && !path.contains(loc)) {
        paths.add(new PathNode(loc, path));
    }
}

The path returned by the solve method, is actually in backward order. For your example above, it finds the path that you mentionned:

    Grid grid = new Grid(5,5,
            Arrays.asList(
                    new Location(0,3),
                    new Location(2,1)),
            Arrays.asList(
                    new Location(1,3),
                    new Location(3,1)));
    PathNode path = grid.solve(
            new Location(0,0),
            new Location(4,4));
    if (path == null) {
        System.out.println("No solution found");
    }
    while (path != null) {
        System.out.println(path.loc);
        path = path.link;
    }


(4, 4)
(3, 4)
(2, 4)
(1, 4)
(0, 4)
(0, 3)
(0, 2)
(1, 2)
(2, 2)
(2, 1)
(1, 1)
(0, 1)
(0, 0)