I am having trouble with returning in depth first search

Question

I am working on an algorithm that finds a path in a hexagon grid. For this I am using depth first search with a depth of 3. It works in the sense that it finds the correct path. The only problem is that it does not return it. Instead it returns an empty set.

public Set findPath(Game game, Point origin, Point destination, Set<Point> hasVisited, int depth) throws Exception {
    if (origin.equals(destination)){
        System.out.println("Return from goal requirements: " + hasVisited);
        return hasVisited;
    }

    if (!origin.equals(destination)){
        if (depth != 0) {
            for (Point emptyNeighbor : getEmptyNeighbors(game, origin)) {
                if (!hasVisited.contains(emptyNeighbor)) {
                    if (!game.isHiveBrokenAfterPush(origin, emptyNeighbor)) {
                        hasVisited.add(emptyNeighbor);
                        game.push(origin.x, origin.y, emptyNeighbor.x, emptyNeighbor.y);

                        findPath(game, emptyNeighbor, destination, actualOrigin, hasVisited, depth - 1);

                        hasVisited.remove(emptyNeighbor);
                        game.push(emptyNeighbor.x, emptyNeighbor.y, origin.x, origin.y);
                    }
                }
            }
        }
    }

    System.out.println("Return from end of function: " + hasVisited);
    return hasVisited;
}

After the loads of If statements it adds the node to hasVisited and pushes the piece in the direction. It then calls itself to continue on the branch of the tree. It removes the node form hasVisited and cancels the push if it does not work out.

What happends right now is that the final return seems to be from the and of the function. These are the last lines it prints:

Return from goal requirements: [java.awt.Point[x=-1,y=0], java.awt.Point[x=-2,y=1], java.awt.Point[x=-2,y=2]]
Return from end of function: [java.awt.Point[x=-1,y=0], java.awt.Point[x=-2,y=1]]
Return from end of function: [java.awt.Point[x=-1,y=0]]
Return from end of function: []
[]

The upper set of coordinates is what it SHOULD return. But it returns an empty set as you can see.

I have tried to return the findPath instead of just executing it. Doing that it only does one branch. It doesn't cancel moves that don't work. I can't see the problem in my code and hope you guys can help me. Cheers!

Answer 1

If there is just one solution, return immediately. The recursion adds one element to the set, calls recursively and undoes the adding. This will alter the set, the result. When collecting more than one result, one would copy the set.

public boolean findPath(Game game, Point origin, Point destination, Set<Point> hasVisited,
            int depth) throws Exception {
    if (origin.equals(destination)){
        System.out.println("Return from goal requirements: " + hasVisited);
        return true;
    }

    if (depth != 0) {
        for (Point emptyNeighbor : getEmptyNeighbors(game, origin)) {
            if (!hasVisited.contains(emptyNeighbor)) {
                if (!game.isHiveBrokenAfterPush(origin, emptyNeighbor)) {
                    hasVisited.add(emptyNeighbor);
                    game.push(origin.x, origin.y, emptyNeighbor.x, emptyNeighbor.y);
                    boolean found = findPath(game, emptyNeighbor,
                            destination, actualOrigin, hasVisited, depth - 1);
                    if (found) {
                        return true;
                    }

                    hasVisited.remove(emptyNeighbor);
                    game.push(emptyNeighbor.x, emptyNeighbor.y, origin.x, origin.y);
                }
            }
        }
    }

    System.out.println("Not found");
    return false;
}