### Solving Boggle

Wednesday, March 16, 2011 by gradbot

Trie

```function Trie(dictionary) {
var trie = {};

function insert(word, trie) {
var word_length = word.length;

if (word_length) {
var next = trie;

for (var i = 0; i < word_length; i++) {
var char = word[i];

if (char in next) {
next = next[char];
} else {
var child = {};
next[char] = child;
next = child;
}
}

next['|'] = null;
}
}

for (var i = 0, length = dictionary.length; i < length; i++) {
insert(dictionary[i], trie);
}

// returns true for a word, null for a segment and false otherwise
this.test = function(str) {
var next = trie;

for (var i = 0, str_length = str.length; i < str_length; i++) {
var char = str[i];

if (char in next) {
next = next[char];
} else {
return null;
}
}

return '|' in next;
};
}```

Boggle Search

```// main workhorse, depth first
function start_search(start_x, start_y, length_x, length_y, segment, trie, board, visited, results) {
var min_y = Math.max(0, start_y - 1),
min_x = Math.max(0, start_x - 1),
max_y = Math.min(length_y - 1, start_y + 1),
max_x = Math.min(length_x - 1, start_x + 1);

for (var y = min_y; y <= max_y; y++) {
var visited_y = visited[y],
board_y = board[y];

for (var x = min_x; x <= max_x; x++) {
if (!visited_y[x]) {
var segment_new = segment + board_y[x],
test = trie.test(segment_new);

if (test === true) {
results[segment_new] = true;
}

if (test !== null) {
visited_y[x] = true;
start_search(x, y, length_x, length_y, segment_new, trie, board, visited, results);
visited_y[x] = false;
}
}
}
}
}

function search(trie, board) {
var length_y = board.length,
length_x = board[0].length;

var visited = [];
for (var y = 0; y < length_y; y++) {
visited[y] = [];
for (var x = 0; x < length_x; x++) {
visited[y][x] = false;
}
}

var results = {};
for (var y = 0; y < length_y; y++) {
var visited_y = visited[y],
board_y = board[y];

for (var x = 0; x < length_x; x++) {
visited_y[x] = true;
start_search(x, y, length_x, length_y, board_y[x], trie, board, visited, results);
visited_y[x] = false;
}
}

var result_array = [];
for (var word in results) {
if (results.hasOwnProperty(word)) {
result_array.push(word);
}
}

result_array.sort();

return result_array;
}```

Example Execution

```function solve_boggle(dictionary) {
var board = [
["d", "g", "f", "k"],
["o", "z", "a", "c"],
["b", "w", "k", "e"],
["b", "w", "k", "e"]
],
trie = new Trie(dictionary),
results = search(trie, board);

\$(".results").text(results.join(", "));
}

if (window.localStorage !== null && window.localStorage.dictionary) {
solve_boggle(window.localStorage.dictionary.split(","), callback);
} else {