Optimized Boggle Board Solver

boggle-solver.js

var board = [
    [ 'a', 'b', 'c', 'd' ],
    [ 'a', 'f', 's', 'j' ],
    [ 'd', 'e', 'a', 't' ],
    [ 'g', 'u', 'n', 'f' ]
];

var dictionary = [ 'fab', 'fad', 'san', 'fan', 'fade', 'fed', 'seat', 'dab', 'bad' ];

var Solver = function ( board, dictionary ) {

    var obj         = {},
        width       = board.length,
        height      = board[ 0 ].length,
        results     = [],
        lookup;

    this.results = results;

    function init () {
        lookup = convertToTree( dictionary );
        scanBoard();
    }
    
    function convertToTree ( dictionary ) {
        var word, scope, c, i, j, tree = {};
        for ( i = dictionary.length; --i; ) {
            scope = tree;
            word = dictionary[ i ];
            for ( j = 0; j < word.length; ++j ) {
                c = word.charAt( j );
                scope[ c ] = scope[ c ] || {};
                scope = scope[ c ]
                if ( j === word.length - 1 ) scope.word = true;
            }
        }
        return tree;
    }
    
    function scanBoard () {
        var i, j, c;
        for ( i = board.length; i--; ) {
            for ( j = board[ i ].length; j--; ) {
                c = board[ i ][ j ];
                if ( lookup[ c ] ) traverse( '', [], i, j, lookup[ c ] );
            }
        }
    }
    
    function traverse ( word, history, x, y, lookup ) {
        var i, j, c, istart, iend, jstart, jend;
        word += board[ x ][ y ];
        history.push( x + ',' + y );
        istart = Math.max( 0, x - 1 );
        iend = Math.min( x + 1, width - 1 );
        if ( lookup.word ) results.push( { coords: history.slice(), word: word } );
        for ( i = istart; i <= iend; i++ ) {
            jstart = Math.max( 0, y - 1 );
            jend = Math.min( y + 1, height - 1 );
            for ( j = jstart; j <= jend; j++ ) {
                if ( history.indexOf( i + ',' + j ) < 0 ) {
                    found = true;
                    c = board[ i ][ j ];
                    if ( lookup[ c ] ) traverse( word, history.slice(), i, j, lookup[ c ] );
                }
            }
        }
    }

    this.print = function () {
        var html = '<dl>';
        for ( var i = results.length; i--; ) {
            html += '<dt>' + results[ i ].word.toUpperCase() + '</dt>';
            html += '<dd>' + results[ i ].coords.join( ' -> ' ) + '</dd>';
        }
        html += '</dl>'
        document.body.innerHTML = html;
    }

    init();
};

var solver = new Solver( board, dictionary );
solver.print()

Neat.