3

ボーグル ソルバーを作成していますが、コーディングのどこで問題が発生したのかわかりません。これが私がこれまでに持っているものです：

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;
}

}

実行されるだけで、単語が見つかったと言うことはめったにありません。また、実行には非常に長い時間がかかります。約 1 時間です。自分の間違いがどこにあるのかわからないし、どこで間違えたかもわからない。どんな助けでも素晴らしいでしょう！

4

2 に答える 2

3

これにより、10、11、12、13、14などのすべての文字の単語を検索する組み合わせ爆発が発生します。word電流が辞書内のどの単語の接頭辞でもなくなったら、検索を削除するコードを追加する必要があります。

また、単語のリストにArrayListを使用しています。でフラットリストを検索すると、wordsPossible.contains(word)毎回リスト全体がスキャンされるため、非常に時間がかかります。平均すると、80,000語の辞書に対して40,000回の反復が必要になります。

より適切なデータ構造は、ツリーセットまたはプレフィックスツリー（またはトライ）です。どちらも高速ルックアップ用に最適化されており、上記のプレフィックスチェックに最適です。ツリーセットの場合、ceiling（）メソッドが便利です。Javaでの試行については、この質問を参照してください。

于 2012-12-03T22:24:41.003 に答える
0

その ArrayList は巨大になるでしょう! たとえば、ArrayList<ArrayList<ArrayList<String>>> 最初のインデックスが単語の最初の文字で、2 番目のインデックスが単語の 2 番目の文字であるような、より適切なデータ構造を使用してみてください。

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次に、大規模な検索を行うことなく、最初に正しい内部に到達することによって、一致する単語を検索します。

于 2012-12-03T22:25:40.697 に答える