Boggle Solver challenge

boggle.js

// Solution to Boggle Solver challenge
// Working example at http://boggle.mcgees.me
// 2014-06-28
// Joshua McGee

(function() {
  "use strict";

  // My solution was to load the Scrabble dictionary into a search tree, then search the board
  // for possible matching words by checking each starting position and recursively checking
  // its neighbors.  Because the search tree by definition shows all valid paths that can lead
  // up to a word, we can abort every search as soon as we know that the search cannot produce
  // an English word.  For instance, if our path begins 'abho', then we keep searching,
  // because 'abhor' and its derivatives are real words.  If we encounter 'd' as the next
  // letter, we know we can stop searching because no English word begins with 'abhod'. This
  // makes the search very fast.  Along the way, we check each node to see if it is itself
  // a valid English word and, if so, push it into an array of matches.

  var addNode, adjacent, explorePath, grid, gridHeight, gridWidth, matches, nodes, resetUsed, solvePuzzle, used;

  /* Root node for our search tree */
  nodes = {
    e: false,
    n: {}
  };
  
  /* Variables to hold grid and match information */
  matches = [];
  grid = [];
  used = [];
  gridWidth = 0;
  gridHeight = 0;
  
  /* Adjacency matrix for exploring the grid */
  adjacent = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

  /* Function to add a node to the search tree */
  addNode = function(letterArray, node) {
    var letter, _base;
    if (letterArray.length === 0) {
      node.e = true;
    } else {
      letter = letterArray.shift();
      (_base = node.n)[letter] || (_base[letter] = {
        e: false,
        n: {}
      });
      addNode(letterArray, node.n[letter]);
    }
  };

  /* Function called at the top level of search to reset the grid of used squares */
  resetUsed = function() {
    var column, row, x, y, _i, _j, _len, _len1;
    used = [];
    for (y = _i = 0, _len = grid.length; _i < _len; y = ++_i) {
      row = grid[y];
      used.push([]);
      for (x = _j = 0, _len1 = row.length; _j < _len1; x = ++_j) {
        column = row[x];
        used[y].push(false);
      }
    }
  };

  /* Function called recursively to explore the grid, aborting when it's impossible to find further matching words */
  explorePath = function(y, x, word, node) {
    var i, newX, newY, relation, _i, _len;
    if (node == null) {
      node = nodes;
    }
    /* Mark this letter as used in the current path */
    used[y][x] = true;
    if (typeof node.n[grid[y][x]] === 'undefined') {
      used[y][x] = false;
      return;
    }
    if (node.n[grid[y][x]].e) {
      matches.push(word);
    }
    /* Look in the eight possible positions for the next letter of a path */
    for (i = _i = 0, _len = adjacent.length; _i < _len; i = ++_i) {
      relation = adjacent[i];
      newY = y + relation[0];
      newX = x + relation[1];
      /* Check that the next letter position is on the board and hasn't been used */
      if (newY >= 0 && newY < gridHeight && newX >= 0 && newX < gridWidth && !used[newY][newX]) {
        explorePath(newY, newX, word + grid[newY][newX], node.n[grid[y][x]]);
      }
    }
    /* Unmark this letter as used and pop */
    used[y][x] = false;
  };

  /* Function to begin a search of a letter grid */
  solvePuzzle = function(puzzleText) {
    var letter, row, x, y, _i, _j, _k, _l, _len, _len1, _len2, _len3, _ref, _ref1;
    used = [];
    matches = [];
    grid = [];
    gridWidth = 0;
    gridHeight = 0;
    _ref = puzzleText.split(/\r?\n/);
    for (y = _i = 0, _len = _ref.length; _i < _len; y = ++_i) {
      row = _ref[y];
      if (row.length) {
        grid.push([]);
        used.push([]);
        gridHeight += 1;
        gridWidth = row.length;
        _ref1 = row.split('');
        for (x = _j = 0, _len1 = _ref1.length; _j < _len1; x = ++_j) {
          letter = _ref1[x];
          grid[y].push(letter);
          used.push(false);
        }
      }
    }
    for (y = _k = 0, _len2 = grid.length; _k < _len2; y = ++_k) {
      row = grid[y];
      for (x = _l = 0, _len3 = row.length; _l < _len3; x = ++_l) {
        letter = row[x];
        resetUsed();
        /* Begin recursive search */
        explorePath(y, x, letter);
      }
    }
    return matches;
  };

  /* Expose solvePuzzle outside the anonymous function */
  window.solvePuzzle = solvePuzzle;

  /* Load dictionary when DOM is loaded */
  $(document).ready(function() {
    /* Retrieve the dictionary and populate the search tree */
    $.ajax({
      url: "http://boggle.mcgees.me/sowpods.txt"
    }).done(function(data) {
      var word, _i, _len, _ref;
      _ref = data.split(/\r?\n/);
      /* Add each word to the search tree */
      for (_i = 0, _len = _ref.length; _i < _len; _i++) {
        word = _ref[_i];
        addNode(word.split(''), nodes);
      }
      $('body').addClass('ready');
      return true;
    });
    return true;
  });

}).call(this);