Tag Archives: solution

Wordbrain solver – letter permutations

When you are stuck after partly solving a puzzle, there is a chance that the puzzle is solved in the wrong order. Using my path seeking algorithm might not work, since the letter are in the wrong place in the matrix. The remaining letters are however correct. This is why I made a simple program for finding all possible permutations of the remaining letter, disregarding the location. The program also compares against the Norwegian dictionary. You type in the letters and choose length of the word.

The program uses a library for permutations:

Norwegian dictionary as Python dict format: wordDict.txt

Terminal output:

Wordbrain Solver – 5×5 – Brute-Force with filtering v.2

Second attempt for this. The previous 5×5 code was estimated to use 12.5 days to get all possible words. Going through the code, I found some weak spots:

  • No control of word length. The program was traversing through words of lengths up to 25. This means extremely long paths with extremely many different variations. Reduced this to maximum traversing 9 letter words.
  • Checking all possible paths, even some that was unnecessary. I made a new dictionary containing all existing first-and-last letters  in a Norwegian dictionary. This way, instead of checking all possible paths between example ‘z’ to ‘ø’, I can skip all these paths immediately, as no words starts and ends with these letters. This would skip 1/600th of the total time.

This reduced the solution time from 22500 minutes to around 7 minutes (!!!). The 4×4 puzzles was also reduced from 10 minutes to 40 seconds.

Implementations for next version:

  • Create a wordlist for all two-first and two-last characters existing from Norwegian dictionary words. This will skip even more unnecessary paths for finding words.
  • Add a filter for the words lengths necessary, the puzzles will show example three-letter, five-letter and nine-letter word.
  • Move all found words to separate dicts and make a function that deletes all words containing one letter, in cases when a word found contains the last letter of one type. This is a quick way to “thin out” the possible words.

Terminal output:

 

WordBrain solver – 4×4 – Semi-Brute-Force

This is my solution so far, for semi-brute-force solving of 4×4 WordBrain puzzles.

This program will find all possible valid words found in a norwegian dictionary. This will take around ten minutes (on a 1.2Ghz MacBook). I have tried to implement skipping of a path-traveling if the first two letter does not exist in my dictionary.

I have one idea to make the program a little bit faster. I will make a new Python dict containing the first and last letter from all the words in a norwegian dictionary. This way, checking all possible paths from ‘t to ø’ is skipped, if I know that no norwegian words start with a ‘t’ and ends with an ‘ø’. That should shave some time of the implementation.

One problems shown above. The first run of the program checks every possible route from every letter to every other letter. When solving for the word JOKER above, the letters are rearranged and new paths are formed. Meaning the program have to be run again.

The first round is run with the letters: k1,e1,e2,r1,o1,r2,j,e3,e4,r3,o2,k2,ø,y,s,t

After JOKER rearranged the letters, we kan input the letters again, exchanging all the used letters with a letter not existing in that specific problem. Here we will use ‘x’: k1,e1,x1,x2,o1,r2,x3,x4,e3,r3,e4,x5,ø,y,s,t

This will take another 10 minutes, since we will look for unlikely paths like from ø to x.

The OSX Terminal output: