My parents like to play word games, and I like to solve these games, but their latest game has me a bit stumped. I've already made a working solver, but it seems to scale exponentially, so many of the later levels in the game I've never seen actually list a solution because of how long it starts to take. Because of this, I'm curious to see other people's take on the problem to see if there's a better solution than mine. Also worth mentioning, I know well there are already plenty of websites that list the answers, but I'm more interested in doing the problem than getting the answer.
Wordbrain as a mobile game is something like a word search meets Candy Crush, with predefined boards and scripted solutions. You start with a square board of size n (increases after you get further in the game, I believe goes from 2 to 7) of predetermined letters. You have to drag across adjacent letters (orthogonal and diagonal) to create words. Each level has a predetermined solution, so not every single word you find will be allowed; you have to find the developer's solution. Once you find one of the correct words, all the letters of that word are removed and any letters above them are moved down to fill their space. Rinse and repeat until you've cleared the board of all letters and found every word. Lastly, below the board the game tells you the length of each word in the solution, and if you use a hint, it'll tell you the first letter of a random unsolved word.
My solution mostly relies on a method of polling words that I don't know if there's already a name for, a fractal dictionary (python dictionary) of words that I've taken to calling a tree dictionary. A good analogy is sorting each word out from my input list (ENABLE with a few extra words added in) into folders each labeled with the first letter. Then in each folder, sort each A word into another 26 folders for each word's second letter, etc. Once completed, the input list of words can be viewed as a binary tree with each node having 26 branches. Lastly, each iteration has a separate data-point to keep track of if the current slew of letters is a word or not (ex: A is a word, AA is a word, AAR is not, but AARDVARK is). This approach changes the runtime of searching if a specific word exists from O(n)=len(list), to O(n)=27*len(n) at worst. For reference, the ENABLE list is 172,820 unique words.
The way my current solver works basically boils down to navigating the tree dictionary via the board as a guide, or vice versa. It starts at each point on the given board, then checks all adjacent tiles to see if the current string has a next letter to continue completing a word, and reiterate, yielding all current words that have a length allowed in the given list of word lengths and (if necessary) have the same first letter. After finding a potential word, it removes the word from the board, applies gravity, then reiterates. Once it finds a list of words on the board that can satisfy the list of word lengths (which should be the same length as the number of letters on the board) then it yields the result, and searches for another solution.
Due to the nature of my solver, its runtime seems to increase exponentially with board size. I've never seen my solver return a result from any 6x6 sized boards (at least while running on my phone) so naturally I'm looking for a better solution.
Wordbrain as a mobile game is something like a word search meets Candy Crush, with predefined boards and scripted solutions. You start with a square board of size n (increases after you get further in the game, I believe goes from 2 to 7) of predetermined letters. You have to drag across adjacent letters (orthogonal and diagonal) to create words. Each level has a predetermined solution, so not every single word you find will be allowed; you have to find the developer's solution. Once you find one of the correct words, all the letters of that word are removed and any letters above them are moved down to fill their space. Rinse and repeat until you've cleared the board of all letters and found every word. Lastly, below the board the game tells you the length of each word in the solution, and if you use a hint, it'll tell you the first letter of a random unsolved word.
My solution mostly relies on a method of polling words that I don't know if there's already a name for, a fractal dictionary (python dictionary) of words that I've taken to calling a tree dictionary. A good analogy is sorting each word out from my input list (ENABLE with a few extra words added in) into folders each labeled with the first letter. Then in each folder, sort each A word into another 26 folders for each word's second letter, etc. Once completed, the input list of words can be viewed as a binary tree with each node having 26 branches. Lastly, each iteration has a separate data-point to keep track of if the current slew of letters is a word or not (ex: A is a word, AA is a word, AAR is not, but AARDVARK is). This approach changes the runtime of searching if a specific word exists from O(n)=len(list), to O(n)=27*len(n) at worst. For reference, the ENABLE list is 172,820 unique words.
The way my current solver works basically boils down to navigating the tree dictionary via the board as a guide, or vice versa. It starts at each point on the given board, then checks all adjacent tiles to see if the current string has a next letter to continue completing a word, and reiterate, yielding all current words that have a length allowed in the given list of word lengths and (if necessary) have the same first letter. After finding a potential word, it removes the word from the board, applies gravity, then reiterates. Once it finds a list of words on the board that can satisfy the list of word lengths (which should be the same length as the number of letters on the board) then it yields the result, and searches for another solution.
Due to the nature of my solver, its runtime seems to increase exponentially with board size. I've never seen my solver return a result from any 6x6 sized boards (at least while running on my phone) so naturally I'm looking for a better solution.