What kind of maze Solving Algorithm is this?

Question

I am trying to figure out if this algorithm is A* (A-Star) Algorithm or whatever but still I am confused.

Stack<Cell> stack = new Stack<>();

stack.push(maze.start());
stack.peek().mark(SOLUTION_MARK);

while (!stack.peek().hasMark(Cell.END)) {

    Cell current = stack.peek();
    ArrayList<Cell> dirs = current.neighbors();

    boolean found = false;
    for (Cell next : dirs) {
        if (next.hasMark(ERROR_MARK) || next.hasMark(SOLUTION_MARK)) {
            continue;
        }
        stack.push(next);
        next.mark(SOLUTION_MARK);
        found = true;
        break;
    }
    if (!found) {
        stack.pop().mark(ERROR_MARK);
    }
    for (MazeBody listener : listeners) {
        listener.repaint();
    }
}

Mark.java

public final class Mark {

    private static Map<String, Mark> TABLE = new HashMap<>();

    private String name;

    private Mark(String markName) {
        name = markName;
    }

    public static Mark get(String name) {
        Mark mark = TABLE.get(name);
        if (mark == null) {
            mark = new Mark(name);
            TABLE.put(name, mark);
        }
        return mark;
    }
}

Answer 1

This is Depth First Search written iteratively rather than recursively.

Recursive DFS (preorder) pseudocode looks like:

visit (current node)
for each child node of current node
    if node is not explored
        dfs (node)

Iterative version of DFS looks like:

Put current node on stack
In a while loop pop the stack if not empty
    visit (popped node)
    push all Unvisited and NotVisiting neighbors of popped node on the stack
End while

Unvisited and NotVisiting in the Iterative version means that the node is neither visited before, nor it is in the stack for visiting.

---

The time complexity of this algorithm depends on whether the graph has been stored as adjacency list or adjacency matrix. For list, it'd be O(n). For matrix, it'd become O(n²) because even though you explore every node only once, you have to visit every row and column of the matrix to know if there is a path between a node X and node Y.

The space complexity of this algorithm can go to worst of O(n), happening when the graph would have each node having only one neighbor, becoming like a singly linked list.

Answer 2

Based on what you show I would say it is depth-first search, but with a check whether the place has already been scheduled for visit. Since it uses a stack, it will always first visit the places deeper in the search tree. But from the moment it adds a place to the stack, it marks the place as a solution mark to prevent it from being re-evaluated if another path would reach the same place.

Note however that it will mark every tile a SOLUTION_MARK unless it cannot come up with nodes others than marked with a SOLUTION_MARK or an ERROR_MARK. It will thus mark more tiles than the tiles contributing to (shortest) the solution. In that sense it is not really a maze solving algorithm: it simply marks tiles as SOLUTION_MARK if there is at least another tile not yet scheduled that can contribute to a solution. The algorithm will finish if it has marked all reachable tiles.