Solving Letter Boxed In Python

Letter Boxed Introduction

Letter Boxed is a word puzzle game developed by The New York Times as part of their daily digital games collection. In Letter Boxed, players are presented with a square grid where the border is filled with letters. The objective is to connect these letters to form words, in such a way that each word starts with the ending letter of the previous word, creating a continuous chain.

The rules are fairly simple:

1. Each word must be at least three letters long.

2. Words must be formed by connecting letters from different edges i.e., a word cannot use consecutive letters from the same edge.

3. Subsequent words must begin with the ending letter of the previous word.

4. The game typically requires finding a series of words that use up all the given letters on the edges.

The challenge lies in strategically determining a sequence of words that utilizes every letter at least once, and achieving this with the fewest possible words.

Solution

Word List

For word games, a word list is quite essential for the search. With Python, there is easy access to the Natural Language ToolKit (NLTK) corpora via the nltk package. The words corpus contains over 235,000 English words.

import nltk

nltk.download('words')
nltk_words = nltk.corpus.words.words()

Search

The search for words that cover the entire word list is quite a large search space. There are a few ways to trim the word list quite rapidly.

1. Make sure that the words meet the minimum length requirement of Letter Boxed

2. Make sure that the words only contain the letters provided in the Letter Boxed square and obey the rule that consecutive letters come from different edges of the square.

# Check if the word is valid for the Letter Boxed game

# word
#     word from the dictionary
# args.top, args.left, args.bottom, args.right
#     letters from each side of the LetterBoxed game

# Check if the word meets the minimum length
if len(word) < args.min or len(word) > args.max:
    return False

# Check if word contains only letters in the box without consecutive letters from same side
sides = {'t': args.top, 'l': args.left, 'b': args.bottom, 'r': args.right}
prev_set_name = None
for letter in word:
    set_name = next((name for name, side in sides.items() if letter in side), None)
    if set_name is None or set_name == prev_set_name:
        return False
    prev_set_name = set_name

Once the word list has been pruned, typically the search space reduces by ~95-99%. Then the problem becomes a recursive search with backtracking starting with a random word from the word list and checking to see if all the letters of the Letter Boxed game are covered.

def recursive_solve(args, all_solutions, solution=None, depth=0):
    """
    A recursive function to solve a given problem using backtracking.

    Args:
        args: The arguments for the recursive solve function.
        all_solutions: A list to store all the found solutions.
        solution: The current solution being built (default is None).
        depth: The current depth of recursion (default is 0).

    Returns:
        list: A list of all the found solutions.
    """
    solution = solution or []
    if depth != args.depth:
        for word in args.search_words:
            potential_solution = solution + [word]
            used_letters = set(list(''.join(potential_solution)))
            if args.all_letters == used_letters:
                logging.info("Found solution: %s", potential_solution)
                all_solutions.append(potential_solution)
            else:
                last_letter = word[-1]
                args.search_words = [x for x in args.all_search_words
                                     if x[0] == last_letter and x != word]
                all_solutions = recursive_solve(args, all_solutions, potential_solution, depth + 1)
    return all_solutions

Full code for this can be found at https://github.com/arunkv/letter-boxed/blob/main/lb.py A typical two-word solve for Letter Boxed finds all possible solutions in under a second.