From @computer_goblin's list of 46659 nine-letter words, the maximum number of letters covered by three words is
24: bockwurst exemplify Ghaznevid
If you instead consider only the subset of 43098 words that do not contain a capital letter, the maximum is
23: bedworthy magnaflux quickstep
I found both sets by solving a maximum coverage problem via integer linear programming, with a binary decision variable $x_w$ to indicate whether word $w$ is selected and a binary decision variable $y_\ell$ to indicate whether letter $\ell$ is covered. Let $W_\ell$ be the set of words that contain letter $\ell$. The problem is to maximize $\sum_\ell y_\ell$ subject to
\begin{align}
\sum_w x_w &= 3 \tag1\label1 \\
y_\ell &\le \sum_{w\in W_\ell} x_w &&\text{for all $\ell$} \tag2\label2
\end{align}
Constraint \eqref{1} selects exactly three words.
Constraint \eqref{2} enforces the logical implication $y_\ell \implies \bigvee_{w\in W_\ell} x_w$. That is, if letter $\ell$ is covered, then some word $w$ that contains $\ell$ must be selected.
By request, here is more detail about the solution process.
Here's the SAS code I used, with more descriptive variable names SelectWord and CoverLetter instead of $x$ and $y$, respectively:
data words;
infile 'Nine Letter Words.txt';
input word $9.;
run;
proc optmodel;
/* declare parameters and read data */
set <str> WORDS;
read data words into WORDS=[word];
WORDS = setof {w in WORDS} lowcase(w);
set LETTERS = setof {k in 97..97+26-1} byte(k);
set <str> WORDS_l {LETTERS} init {};
str letterThis;
for {w in WORDS} do;
for {k in 1..length(w)} do;
letterThis = char(w,k);
WORDS_l[letterThis] = WORDS_l[letterThis] union {w};
end;
end;
/* SelectWord[w] = 1 if word w is selected; 0 otherwise */
var SelectWord {WORDS} binary;
/* CoverLetter[l] = 1 if letter l is covered; 0 otherwise */
var CoverLetter {LETTERS} binary;
/* maximize the number of letters covered */
max NumLettersCovered = sum {l in LETTERS} CoverLetter[l];
/* select exactly three words */
con Cardinality:
sum {w in WORDS} SelectWord[w] = 3;
/* if CoverLetter[l] = 1 then SelectWord[w] = 1 for some word w that contains letter l */
con LetterImpliesWord {l in LETTERS}:
CoverLetter[l] <= sum {w in WORDS_l[l]} SelectWord[w];
/* call MILP solver */
solve;
/* display selected words */
put ({w in WORDS: SelectWord[w].sol > 0.5});
quit;
And here is the resulting log:
NOTE: There were 46659 observations read from the data set WORK.WORDS.
NOTE: Problem generation will use 4 threads.
NOTE: The problem has 46683 variables (0 free, 0 fixed).
NOTE: The problem has 46683 binary and 0 integer variables.
NOTE: The problem has 27 linear constraints (26 LE, 1 EQ, 0 GE, 0 range).
NOTE: The problem has 390770 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The OPTMODEL presolver is disabled for linear problems.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 0 variables and 0 constraints.
NOTE: The MILP presolver removed 50163 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 46683 variables, 27 constraints, and 340607 constraint
coefficients.
NOTE: The MILP solver is called.
NOTE: The parallel Branch and Cut algorithm is used.
NOTE: The Branch and Cut algorithm is using up to 4 threads.
Node Active Sols BestInteger BestBound Gap Time
0 1 3 17.0000000 24.4187817 30.38% 0
NOTE: The MILP solver's symmetry detection found 31186 orbits. The largest orbit contains 28
variables.
0 1 4 20.0000000 24.4187817 18.10% 0
0 1 4 20.0000000 24.3769559 17.96% 0
0 1 4 20.0000000 24.3474535 17.86% 1
0 1 4 20.0000000 24.3403990 17.83% 1
0 1 4 20.0000000 24.3230216 17.77% 1
0 1 4 20.0000000 24.3018657 17.70% 1
0 1 5 21.0000000 24.3018657 13.59% 1
0 1 5 21.0000000 24.2928681 13.55% 1
0 1 5 21.0000000 24.2719184 13.48% 2
0 1 5 21.0000000 24.2474321 13.39% 2
0 1 5 21.0000000 24.2403600 13.37% 2
0 1 5 21.0000000 24.2295855 13.33% 3
0 1 5 21.0000000 24.2221405 13.30% 3
0 1 5 21.0000000 24.2185102 13.29% 3
0 1 5 21.0000000 24.2137198 13.27% 4
0 1 5 21.0000000 24.2114068 13.26% 4
0 1 5 21.0000000 24.2095593 13.26% 5
0 1 5 21.0000000 24.2045244 13.24% 6
0 1 5 21.0000000 24.2010946 13.23% 6
NOTE: The MILP solver added 13 cuts with 601893 cut coefficients at the root.
1 2 5 21.0000000 24.2010946 13.23% 7
9 8 6 23.0000000 24.1990119 4.95% 8
13 2 6 23.0000000 24.1519567 4.77% 8
58 0 7 24.0000000 24.0000000 0.00% 8
NOTE: Optimal.
NOTE: Objective = 24.
- The Node column reports the number of (non-root) branch-and-bound nodes in the search tree. Node 0 is the root.
- The Active column reports the number of active nodes in the tree.
- The Sols column reports the number of integer feasible solutions found so far.
- The BestInteger column reports the objective value of the best integer feasible solution found so far and is a lower bound on the global maximum.
- The BestBound column reports the best upper bound found so far; in particular, the first value 24.4187817 is the optimal objective value of the linear programming relaxation.
- The Gap column reports the optimality gap, that is, relative difference between these lower and upper bounds.
- The Time column reports the number of seconds that have elapsed.
In case it helps your understanding, here are the nonzero parts of an optimal LP solution that yields objective value 24.4187817 and satisfies all variable bounds and linear constraints but violates integrality:
w SelectWord[w]
backswamp 0.129019
backvelds 0.117597
blitzweed 0.033418
byproduct 0.096447
dezinkify 0.096024
egyptized 0.040609
fauxhawks 0.358714
fevertwig 0.055415
flapjacks 0.091794
flaxbirds 0.129442
ghaznavid 0.217851
jarovized 0.236464
jumpingly 0.435279
objectify 0.236464
pibloktoq 0.069797
prongbuck 0.046531
sixtyfold 0.032149
verklempt 0.090525
vetchworm 0.282149
whizbangs 0.141286
zygantrum 0.063029
l CoverLetter[l]
a 1.000000
b 1.000000
c 1.000000
d 1.000000
e 1.000000
f 1.000000
g 1.000000
h 1.000000
i 1.000000
j 1.000000
k 1.000000
l 1.000000
m 1.000000
n 1.000000
o 1.000000
p 1.000000
q 0.069797
r 1.000000
s 1.000000
t 1.000000
u 1.000000
v 1.000000
w 1.000000
x 0.520305
y 1.000000
z 0.828680
The branch-and-bound algorithm would choose some fractional variable, say SelectWord[backswamp] = 0.129019, and "branch" on that variable, that is, create two child nodes, one with SelectWord[backswamp] = 0 and one with SelectWord[backswamp] = 1. It would then choose one of those nodes, solve the LP, and repeat the process. Branch-and-bound is a recursive "divide and conquer" tree search, where the tree is dynamically constructed as needed.
Here are optimal results obtained with word.list as the dictionary.
The maximum coverage from the 26649 eleven-letter words is
24: buckjumping reflexivity schwarzlots
The maximum coverage from the 33679 ten-letter words is
24: buckjumped flyweights overtaxing
The maximum coverage from the 38318 nine-letter words is
24: buckjumps wildgrave zanthoxyl
The maximum coverage from all 264097 words is
25: exemplificative jawbreakingly soliloquized
which you can also achieve by restricting to words that have at most eleven letters:
25: buckjumped overflowing zanthoxyls
Here are optimal results obtained with word.list as the dictionary, excluding buckjump* and zanthoxyl*.
The maximum coverage from the eleven-letter words is
24: frankpledge objectivize sympathique
The maximum coverage from the ten-letter words is
24: jackknifed playwright squeezebox
The maximum coverage from the nine-letter words is
23: foxgloves whipjacks zygantrum
The maximum coverage from all words is
25: exemplificative hydrogenizes kabeljouw
which you can also achieve by restricting to words that have at most eleven letters:
25: jumboizing paddywhacks reflexivity
