How to design an algorithm to figure out all possible permutations of elements?

Question

I am trying to build a Sudoku game with letters instead of numbers. There will be an empty box like the following:

Each little box will be filled with a letter such that all horizontal and all vertical letters form words. To help the user, I will give them 6 words which will work, but they have to figure out how to arrange the 6 words. An example of a correctly completed box:

For this version of Sudoku made for scrabble players, oxo is a valid word (I am using a txt file for list of valid words).

The problem I have is this: How can the program figure out all 3 letter words that fit together horizontally and vertically? (I will choose 6 words from this subset to output to user).

The txt file is stored in a set, so each word is a string element. I thought about looping through all words in the set, and breaking each word into an array of char. But this seems like a long shot. Do you have any ideas about how to generate all possible solutions?

Answer 1

As requested, here is the solution I came up with after a few hours of tinkering. It comprises of three main parts, the main class doing the work, a Word class and a Dictionary help class. (There is also a Loader for reading the word list from file.)

Loader:

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

Word:

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

The primary reason for the Word class is to pre compute the constituent characters.

Dictionary:

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

Not much to explain here. It contains the word list a map to look up words based on their first letter. It also has a a method for validating a word.

Main program:

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

This is the second attempt (hence run2()). The first was brute force, picking one word per line from the full list and then checking if the vertical words were valid. Needless to say, this approach was not very efficient. (My list contains 1347 words so that's 2474829630 combinations to check.)

The second approach, with the goal to reduce the number of combinations, is to only check combinations of rows which have a chance of being valid.

This is how it works: We iterate over the full list of words. In each iteration, the selected word, 'w', is the first column. We then filter out three lists of possible rows based on the first, second and third letter of w.

These reduced lists are vastly smaller than the full list and we do an exhaustive search on these lists. For each of these combinations, the first column remains the same.

Evaluation checks that each of the 6 words is valid and that there are indeed 6 unique words. Any valid combination is saved as a Set, in a Map. The Set should make any duplicates be overwritten and the Map is necessary for concurrency.

Last step is to write to file. This seems to not work brilliantly so I would look into changing that.

In the loop, we keep track of which words, w, we have used. If w1 is the same as w, we skip it. This is because each (valid) combination of 6 words has two possible forms.

A A A
B B B
C C C

is the same as

A B C
A B C
A B C

EDIT

Finding all solutions takes time, but finding some solution can be done quickly. It requires two additional lines of code.

In the Dictionary constructor, add a shuffle on the primary word list after it has been mapped:

// ....
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);
// ....

This will make all subsequent word lists and collections shuffled, making each new run unique.

In the main loop of the program, in run2(), add a a return statement in the innermost loop when finding a valid board:

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

The reason why it's a return and not some other break is because we're inside a lambda (the outer loop is a Stream.forEach()) so this will exit the lambda expression.

My expectation was to find one (1) valid board with this change, however, for some reason I end up with around 1310 (exact number varies) results instead. It seems it will finish the complete outer loop once before stopping.

Happy holidays!