I’ve previously spent some time implementing wordle, and since then enjoyed watching others discuss how to solve the game using programming, especially the solutions based on information theory.
Naturally, I was interested in trying them out, given my own implementation of the game. Let me show you how I used SQL to solve Wordle, using maths from information theory.
Briefly, Wordle is a daily word game run by the New York Times, where we need to find a secret 5-letter word within 6 attempts. You may know this game from the American/Dutch TV game Lingo, or the French TV game Motus. To guide us, each character of each attempt is scored as either perfect (right letter, right position) = “🟩”, or wrong position (letter is used but elsewhere) = “🟨”, or a miss (character not used at all in the word) = “⬜” (or “⬛” depending on OS).
In the past, I’ve been interested in this game enough to publish my own from-scratch implementation, using literate-programming and BDD/TDD to demonstrate traceability from requirements all the way to tests. Good stuff.
Keeping an eye on the discussions around Wordle, I noticed solutions like 3Blue1Brown’s video, and more recently this paper from Binghamton, both converging on the same approaches.
I can’t do these sources justice, but I’d summarize the key idea this way: Both rely on statistics, choosing guesses by calculating a metric using the information theory concept of “entropy”, then picking the guess word that maximizes that metric.
Entropy here is the “distinguishing power” of a guess, its capacity to reduce the size of the possible answer pool, computing how much “information” we’d expect to learn once we reveal the score of the guess word. The more the answer pool is cut down by a guess, the better it is. Entropy formalizes this idea into a single number with convenient properties.
So, with my existing game implementation, I considered how I could implement this.
The first thing that occurs to me is that we can do the heavy lifting ahead of time, precomputing all the scores of every possible guess against every possible answer, and storing that result. Conceptually, this is kind of a rainbow table1: brute-forcing an expensive computation so we can reverse it later, sacrificing a lot of storage along the way.
How much storage are we talking though? Let’s consider: the dictionary of accepted word-guesses (downloaded as part of implementing the game long ago) is 12897 words long, simplifying it down to 10000, that’s 10k = 104. Similarly, the answers dictionary has 2315 words2, so around 2k = 2.103.
Crossing all guesses against all answers, there would be approximately 104 . 2.103 = 2.107 individual guess/answer combos. We’re talking 20 million rows: database-size-wise, that’s nothing, barely an inconvenience!
For each row, let’s imagine we (wastefully) store the 5 characters (as ASCII, 5 chars at 1 byte each) of each guess + same for answer, that’s 10 bytes per row, plus the size of the score, which is Unicode (experimentally measured) at 4 bytes per character, that’s another 5 * 4 = 20 bytes. So each row would be 30 bytes if we store everything as is without optimizing. That’s 30 . 2.107 = 6.108 bytes, around 572MB. Manageable! Though very unoptimized (storing full words and scores each time is wasteful, more on that later).
Half a Gig upper bound for storage is fine, let’s store all this in sqlite, and see how far we can go with it!
So here I go, creating SQL tables to store words, scores etc, then writing a script from my old wordle implementation to generate each guess/answer/score combo, storing the lot.
To avoid some wasting of storage, we’ll dump our dictionaries of words and Unicode scores into some tables first, then we can manipulate row numbers instead of expensive Unicode chars.
First, we store all the accepted guess words:
-- Superset of all valid Wordle words = accepted guesses
CREATE TABLE word_index (
wordidx INT,
word TEXT
);
We also store the list of actual answers, which are just indices in the previous word_index table
-- Wordle answers = subset of accepted guesses, referencing word_index
CREATE TABLE answer_index (
wordidx INT,
FOREIGN KEY (wordidx) REFERENCES word_index (wordidx)
);
word_index (guesses) table
With guess and answers, next we have all the possible scores:
-- Wordle scores (Unicode 5 letter strings),
-- 3 possibilities = 3^5 = 243 entries
CREATE TABLE score_index (
scoreidx INT,
score TEXT
);
We note that sqlite’s data type system does not specify the size of the counters, or the size of the text storage.
So we can’t do the obvious storage optimization of using the knowledge that score indexes are bounded to be << 256, hence could be represented with a uint8.
A more elaborate tool, like Postgres, would let us refine the type, but sqlite is performing very adequately so far, we don’t need to break out bigger guns.
So, we have tables in which to store individual entities, next we want our “rainbow table”:
-- Pre-computed score of a guess (word) against an answer (word), all via index
CREATE TABLE score (
guessidx INT,
answeridx INT,
scoreidx INT,
FOREIGN KEY (guessidx) REFERENCES word_index (wordidx),
FOREIGN KEY (answeridx) REFERENCES answer_index (wordidx),
FOREIGN KEY (scoreidx) REFERENCES score_index (scoreidx)
);
So now, to populate the database, we flip to Python, writing a script that roughly amounts to:
from literate_wordle.guess import score_guess
from literate_wordle.words import GUESS_WORDS, ANSWER_WORDS
db = sqlite3.connect("wordle_solve.db")
# Simplified: real code inserts indices, not raw strings
for guess in GUESS_WORDS:
for answer in ANSWER_WORDS:
score = score_guess(guess, answer)
db.execute("INSERT INTO score (guess, answer, score)"
"VALUES (?, ?, ?)",
(guess, answer, score))
The result is a sqlite database file of 472MB, which, while surprisingly approaching our theoretical worst-case file size, stays usable! If this were for production use, I would try to investigate ways to shave off that storage, but as it is, I am fine with this.
As an aside: Guided by my previous foray, I tried importing the same database in DuckDB, to select these specific types, like UINT8, saving storage and widening the available query language.
But the resulting database file grew to 2GB, 4 times as big as the sqlite file.
Likely due to indexes being set up for each primary key by default?
Oh well, I dropped DuckDB for this: sqlite is plenty, and I didn’t really need more!
So we have filled our database, we’re ready to play. Let’s practice some queries to warm up the SQL muscles.
SELECT wordidx
FROM word_index
WHERE word = 'crane';
-- 2368
SELECT scoreidx
FROM score_index
WHERE score = '⬜⬜🟨🟩⬜';
-- 15
SELECT COUNT(answeridx)
FROM score
WHERE guessidx = 2368
AND scoreidx = 15;
-- 20
Of course, we don’t want to have to specify index by hand!
SELECT COUNT(s.answeridx)
FROM score AS s
INNER JOIN word_index AS w
ON s.guessidx = w.wordidx
INNER JOIN score_index AS sc
ON s.scoreidx = sc.scoreidx
WHERE w.word = 'crane' AND sc.score = '⬜⬜🟨🟩⬜';
-- 20
And of course, let’s see those answers, not just indexes!
-- Show me the answer word
SELECT answer_wi.word
-- From the real word table
FROM word_index AS answer_wi
-- Which we find from the answers (index) table
INNER JOIN answer_index AS answer_ai
ON answer_wi.wordidx = answer_ai.wordidx
-- That we find from scores table
INNER JOIN score AS s
ON answer_ai.wordidx = s.answeridx
-- back to using our earlier score query:
INNER JOIN word_index AS w
ON s.guessidx = w.wordidx
INNER JOIN score_index AS sc
ON s.scoreidx = sc.scoreidx
WHERE w.word = 'crane' AND sc.score = '⬜⬜🟨🟩⬜';
-- aging
-- agony
-- along
-- among
-- aping
-- daunt
-- faint
-- fanny
-- fauna
-- gaunt
-- haunt
-- jaunt
-- nanny
-- paint
-- saint
-- sauna
-- taint
-- taunt
-- tawny
-- vaunt
It’s around this point that I realized that in order to solve Wordle, one may never need to leave the comfort of SQL to generate good answers! Why not push a SQL-only solution!?
Let’s first look at the maths behind these solvers, see what the trick is.
As mentioned before, solving Wordle means minimizing the number of guesses, which we’ll do by picking the best guess words, calculating a metric that a good guess word would maximize. Now, let’s retrace the path of others, and show how to use information theory. Again, please do watch the 3Blue1Brown video, which is likely a better support for learning.
In general, a good guess word would tell us “much information” about the answer, which we can imagine as “how many possible answers have been invalidated by the reveal of this guess’s score”, whatever the score turns out to be. The more possible answers eliminated, the better the guess was. Since we don’t know the score ahead of time for a given guess (it’s only revealed when we “play” that guess), we’ll need to consider every possible score a guess could have, and compute, in aggregate, how much these different score-outcomes tell us (by affecting how many answers remain after, for each possible score-outcome) for that specific guess. So there are two phases to this calculation for each possible guess: first we measure the information-learned metric for each specific score, then we aggregate that metric across all the scores the guess can end up in, weighted by how likely the score is to occur.
Some notation: For the next few sections, we’ll assume we’re examining a specific candidate guess word, and want to calculate its expected-information-gained metric, to compare it to other possible guesses to play.
Of all the possible scores this guess can have, the probability that the score s occurs, is described as:
P[s] = number of answers that match this guess-score-combo / total number of possible answers at this point. And of course, P[s] sums up to 1 if we check all the possible values of s.
So if the answer pool started out as 2000 possible answers, and the guess we use scores s, and that guess/score matches 100 possible (remaining) answers, then P[s] = 100 / 2000 = 1/20 = 0.05 = 5%.
The first key idea is how to compute the “amount of information” learned on a specific guess, for a specific score outcome. We introduce “entropy”, a unit of information, measured in bits (or Shannon).
Entropy measures information gained by describing how much the number of possible outcomes changed after an event. Specifically, how many “halvings” of the possibility-space, aka the halvings of the answer list, that happened when revealing a score. 1 bit means we halved the answer pool, 2 bits means we quartered it (regardless of the pool size before or after, we’re measuring ratios).
In numbers, we calculate entropy as I = - log2(P[s]).
Taking the example from above, then I = - log2(P[s]) = - log2(100 / 2000) = -log2(1/20) = 4.32192809489. Interpreting this number, this score cut the answer pool in half 4 times (and a bit). That’s the metric for a single guess/single score.
For the second key idea, we now want to aggregate this information metric, to get the “average” amount of information for all possible scores that our guess could end up scoring.
So we’re trying to aggregate a metric that depends on the score, but each score is not equally likely to occur. In the probability toolbag, that’s the expectancy.
The expectancy of a metric I is defined as E[I] = 𝚺 (P[s] * I), that is, the weighted average of the metric according to its probability.
Injecting in the definition of I from above, we get: E[I] = 𝚺 (P[s] * - log2(P[s])) = - Σ (P[s] * log₂(P[s])).
Let’s translate that to Python pseudocode for illustration purposes:
entropy: dict[str, float] = {}
for guess in GUESS_WORDS:
entropy_of_guess = 0
for score in POSSIBLE_SCORES:
num_answers = len(answers_matching(guess, score))
proba_score = num_answers / len(ANSWER_WORDS) # P[s]
if proba_score > 0: # log2(0) undefined: skip
entropy_of_guess -= proba_score * log2(proba_score)
entropy[guess] = entropy_of_guess
# Now find guess that maximizes entropy[guess]
That’s it, that’s our metric.
Let’s translate it to SQL. We’ll use sub-queries, which we’ll inject via CTE. Starting with the number of total answers:
SELECT COUNT(answeridx) AS num_answers
FROM answer_index;
Next, we’ll need the count of answers per guess/score:
SELECT
guessidx,
scoreidx,
COUNT(*) AS num_occur
FROM score
GROUP BY guessidx, scoreidx;
And then we bring this together to find the top 10 opener guess words:
WITH
-- Count of all answers
answer_count AS (
SELECT COUNT(*) AS num_answers FROM answer_index
),
-- Count how many answers for each guess x score combo
answers_per_guess_score AS (
SELECT
guessidx,
scoreidx,
COUNT(*) AS num_occur
FROM score
GROUP BY guessidx, scoreidx
)
-- Actual compute to get best guess:
-- Maximizing entropy ("surprise") per guess
-- for all scores and their count-of-answers
SELECT
w.word AS guess,
-- entropy = - Σ [P[s] * log₂(P[s])]
ROUND(
-SUM(
(ags.num_occur / CAST(ac.num_answers AS REAL)) -- P[s]
*
LOG2(ags.num_occur / CAST(ac.num_answers AS REAL)) -- log2(P[s])
), 4) AS entropy,
ac.num_answers AS answer_pool_size
FROM answers_per_guess_score AS ags
INNER JOIN word_index AS w
ON ags.guessidx = w.wordidx
-- Single row table, crossjoin to get the variable in
CROSS JOIN answer_count AS ac
GROUP BY ags.guessidx -- aggregate all scores of each guess
ORDER BY entropy DESC
LIMIT 10;
-- soare|5.8860|2315
-- roate|5.8828|2315
-- raise|5.8779|2315
-- raile|5.8657|2315
-- reast|5.8655|2315
-- slate|5.8558|2315
-- crate|5.8349|2315
-- salet|5.8346|2315
-- irate|5.8314|2315
-- trace|5.8305|2315
We can intuitively make sense of these “best guess” picks: a good guess word will likely explore many vowels, justifying the value of “soare”.
I found it useful to return the size of the answer pool, just in case: Currently it’s the whole dictionary (as expected before playing the first guess), but as we’ll play guesses, the pool of answers that are compatible given our previous guesses and scores will shrink. At some point, when the pool is less than 10 words, we may want to just lock-in a word!
So we have the theoretically best opener words (for these particular dictionaries! I believe the New York Times changed the dictionaries a tad when they took over tenancy of the game). Wonderful.
Next, we need to know how to pick our second guess after first guess was played, revealing its score.
We still want to run the same entropy calculation for all guesses, and maximize that number. The only thing that has changed is that we revealed the score of the previous guess, so the pool of valid answers to pick from is smaller.
So we first want to compute the pool of remaining answers given the guess we played. This is something we did before in Code Snippet 9. So the overall query is similar to our previous one, but with some early CTE clauses to account for the remaining answer pool:
-- Find the best next guess, given a previous scored guess
-- First, compute answers compatible with first guess' received score:
WITH remaining_answers AS (
SELECT s.answeridx
FROM score AS s
INNER JOIN word_index AS w
ON s.guessidx = w.wordidx
INNER JOIN score_index AS sc
ON s.scoreidx = sc.scoreidx
WHERE w.word = 'crane' AND sc.score = '⬜⬜🟨🟩⬜'
),
-- Count answers for each guess x score combo (of remaining answer pool)
answers_per_guess_score AS (
SELECT
s.guessidx,
s.scoreidx,
COUNT(*) AS num_occur
FROM score AS s
INNER JOIN remaining_answers AS ra -- from smaller pool
ON s.answeridx = ra.answeridx
GROUP BY s.guessidx, s.scoreidx
),
-- Total number of remaining answers
answer_count AS (
SELECT COUNT(*) AS num_answers
FROM remaining_answers
)
-- Actual compute to get best guess:
SELECT
w.word AS guess,
ROUND(
-SUM(
(ags.num_occur / CAST(ac.num_answers AS REAL))
*
LOG2(ags.num_occur / CAST(ac.num_answers AS REAL))
), 4) AS entropy,
ac.num_answers AS answer_pool_size
FROM answers_per_guess_score AS ags
INNER JOIN word_index AS w
ON ags.guessidx = w.wordidx
CROSS JOIN answer_count AS ac
GROUP BY ags.guessidx
ORDER BY entropy DESC
LIMIT 10;
-- tousy|3.3414|20
-- thigs|3.3087|20
-- tying|3.2842|20
-- tings|3.2842|20
-- tipsy|3.2660|20
-- twigs|3.2464|20
-- tough|3.2087|20
-- tumpy|3.2037|20
-- tifos|3.2037|20
-- thugs|3.2037|20
Notice the value of the answer pool size before we play that second guess: after only scoring the first guess, the pool of answers is already down to 20.
And then, the average entropy of these second guesses is around 3 bits, which means we expect “3 halvings” of the answer pool, cutting by 23 = divide by 8 its size. That second guess would, on average, leave only 20 / 8 = 2 and a half answers left, after the second guess is played.
The next question is how to extend the solution to show how to get 2 or more scored guesses, beyond the one we just showed.
Turns out, we can merge lists of answers via INTERSECT, so we fall back on a well understood pattern:
WITH remaining_answers1 AS (
SELECT s.answeridx
FROM score AS s
INNER JOIN word_index AS w
ON s.guessidx = w.wordidx
INNER JOIN score_index AS sc
ON s.scoreidx = sc.scoreidx
WHERE w.word = 'soare' AND sc.score = '⬜⬜⬜⬜⬜'
),
-- Second set of answers
remaining_answers2 AS (
SELECT s.answeridx
FROM score AS s
INNER JOIN word_index AS w
ON s.guessidx = w.wordidx
INNER JOIN score_index AS sc
ON s.scoreidx = sc.scoreidx
WHERE w.word = 'dumpy' AND sc.score = '⬜🟨⬜⬜🟩'
),
-- Then we cross-reference all these.
remaining_answers AS (
SELECT answeridx FROM remaining_answers1
INTERSECT
SELECT answeridx FROM remaining_answers2
-- Can add more via INTERSECT remaining_answer3 (etc)
)
-- Now back to the same old queries after this
-- Elided for brevity
The rest of the query is the same all over, cut because it’s boring to repeat.
We’ve given new life to old Wordle scoring code by brute-forcing scoring, dumping it to a sqlite database, playing with SQL queries to find what answers fit a guess and its score. We then took a trip down information theory to find creative ways to discover the solution, and then came back to SQL to calculate these metrics, demonstrating the selection of good guess candidates.
At the same time, we chose NOT to take the time to optimize these queries, like by designing proper search indexes, nor did we refine our SQL query order using tools like EXPLAIN ANALYZE. Nor did we package the resulting solver, it’s just text queries and a hand-rolled database file: we were in research mode, not development!
I’m still glad I was able to breathe fresh life into old code, and that, through SQL, I found my own twist to the information theory idea others have laid out before. In particular, I’ve learned a couple of tricks in SQL this time around, like cross-joining a single-row table to inject a pre-computed variable from a CTE, and the subtleties of making a complex INNER JOIN’s ON clause, compared to moving that restriction to the WHERE side.
All this reminds me there’s a whole depth to SQL I have yet to play with, around the balance of performance and maintainability. For instance, I haven’t started making views in SQL to simplify using these tables, or maybe using stored procedures to simplify scoring queries. All good things for another day!
Yes, a rainbow table is about encryption/hashing, whatever, I found the similarity inspiring. ↩︎
I’ve intentionally simplified the problem by separating the answer-solutions subset from the accepted guesses. It’s reduced the answers pool from 12k (all possible guesses can be answers) to 2k, less than one order of magnitude. If you feel like getting a more authentic computation, you’d just use the guesses dictionary (superset of answers/solutions) twice, instead of using the smaller “answers” one, and wait for the slower queries. Exercise left to the reader… ↩︎