我正在尝试实现一个 boggle 求解器。
我的基本想法是创建一种方法来检查单词是否在板上。然后通过删除以char开头的单词来修剪我的字典,然后将该方法应用于字典集上的每个单词以获得解决方案集。
我不完全确定这个解决方案的效率有多高。我很确定它只在 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() 方法,它们都按预期工作。