NYT "Letter Boxed" solver in C++
My wife and I regularly solve the NYT crossword in the app.
Lately it's been trying to get me to solve a puzzle called "Letter Boxed".
In this puzzle, there are 12 letters arranged with 3 on each side of a square. Valid words have to be made from the letters, with the additional constraint that two consecutive letters may not be on the same side of the square. For example if the edges are "xoy", "tws", "apv" and "kri" then "air" is not a valid word because the consecutive letters "ir" come from the same side. "vow" is. The last constraint is that each consecutive word starts with the last letter of the previous word, so "vow" can be followed by "wok" but not "sat". (Words of any length are permitted, not just 3 letters)
There is no particular scoring to the game, though you're suggested to "try to solve it in # words"; you can also view the previous day's suggested solution.
To me, it seems that the best answer is in the fewest words, with ties broken by the fewest number of characters.
The following program (which assumes that there's a standard unix-style dictionary at /usr/share/dict/words) can find what appear to be "optimal" solutions in only a few milliseconds. Simply supply it with the 12 letters as the first commandline argument, and it will perform a breadth-first search (BFS) with up to 5 words in length. Each candidate printed is better scoring (shorter) than the previous one, so the last line is the best score.
$ ./a.out xoytwsavpkri 228 candidate words proviso - oaks - sixty - yaw provisos - sixty - yaw - wk vow - warps - sixty - yak Checked 3027570 sequences
I originally wrote a program in Python, but memory usage was high and speed was low. This version uses an efficient structure where each word is reduced to a 32-bit quantity that tracks the letters present, the word length, and the word's terminal character. A particular game play is characterized by a fixed-size data structure that includes the characters used so far, the number of words, the number of total characters, and an array of up to 5 words. The deque is initialized with one entry for each possible word. In the main loop, the item is taken from the front of the deque. Then, based on the terminal letter of the last word played it tries each word starting with that letter. If this potential solution is not lower-scoring than the best one, then it stops evaluating. Otherwise, if this word completes the puzzle, the solution is printed and the best known score values are updated. Otherwise, this puzzle state is added to the end of the deque. The program loops until all possibilities have been evaluated.
A dynamic-programming approach would probably beat the BFS but BFS is quite fast enough for the published puzzles I've solved. It might also be possible to work from both ends towards the middle.
I don't have enough experience with the puzzle to know if 5 words always suffice for published puzzles, but it seems likely. The two real puzzles I have tried have 2-word solutions from this program (13 characters, the minimum possible length for 2 words), while they were suggested to be solvable in 5 and 6 steps.
When it comes to randomly selected puzzles, there are possible boards for which I find a best answer of 7 words (using a modified version of the program)
knezcuvamybx 68 candidate words zany - yak - kc - can - numb - beaux - xv 7/23 zany - ye - exec - cab - bevy - yuk - km 7/22 zany - yuk - km - me - eve - exec - cab 7/21 Checked 3516880 sequences
and other sequences which have no solutions up to 7 words and use a lot of RAM and time before giving no solution (11GB peak resident size, 16 seconds):
mtijacfshpwk 194 candidate words Checked 636279365 sequences
I didn't go full dynamic-programming but I did track the best way to each each of the 12*4096 states and stop recursing if the new candidate doesn't reach a known state faster. This runs much faster and uses less memory; the 11GB & 16s example with no solution above is now <4MB and <.01s! Runs below are with that version. (and apparently using a different dictionary, some runs were on debian oldstable and some on debian stable)
mtijacfshpwk 214 candidate words Checked 1944 sequences
I also found that there are 8-word puzzles:
kmujpocaziqh 69 candidate words jam - ma - aqua - ah - ho - oz - zip - pick 8/22 Checked 854 sequencesand 9+-word but I don't like some of the words (and the app doesn't accept 2-letter words):
dnijzaexkyrc 153 candidate words jerk - kc - ca - ax - xi - icky - yd - dz - zen 9/23 Checked 1038 sequences
Source code (GPL-3.0 license) (build with g++ -std=c++20 -O2):
Faster version:
Original version:
Tyler Wong's Possibly Optimal Hangman Strategy
I always like it when a computer is able to establish an optimal strategy for a game; that forever frees human beings from spending their time playing it.
Toward that end, here's an effort from 2001: http://www.sharkfeeder.com/hangman/. I wonder if a modern computer runs much faster than the reported 15 hours on a P3/600 -- let's hope it does. Perhaps this can be used to push the search deeper than choosing one of the 4 most likely letters at each junction, though for each one-letter increase I imagine there's a pretty steep runtime increase.
All older entries
Website Copyright © 2004-2024 Jeff Epler