CareerCup

Multiple solutions exist (based on the dictionary used), e.g.:
[fever, queue, zoo, mat, speaker, person, backgammon, house, wax, jury, diligent]

public static void fillInWords(String[] words) {
    Set<String> dict = generateDict();
    Set<Character> usedLetters = new HashSet<>();

    if (fillInWords(words, 0, "", dict, usedLetters)) {
        System.out.println(Arrays.toString(words));
    } else {
        System.out.println("No solution exists.");
    }
}

private static boolean fillInWords(String[] words, int wordIdx, String candidate,
                                   Set<String> dict, Set<Character> usedLetters) {
    // Final word completed
    if (wordIdx == words.length) return true;

    // Construct word
    StringBuilder sb = new StringBuilder(candidate);
    for (int i = sb.length(); i < words[wordIdx].length(); i++) {
        char currChar = words[wordIdx].charAt(i);

        // Fill in a blank and recurse or simply add current char to StringBuilder
        if (currChar == '*') {
            for (char c = 'a'; c <= 'z'; c++) {
                if (!usedLetters.contains(c)) {
                    sb.append(c);
                    usedLetters.add(c);

                    if (fillInWords(words, wordIdx, sb.toString(), dict, usedLetters)) {
                        return true;
                    }

                    // Backtrack
                    sb.setLength(sb.length() - 1);
                    usedLetters.remove(c);
                }
            }

            // No letter fits
            return false;
        } else {
            sb.append(currChar);
        }
    }
    candidate = sb.toString();

    // Test completed word
    if (candidate.length() == words[wordIdx].length() && dict.contains(candidate)) {
        if (fillInWords(words, wordIdx + 1, "", dict, usedLetters)) {
            words[wordIdx] = candidate;
            return true;
        }
    }
    return false;
}