1
$\begingroup$

Letter boxed

WARNING: I solved this puzzle and posted a solution below. I'm posting this more for muse.

Hello! I don't know if anyone's enjoyed this puzzle on The New York Times website, but I find it rather fun. The rules published on the site are as follows:

  • Connect letters to spell words
  • Words must be at least 3 letters long
  • Letters can be reused
  • Consecutive letters cannot be from the same side
  • The last letter of a word becomes the first letter of the next word
  • e.g. THY > YES > SINCE
  • Words cannot be proper nouns or hyphenated
  • No cussing either, sorry
  • Use all letters to solve!

It's visually helpful to graph the words by connecting the dots from one side of the box to another to spell the words, so you can see where you are and where you can go. The challenge, therefore, is to solve using as few words as possible. The ideal solution (which likely never exists) would be one monster word, at least 12 letters long, that has at least one of each of the letters in the puzzle and that also satisfies the constraints listed above.

Not being a cheater but more of a computer science/math person, I was able to devise a list of candidate words for the puzzle above using the following method:

  1. Assuming a word no longer than 26 characters in length, I submitted the following string of 26 characters to the Anagram Server: jtttddcceeeepblliiiwwyyhhh

    This string has repetition of letters relative to the frequency distribution of letters in the English language.

  2. The Anagram Server returned 483 candidate words. However, most of these candidate words do not meet the constraints of the rules listed above because they may contain consecutive letters of the same side of the box and/or were fewer than 3 letters long.
  3. Besides eliminating candidate words fewer than four letters long, I also eliminated words containing these 36 pairs of consecutive letters: jt, jd, tj, td, dj, dt, jj, tt, dd, ce, cp, ec, ep, pc, pe, cc, ee, pp, bl, bi, lb, li, ib, il, bb, ll, ii, wy, wh, yw, yh, hw, hy, ww, yy, hh.
  4. The candidate list was then whittled down to these 159 qualifying words: bed, beheld, bejewel, bejeweled, belch, belched, belt, belted, bet, betel, betide, betided, bewitch, bewitched, bey, bye, byte, chew, chewed, chi, chic, chichi, chicle, chid, chide, chided, chip, chit, cite, cited, city, clew, clewed, cycle, cycled, deb, debt, deity, delete, deleted, dew, did, die, died, diet, dieted, dietetic, dip, diptych, ditch, ditched, dwelt, dye, dyed, edict, edit, edited, etch, etched, ethic, ewe, eye, eyed, eyelet, held, help, hew, hewed, hey, hid, hide, hided, hie, hied, hip, hit, hitch, hitched, icicle, icy, idle, idled, idly, idyl, itch, itched, jet, jew, jewel, jeweled, led, lei, let, lewd, lewdly, lye, phew, phi, pic, pie, pied, piety, pit, pitch, pitched, pith, pitied, pity, plebe, pled, ply, the, thew, they, tic, tide, tided, tidied, tidy, tie, tied, tip, tipi, tit, tithe, tithed, title, titled, twit, twitch, twitched, web, wed, welch, welched, weld, welded, welt, welted, wet, wetly, wide, widely, wield, wielded, wit, witch, witched, wite, with, withe, withed, yelp, yet, yeti, yew, yield, yielded, yip.
  5. The obvious solution would be to choose which words among these has both the most and greatest diversity of letters, and that would solve the puzzle. The two words I chose for the solution were bejeweled and diptych.

It got me thinking that an "extra challenge" puzzle would be to take those 159 candidate words above and sort them in an order such that most, if not all, words could be graphed in the puzzle. That is the part I haven't figured out yet. There are 54 words that end in the letter D, but only 19 words that start with that letter. Therefore, words that end in D would need to be rationed while maximizing other letters that have more balance beginning and ending.

Anyone have ideas how to achieve this mathematically?

$\endgroup$
  • 4
    $\begingroup$ The longest path problem is NP-hard, so if you figure out a better way than a brute-force search, write a paper and get rich :-) $\endgroup$ – Bass Nov 25 '20 at 9:58
  • 2
    $\begingroup$ It's possible for a problem to be NP-hard but for most actual instances one encounters to be efficiently solvable. Or for a problem to be NP-hard but a particular instance small enough to be solved efficiently. $\endgroup$ – Gareth McCaughan Nov 25 '20 at 12:40
  • 1
    $\begingroup$ @bobble IANAL, but this seems to tick pretty much all the boxes of "fair use": it's used for educational purposes, it's transformed from the original, it's a small excerpt, and it doesn't diminish the value of the original. $\endgroup$ – Bass Nov 25 '20 at 16:15
  • 1
    $\begingroup$ @bobble This puzzle was publicly accessible on their site. I'm not a puzzle subscriber (too expensive for me). $\endgroup$ – Aaron Nov 25 '20 at 19:59
  • 2
    $\begingroup$ Fair, fair. I retract my earlier worry. $\endgroup$ – bobble Nov 25 '20 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.