Solving Wordscapes with Brute Force

Wordscapes is a popular IOS game where players solve each level by spelling out words on a Scrabble-like board from a list of characters. We're going to solve Wordscapes with a very simple brute force algorithm.

The algorithm works as follows:

• Compute all permutations of the characters from length three up to the number of characters
• Check if each permutation is a valid word

Wordscapes always has between three and seven characters to choose from in the circle. This is why we can get away with using a brute force solution. The runtime of this algorithm becomes unsustainable even once we get up to ten characters, but since we are always limited to a small starting list we don't need to optimize further.

Now let's create a python class to represent and solve a level in Wordscapes.

To validate words, we're going to use PyEnchant, a python wrapper for the Enchant library.

python
Copy Code
import enchant
import itertools
from collections import defaultdict

class Wordscapes:
    def __init__(self, letters):
        self.letters = [char for char in letters]
        self.words = set()
        self.word_length_map = defaultdict(set)
        self.english_dict = enchant.Dict("en_US")
        self.generate_words()

    def generate_words(self):
        for i in range(3, len(self.letters) + 1):
            for perm in itertools.permutations(self.letters, i):
                temp = ''.join(perm)
                if self.english_dict.check(temp):
                    self.words.add(temp)
                    self.word_length_map[len(temp)].add(temp)

    def summarize(self):
        for i, words in self.word_length_map.items():
            print("{}: ".format(i), words)

Let's look at level 93 on Wordscapes, where the list of characters is: "csaecs".

Wordscapes('csaecs').summarize()

Now we have all the possible valid words of length three to six, and we can enter them and solve the level. We can use this same approach to solve every level in Wordscapes.