Missing nodes in solution (maze DFS solving algorithm)

Question

I have a problem with my DFS algorithm missing nodes from solution (check image). It happens every time my algorithm encounters a dead end: the node is poped from stack to go back till available move is found, and is never reincluded again. Is there a easy way to fix it without reimplementing whole algorithm?

    final int start = maze.getStart();
    final int stop = maze.getStop();
    final int columns = maze.getColumns();
    final int[] moves = { 0, 1, 2, 3 }; //North, E, S, W
    int position = start;

    Maze.Cells cells = maze.getCells();
    cells.setVisited(position);
    Stack<Integer> stack = new Stack<>();
    visitCells:
    while(position != stop){
        boolean[] availableMoves = cells.getAvailableMoves(position); //only visit yet unvisited cells
        for(int move : moves){
            if(availableMoves[move] && maze.isMovePossible(position, move)){
                position = doMove(position, move)
                cells.setVisited(position);
                stack.push(position);
                continue visitCells;
            }
        }
        position = stack.pop();
    }
    return stack;

I hope that the code is sefl-explicable. Drawing algorithm is correct, so I dont post it here. Don't hesitate to ask for more information in comments.

Answer 1

I think the problem is that when you make a move from A to B, you are pushing the new position B onto the stack. This means that when you backtrack you never get back to A.

Try reordering:

            position = doMove(position, move)
            cells.setVisited(position);
            stack.push(position);

to

            stack.push(position);
            position = doMove(position, move)
            cells.setVisited(position);