Solving [WordHero] October 10, 2012
I took pretty much a brute force attack at coming up with this app that solves [WordHero]. It is pretty efficient and takes longer to type in the letters of the puzzle than for it to solve it.
Here's how I went about it.
So, you get a puzzle with 16 (or so, as you can see with the Qu block) letters arranged in a 4x4 grid. Obviously this is a dictionary brute force attack, in the most literal sense.
What I do is start at the top left block, finding words that start there, then when all options are exhausted, move onto the next block and find all words that start there, and so on until we've covered all blocks. I wrote this solution in Node.js. First, there is the LetterBox class:
var LetterBox = function(letter, row, col){
this.letter = letter;
this.row = row;
this.col = col;
this.used = false;
}
LetterBox.prototype.clone = function(){
var lb = new LetterBox(this.letter, this.row, this.col);
return lb;
}
The letter box can only be used once during a word solve. The next is the Board, which consists of LetterBoxes
var Board = function(str){
this.originalString = str;
this.makeBoard(str);
this.letterBoxLookup = {};
var self = this;
this.letterBoxes.forEach(function(lb){
self.letterBoxLookup[lb.row + "" + lb.col] = lb;
});
this.rows = 4;
this.cols = 4;
}
I implemented clone on both the Board and LetterBox classes.
The last piece is the BoardSolver class. We'll just look at two functions of it:
Solve:
BoardSolver.prototype.solve = function(max){
for (var i = 0; i < this.board.rows; i++){
for (var j = 0; j < this.board.cols; j++){
var boardinstance = this.board.clone();
this.getWords("", i, j, boardinstance, this.dictionary);
}
}
var list = [];
for (var w in this.foundWords)
list.push(w);
return list;
}
And getWords:
BoardSolver.prototype.getWords = function(cur, row, col, boardinstance, dictlocal){
var letter = boardinstance.getLetter(row,col);
if (letter == null || letter.used) return;
var curlocal = cur + letter.letter;
var potlocal = this.potential(curlocal, dictlocal);
if (potlocal.length == 0) return; // no potentials down this path
var wordlocal = curlocal.length > 2 ? this.matches(curlocal, potlocal) : [];
var self = this;
wordlocal.forEach(function(w){
if (!(w in self.foundWords)) self.foundWords[w] = w;
});
letter.used = true;
//var recurseClone = boardinstance.clone();
// n,s,e,w
this.getWords(curlocal, row, col-1, boardinstance.clone(), potlocal);
this.getWords(curlocal, row, col+1, boardinstance.clone(), potlocal);
this.getWords(curlocal, row+1, col, boardinstance.clone(), potlocal);
this.getWords(curlocal, row-1, col, boardinstance.clone(), potlocal);
// diagonals
this.getWords(curlocal, row-1, col-1, boardinstance.clone(), potlocal);
this.getWords(curlocal, row+1, col+1, boardinstance.clone(), potlocal);
this.getWords(curlocal, row+1, col-1, boardinstance.clone(), potlocal);
this.getWords(curlocal, row-1, col+1, boardinstance.clone(), potlocal);
}
So, while we're recursing, we'll get the current potential word (previous cur + this letter) and see if there are any potential words, words that start with the letters in curlocal. If there are no potential matches, stop recursion. If there are potential matches, keep going, also, store the current matched words at the current length (e.g. "break" is found on the way to finding "breaking")
To speed things up a bit, I only then search the potential list in the future attempts to narrow it down. Notice I'm passing the potlocal (potential local dictionary) into getWords on recursion.
To use the app currently, I just modify the string of characters. They are entered as follows (for example, for solving the puzzle attached in the screenshot)
[qu]aaevftmeimsckou
It will then store a file called
[qu]aaevftmeimsckou.txt.
Here's the results of it running that:
My dictionary is lacking words, it only has 81,536...
One thing to point out. Since Javascript does everything by reference, I have to clone the board for each level of recursion since they will mark letters as used and then future recursions will see them as used. The clone board method clones the letter boxes and then correctly marks the currently used letters as used in the clone. This makes it correct.
The file uses a library I wrote for node.js to easily read / write files. You can download my [WordHero] solver here. You can fill in the missing fshelp methods with standard node file IO methods.