Поиск в глубину завершается досрочно

Я создаю программу на Java, которая решает n-puzzle без использования эвристики, просто просто с поиском в глубину и в ширину пространства состояний. Я немного борюсь с моей реализацией поиска в глубину. Иногда он решит данную загадку, но иногда кажется, что он рано сдается.

Вот мой класс DFS. DepthFirstSearch() передается PuzzleBoard, который изначально создается путем перетасовки решенной доски (чтобы гарантировать, что доска находится в решаемом состоянии).

public class DepthFirst {
static HashSet<PuzzleBoard> usedStates = new HashSet<PuzzleBoard>(); 

public static void DepthFirstSearch(PuzzleBoard currentBoard)
{   
    // If the current state is the goal, stop.
    if (PuzzleSolver.isGoal(currentBoard)) {    
        System.out.println("Solved!");
        System.exit(0); 
    } 

    // If we haven't encountered the state before,
    // attempt to find a solution from that point.
    if (!usedStates.contains(currentBoard)) {                       
        usedStates.add(currentBoard);           
        PuzzleSolver.print(currentBoard);

        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != 0) {
            System.out.println("Moving left");
            DepthFirstSearch(PuzzleSolver.moveLeft(currentBoard));
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != PuzzleSolver.n-1) {
            System.out.println("Moving down");
            DepthFirstSearch(PuzzleSolver.moveDown(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[1] != PuzzleSolver.n-1) {
            System.out.println("Moving right");
            DepthFirstSearch(PuzzleSolver.moveRight(currentBoard)); 
        }
        if (PuzzleSolver.blankCoordinates(currentBoard)[0] != 0) {
            System.out.println("Moving up");
            DepthFirstSearch(PuzzleSolver.moveUp(currentBoard));    
        }

        return; 
    } else {
        // Move up a level in the recursive calls
        return; 
    }
}   
}

Я могу утверждать, что мои методы и логика moveUp(), moveLeft(), moveRight() и moveDown() работают правильно, поэтому проблема должна быть где-то в другом месте.

Вот мой класс объектов PuzzleBoard с методами hashCode и equals:

static class PuzzleBoard {
    short[][] state;        
    /**
     * Default constructor for a board of size n
     * @param n Size of the board 
     */
    public PuzzleBoard(short n) {
        state = PuzzleSolver.getGoalState(n);
    }
    public PuzzleBoard(short n, short[][] initialState) {
        state = initialState; 
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.deepHashCode(state);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        PuzzleBoard other = (PuzzleBoard) obj;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (state[i][j] != other.state[i][j])
                    return false; 
            }
        }
        return true;
    }   
}

Как указывалось ранее, иногда поиск работает правильно и находит путь к решению, но в других случаях он останавливается до того, как находит решение и до того, как заканчивается память.

Вот фрагмент вывода, начинающийся за несколько ходов до того, как поиск прекращает поиск.

...
Moving down
6 1 3 
5 8 2 
0 7 4 
Moving right
6 1 3 
5 8 2 
7 0 4 
Moving left
Moving right
Moving up
6 1 3 
5 0 2 
7 8 4 
Moving left
Moving down
Moving right
Moving up
Moving up
Moving right
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
Moving up
Moving down
...

Я урезал его раньше для краткости, но в итоге он просто перемещается вверх и вниз десятки раз и никогда не достигает решенного состояния.

Может ли кто-нибудь пролить свет на то, что я делаю неправильно?

Изменить: это MoveUp(). Аналогично реализованы остальные методы перемещения.

/**
 * Move the blank space up
 * @return The new state of the board after the move
 */
static PuzzleBoard moveUp(PuzzleBoard currentState) {
    short[][] newState = currentState.state; 
        short col = blankCoordinates(currentState)[0]; 
        short row = blankCoordinates(currentState)[1]; 
        short targetCol = col; 
        short targetRow = row; 
        newState[targetCol][targetRow] = currentState.state[col - 1][row];
        newState[targetCol - 1][targetRow] = 0; 

        return new PuzzleBoard(n, newState); 
    }