Отладка рекурсивного метода для поиска, существует ли слово в ошибочной доске

Question

Я пытаюсь реализовать ошеломляющий решатель.

Моя основная идея состояла в том, чтобы создать метод, который проверял бы слово, чтобы увидеть, было ли оно на доске. затем обрежьте мой словарь, избавившись от слов, начинающихся с символов, которых нет на доске, а затем примените этот метод к каждому слову в словаре, чтобы получить набор решений.

Я не совсем уверен, насколько эффективно это решение... Я почти уверен, что оно работает только на O(n) (пропорционально размеру набора словарей) - что было бы неплохо на больших досках (5x5 - 7x7)

Мой текущий метод (который должен работать, если я могу исправить то, как работает посещаемый):

private Tile findFirstTile(String word) {
    word = word.toUpperCase();
    Tile first = null;
    boolean found = false;
    for (Tile tile : tiles) {
        if (tile.getChar() == word.charAt(0)) {
            first = tile;
            found = true;
        }
    }
    if (found) {
        System.out.println("Found the tile!!");
        return first;
    }
    else return null;
}


public boolean findWordOnBoard(String word, Tile tile, int depth, HashSet<Integer> visited) {
    System.out.println("depth is " + String.valueOf(depth) + " right meow.");
    if (depth == word.length()) return true; // base case - breaks recursion (on board)
    else {
        word = word.toUpperCase();
        if (tile == null) return false;
        HashSet<Integer> neighbors = map.get(tile.getPlace());
        for (int n : neighbors) {
            if ((tiles[n-1].getChar() == word.charAt(depth)) && (!visited.contains(n))) {
                visited.add(n);
                System.out.println("found " + tile.getChar() + " at " + n);
                if (depth == word.length()) return true; // it shouldn't but oh well it's just here
                findWordOnBoard(word, tiles[n-1], depth +1, visited);
            } 
        }

        System.out.println("only supposed to be here if it's ACTUALLY not on board");
        return false; //will only get here if it doesn't find a new word
    }
}

Я не уверен, правильно ли я выполняю рекурсию... сейчас она не находит слов, но мне кажется, что она должна работать..? меня особенно беспокоит, правильно ли я обращаюсь с посещенным набором (если он отслеживает, какие плитки он посещал на каждой глубине), но я знаю, что это не единственная проблема, потому что я все равно смогу найти несколько коротких слов в противном случае...

R L O S
E E A P
M S T R
E A T S

Кроме того, я только что понял, что мой метод "findFirstTile" начнет искать слова только в последней плитке, начинающейся с этой буквы... поэтому, если на доске несколько вхождений этой буквы, он может не просмотреть их все.

это конструктор для моего объекта Tile также:

  public Tile (char letter, int place){ // NOTE: the char MUST BE capital
    this.letter = letter;
    this.place = place;
    try {
        img = ImageIO.read(new File("tile"+letter+".png"));
    } catch (IOException e) {
    }

Массив плиток (тайлы), на который я ссылаюсь, также является просто массивом всех тайлов в порядке, так что в основном на моей доске:

tiles[0]  tiles[1]  tiles[2]  tiles[3]
tiles[4]  tiles[5]  tiles[6]  tiles[7]
tiles[8]  tiles[9]  tiles[10] tiles[11]
tiles[12] tiles[13] tiles[14] tiles[15]

в то время как "места" (из конструктора Tile) просто

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

Я проверил мои методы getNeighbors() и getChar() и getPlace(), и все они работают как положено.

Answer 1

На случай, если кому-то интересно (вероятно, нет, смеется)

вот пересмотренный (и рабочий) код:

public boolean findWordOnBoard(String word, Tile tile, int depth, HashSet<Integer> visited) {
    if (depth == word.length()) return true; // base case - breaks recursion (on board)
    else {
        word = word.toUpperCase();
        if (tile == null) return false;
        HashSet<Integer> neighbors = map.get(tile.getPlace());
        for (int n : neighbors) {
            if (depth >= word.length()) return true;
            if ((tiles[n-1].getChar() == word.charAt(depth)) && (!visited.contains(n))) {
                visited.add(n);
                System.out.println("found " + tile.getChar() + " at " + n);
                return findWordOnBoard(word, tiles[n-1], depth+1, visited);
            } 
        }

    }
    return false; //will only get here if it doesn't find a new word
}

проблема заключалась в том, чтобы просто возвращать рекурсивный вызов, а не просто сделать его, так как, когда он проходил в обратном направлении через рекурсию, базовый случай вызова break (deep == word.length()) перестал быть истинным, поскольку глубина вернулась к 1,