爲什麼不減少Boggle求解器的工作？

Question

我正在寫一個boggle求解器，我不知道我的編碼出錯了。以下是我迄今爲止：

public class Boggle { 
char[][] letters; 
ArrayList <String> wordsPossible; 
boolean[][] lettersUsed; 
ArrayList<String> wordsMade = new ArrayList<String>(); 


public static void main(String[] args) { 
    Boggle boggle = new Boggle(); 

    boggle.findWords(); 
} 

public Boggle(){ 
    letters = new char[4][4]; 
    letters[0][0] = 'a'; 
    letters[0][1] = 'd'; 
    letters[0][2] = 'e'; 
    letters[0][3] = 'h'; 
    letters[1][0] = 's'; 
    letters[1][1] = 't'; 
    letters[1][2] = 'i'; 
    letters[1][3] = 'p'; 
    letters[2][0] = 's'; 
    letters[2][1] = 'k'; 
    letters[2][2] = 'c'; 
    letters[2][3] = 'e'; 
    letters[3][0] = 'u'; 
    letters[3][1] = 'f'; 
    letters[3][2] = 'r'; 
    letters[3][3] = 'o'; 

    Scanner scanner = null; 
    try { 
     scanner = new Scanner(new File("brit-a-z.txt")); 
    } catch (FileNotFoundException ex) { 
     Logger.getLogger(Boggle.class.getName()).log(Level.SEVERE, null, ex); 
    } 
    wordsPossible = new ArrayList<String>(); 
    while(scanner.hasNext()){ 
     String str = scanner.nextLine(); 
     wordsPossible.add(str); 
    } 
    lettersUsed = new boolean[4][4]; 
} 

public void findWords(){ 
    for(int i=0; i<letters.length; i++){ 
     for(int j=0; j<letters[i].length; j++){ 
      //findWords(jLabels[i][j].getText(), i, j, labelsUsed); 
      findWords(Character.toString(letters[i][j]), i, j, lettersUsed); 
      System.out.println("Done"); 
     } 
    } 
    for(int i=0; i<wordsMade.size(); i++){ 
     System.out.println(wordsMade.get(i)); 
    } 
} 

public void findWords(String word, int iLoc, int jLoc, boolean[][] lettersUsed){ 
    if(iLoc < 0 || iLoc >= 4 || jLoc < 0 || jLoc >= 4){ 
     return; 
    } 

    if(lettersUsed[iLoc][jLoc] == true){ 
     return; 
    } 

    word += letters[iLoc][jLoc]; 
    lettersUsed[iLoc][jLoc] = true; 

    if(word.length() >= 3 && wordsPossible.contains(word)){ 
     System.out.println(word); 
     wordsMade.add(word); 
    } 

    findWords(word, iLoc-1, jLoc, lettersUsed); 
    findWords(word, iLoc+1, jLoc, lettersUsed); 
    findWords(word, iLoc, jLoc-1, lettersUsed); 
    findWords(word, iLoc, jLoc+1, lettersUsed); 
    findWords(word, iLoc-1, jLoc+1, lettersUsed); 
    findWords(word, iLoc-1, jLoc-1, lettersUsed); 
    findWords(word, iLoc+1, jLoc-1, lettersUsed); 
    findWords(word, iLoc+1, jLoc+1, lettersUsed); 

    lettersUsed[iLoc][jLoc] = false; 
} 

}

它只是運行，幾乎不會說一個字被發現。運行需要很長時間，大約一個小時。我看不出我的錯誤在哪裏，我看不到我能在哪裏做出一個。任何幫助將是偉大的！

Answer 1

這將有一個組合爆炸搜索所有10,11,12,13,14等字母單詞。一旦當前的word不是字典中任何單詞的前綴，您應該添加代碼以修剪搜索。

另外，您正在使用ArrayList作爲單詞列表。在wordsPossible.contains(word)的平面列表中搜索速度非常慢，因爲它每次都會掃描整個列表。平均而言，這將需要40,000次迭代來處理80,000字的字典。

更合適的數據結構可以是tree set或prefix tree（或trie）。兩者都針對快速查找進行了優化，並且非常適合上述前綴檢查。對於樹集，ceiling()方法會很方便。有關嘗試使用Java的信息，請參閱this question。

Answer 2

該ArrayList將是巨大的！您應該嘗試使用更好的數據結構，例如，ArrayList<ArrayList<ArrayList<String>>>其中第一個索引是該單詞的第一個字母，第二個索引是該單詞的第二個字母。

wordsPossible = new ArrayList<ArrayList<ArrayList<String>>>(26); 
for (char c = 'a'; c <= 'z'; c++) { 
    ArrayList<ArrayList<String>> temp = new ArrayList<ArrayList<String>>(26); 
    wordsPossible.add(temp); 
    for(char d = 'a'; d <= 'z'; d++) { 
     ArrayList<String> innerTemp = new ArrayList<String>(); 
     temp.add(innerTemp); 
    } 
} 

// Snip 

while(scanner.hasNext()){ 
    String str = scanner.nextLine(); 
    addWord(str); 
} 

// Snip 

public void addWord(String str) { 
    int first = str.toLowerCase().charAt(0) - 'a'; 
    int second = str.toLowerCase().charAt(1) - 'a'; 
    wordsPossible.get(first).get(second).add(str); 
} 

再看看先得到正確的內ArrayList不必做一個大的搜索匹配的詞。