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 {
  function dictionary_load(data) {
    if (window.localStorage !== null) {
       window.localStorage.dictionary = data.join(",");
    }
    solve_boggle(data, callback);
  }

  $.getScript("http://goo.gl/8EhgZ");
}