DSSudokuSolver - A JavaScript Sudoku solving algorithm
It's not a huge improvement, just taking a stab at a few slight tweaks:

var sudoku = {
    CleanElements:function(comp_ary, Qsudoku){
        var i_factor,
            j_factor,
            i_min,
            i_max,
            i_index,
            j_index,
            index;

        for(var i=9; i--;){
            i_factor = (3*Math.floor(i/3));
            i_min = 6 - i_factor;
            i_max = 8 - i_factor;

            for(var j=9; j--;){
                j_factor = (3*Math.floor(j/3));
                j_min = 6 - j_factor;
                j_max = 8 - j_factor;

                for(var k=9; k--;){
                    i_index = comp_ary[i][k].indexOf(Qsudoku[i][j]);
                    j_index = comp_ary[k][j].indexOf(Qsudoku[i][j]);

                    if(i_index !== -1){
                        comp_ary[i][k].splice(i_index,1);
                    }

                    if(j_index !== -1){
                        comp_ary[k][j].splice(j_index,1);
                    }
                }

                for(var i_box=i_max; i_box&gt;=i_min; i_box--){
                    for(var j_box=j_max; j_box&gt;=j_min; j_box--){
                        index = comp_ary[i_box][j_box].indexOf(Qsudoku[i][j]);
                        if(index !== -1){
                            comp_ary[i_box][j_box].splice(index, 1);
                        }
                    }
                }
            }
        }
        return comp_ary;
    },
    FindElements:function(comp_ary, Qsudoku){
        for(var i=9; i--;){
            for(var j=9; j--;){
                if(comp_ary[i][j].length === 1){
                    // in case you were specifically checking that it was an empty string and not a null / undefined / etc, change to Qsudoku[i][j] === ''
                    if (Qsudoku[i][j].length === 0){
                        Qsudoku[i][j] = comp_ary[i][j][0];
                        comp_ary[i][j] = [];
                    }
                }
            }
        }
        return Qsudoku;
    },
    IsThereNullElement:function(Qsudoku){
        for(var i=9; i--;){
            for(var j=9; j--;){
                // same here, change to === '' if specifically needed
                if(Qsudoku[i][j].length === 0){
                    return false;
                }
            }
        }
        return true;
    },
    InitEmptyArray:function(){
        var empty_ary = Array();

        for(var i=9; i--;){
            empty_ary[i] = Array();

            for(var j=9; j--;){
                empty_ary[i][j] = Array();

                for(var k=9; k--;){
                    empty_ary[i][j][k] = (k+1)+'';
                }
            }
        }
        return empty_ary;
    },
    DSSolve:function(Qsudoku){
        var self = this,
            comp_ary = self.InitEmptyArray(),
            Qsudoku;

        this.comp_ary_old = comp_ary;

        for(var i=5000; i--;){
            comp_ary = self.CleanElements(comp_ary, Qsudoku);
            // console.log(comp_ary);

            if(sudoku.comp_ary_old === comp_ary){
                // implement this.
            } else {
                sudoku.comp_ary_old = comp_ary;
            }

            Qsudoku = self.FindElements(comp_ary, Qsudoku);
            // console.log(Qsudoku);

            if(self.IsThereNullElement(Qsudoku)){
                return Qsudoku;
            }

            if(i === 0){
                return null;
            }
        }
    }
};


And then you call it with this (Qsudoku being the value you want to pass in):

sudoku.DSSolve(Qsudoku);


Quick breakdown of changes:


changed all for loops and final while loop to decrement (faster in all browsers)
changed == '' to .length === 0 (faster in all browsers)
applied strict comparison === rather than implicit == (faster on certain browsers)
changed multiple if/else if/else statements to applying Math.floor to compute reduction factor
encapsulated all functions within object to allow for use of object comp_ary_old (instead of using window)
added explicit var statement for variable declaration (prevents bubbling up to window)
moved variables to top of respective function and assigned value at point where the fewest loops occur while retaining value integrity
changed the .toString() function to the +'' trick (its a miniscule improvement, more of a "squeeze every byte" thing, so if you would rather stick with code clarity switch it back to .toString())


I haven't tested this at all, so no benchmarks to show if it actually improves performance, but theoretically it should maintain your code operations while executing faster. Figured it was worth a shot, since no one else answered. Hope it helps!