要素のすべての可能な順列を把握するためのアルゴリズムを設計するにはどうすればよいですか？

要求に応じて、これが私が数時間いじくり回した後に思いついた解決策です。これは、作業を行うメインクラス、Wordクラス、および辞書ヘルプクラスの3つの主要部分で構成されています。（ファイルから単語リストを読み取るためのローダーもあります。）

ローダ：

public class Loader {

    public List<String> load(String fileName) throws IOException {
        List<String> wordList = new ArrayList<>();
        InputStream is = getClass().getClassLoader().getResourceAsStream(fileName);
        BufferedReader br = new BufferedReader(new InputStreamReader(is));

        String currentLine = br.readLine();
        while (currentLine != null) {
            if (!"".equals(currentLine)) {
                for (String word : currentLine.split(" ")) {
                    wordList.add(word);
                }
            }
            currentLine = br.readLine();
        }

        br.close();

        return wordList;
    }
}

語：

public class Word {
    private final String word;
    private final Character[] characters;

    public Word(String word) {
        this.word = word;
        characters = new Character[3];
        characters[0] = word.charAt(0);
        characters[1] = word.charAt(1);
        characters[2] = word.charAt(2);
    }

    public String getWord() {
        return word;
    }

    public Character getCharacter(int index) {
        return characters[index];
    }

    @Override
    public String toString() {
        return getWord();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Word word1 = (Word) o;

        if (word != null ? !word.equals(word1.word) : word1.word != null) return false;
        // Probably incorrect - comparing Object[] arrays with Arrays.equals
        return Arrays.equals(characters, word1.characters);
    }

    @Override
    public int hashCode() {
        int result = word != null ? word.hashCode() : 0;
        result = 31 * result + Arrays.hashCode(characters);
        return result;
    }
}

Wordクラスの主な理由は、構成文字を事前に計算することです。

辞書：

public class Dictionary {
    private final List<Word> wordList;
    private final Set<Word> wordSet;
    private final Map<Character, List<Word>> firstLetterMap;
    private final Map<Character, Word[]> firstLetterArrayMap;


    public Dictionary(List<String> wordList) {
        this.wordList = wordList.stream().map(Word::new).collect(toList());
        this.wordSet = new HashSet<>();
        wordSet.addAll(this.wordList);

        this.firstLetterMap = this.wordList.stream()
                .collect(groupingBy(
                        w -> w.getCharacter(0)
                ));
        this.firstLetterArrayMap = new ConcurrentHashMap<>();
        for (Map.Entry<Character, List<Word>> entry : firstLetterMap.entrySet()) {
            Word[] ws = new Word[entry.getValue().size()];
            entry.getValue().toArray(ws);
            firstLetterArrayMap.put(entry.getKey(), ws);
        }
    }

    public List<Word> getWords() {
        return new ArrayList<>(wordList);
    }

    public Word[] getWordsArray(Character c) {
        return Optional.ofNullable(firstLetterArrayMap.get(c)).orElseGet(() -> new Word[0]);
    }

    public boolean isValidWord(Word word) {
        return wordSet.contains(word);
    }
}

ここで説明することはあまりありません。単語リストには、最初の文字に基づいて単語を検索するためのマップが含まれています。また、単語を検証するためのメソッドもあります。

メインプログラム：

public class Tester {

    private final Loader loader;

    public Tester() {
        loader = new Loader();
    }

    public static void main(String[] args) {
        new Tester().run2();
    }

    public void run2() {

        Map<Set<Word>, String> validBoards = new ConcurrentHashMap<>();
        try {
            List<String> words = loader.load("scrabble-3-letter.txt");
            Dictionary dictionary = new Dictionary(words);
            List<Word> allWords = dictionary.getWords();
            Map<Word, String> checked = new ConcurrentHashMap<>();


            System.out.println("Start search...");
            long start = System.currentTimeMillis();

            allWords.parallelStream().forEach(w -> {
                checked.put(w, "");
                Word[] list1 = dictionary.getWordsArray(w.getCharacter(0));
                Word[] list2 = dictionary.getWordsArray(w.getCharacter(1));
                Word[] list3 = dictionary.getWordsArray(w.getCharacter(2));
                for (int i = 0; i < list1.length; ++i) {
                    Word w1 = list1[i];
                    if (checked.get(w1) != null) {
                        continue;
                    }
                    for (int j = 0; j < list2.length; ++j) {
                        Word w2 = list2[j];
                        for (int k = 0; k < list3.length; ++k) {
                            Word w3 = list3[k];
                            if (evaluate(w1, w2, w3, dictionary)) {
                                validBoards.put(new HashSet<>(Arrays.asList(w1, w2, w3)), "");
                            }
                        }
                    }
                }
            });
            long end = System.currentTimeMillis();

            System.out.println("Found " + validBoards.size() + " unique boards in " + (end - start) + " ms");

            String forPrint = validBoards.keySet().stream()
                    .map(ArrayList::new)
                    .map(this::boardToString)
                    .collect(Collectors.joining("\n"));
            writeToFile(forPrint, ".\\scrabble-sudoku-output.txt");

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void writeToFile(String data, String fileName) throws IOException {
        BufferedWriter writer = new BufferedWriter(new FileWriter(fileName));
        writer.write(data);

        writer.close();

    }

    private boolean evaluate(Word first, Word second, Word third, Dictionary dictionary) {
        Word firstV = buildVerticalWord(first, second, third, 0);
        Word secondV = buildVerticalWord(first, second, third, 1);
        Word thirdV = buildVerticalWord(first, second, third, 2);

        return dictionary.isValidWord(first) && dictionary.isValidWord(second) && dictionary.isValidWord(third)
                && dictionary.isValidWord(firstV) && dictionary.isValidWord(secondV) && dictionary.isValidWord(thirdV)
                && boardUniqueness(first, second, third, firstV, secondV, thirdV);
    }

    private boolean boardUniqueness(Word w1, Word w2, Word w3, Word w4, Word w5, Word w6) {
        Set<Word> checkDup = new HashSet<>();
        checkDup.add(w1);
        checkDup.add(w2);
        checkDup.add(w3);
        checkDup.add(w4);
        checkDup.add(w5);
        checkDup.add(w6);
        return checkDup.size() == 6;
    }

    private static Word buildVerticalWord(Word first, Word second, Word third, int index) {
        return new Word("" + first.getCharacter(index) + second.getCharacter(index) + third.getCharacter(index));
    }

    private String boardToString(List<Word> board) {
        StringBuilder sb = new StringBuilder();
        List<Word> sortedWords = new ArrayList<>(board);
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 0));
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 1));
        sortedWords.add(buildVerticalWord(board.get(0), board.get(1), board.get(2), 2));
        sortedWords.sort(Comparator.comparing(Word::getWord));
        sb.append(sortedWords.stream().map(Word::getWord).collect(Collectors.joining(", ")));
        return sb.toString();
    }
}

これは2回目の試行です（したがって、run2（））。1つ目はブルートフォース攻撃で、完全なリストから1行に1つの単語を選択し、垂直方向の単語が有効かどうかを確認しました。言うまでもなく、このアプローチはあまり効率的ではありませんでした。（私のリストには1347語が含まれているので、2474829630の組み合わせを確認する必要があります。）

組み合わせの数を減らすことを目的とした2番目のアプローチは、有効である可能性のある行の組み合わせのみをチェックすることです。

これがその仕組みです。単語の完全なリストを繰り返し処理します。各反復で、選択された単語「w」が最初の列になります。次に、wの最初、2番目、3番目の文字に基づいて可能な行の3つのリストを除外します。

これらの縮小リストは完全なリストよりもはるかに小さく、これらのリストを徹底的に検索します。これらの組み合わせのそれぞれについて、最初の列は同じままです。

評価では、6つの単語のそれぞれが有効であり、実際に6つの一意の単語があることを確認します。有効な組み合わせはすべて、セットとしてマップに保存されます。セットは重複を上書きする必要があり、同時実行にはマップが必要です。

最後のステップはファイルに書き込むことです。これは見事に機能していないようですので、私はそれを変更することを検討します。

ループでは、どの単語wを使用したかを追跡します。w1がwと同じ場合は、スキップします。これは、6つの単語の（有効な）組み合わせごとに2つの可能な形式があるためです。

A A A
B B B
C C C

と同じです

A B C
A B C
A B C

編集

すべての解決策を見つけるには時間がかかりますが、いくつかの解決策を見つけることは迅速に行うことができます。追加の2行のコードが必要です。

辞書コンストラクターで、マップされた後、プライマリ単語リストにシャッフルを追加します。

// ....
public Dictionary(List<String> wordList) {
    this.wordList = wordList.stream().map(Word::new).collect(toList());
    Collections.shuffle(this.wordList); // Shuffle here
    this.wordSet = new HashSet<>();
    wordSet.addAll(this.wordList);
// ....

これにより、後続のすべての単語リストとコレクションがシャッフルされ、新しい実行がそれぞれ一意になります。

プログラムのメインループのrun2（）で、有効なボードを見つけるときに、最も内側のループにreturnステートメントを追加します。

                    if (evaluate(w1, w2, w3, dictionary)) {
                        validBoards.put(new HashSet<>(Arrays.asList(w1, w2, w3)), "");
                        return; // Return here to end search
                    }

それがリターンであり、他のブレークではない理由は、ラムダ内にいるため（外側のループはStream.forEach（））、ラムダ式を終了するためです。

私の期待は、この変更で1つの有効なボードを見つけることでしたが、何らかの理由で、代わりに約1310（正確な数は異なります）の結果になります。停止する前に、一度完全な外側のループを終了するようです。

ハッピーホリデー！