7
\$\begingroup\$

I wrote DSSudokuSolver - a sudoku solving algorithm a while back. Is there any possibility that this algorithm can be improved?

Original Algorithm:

CleanElements = function(comp_ary, Qsudoku){
    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            /*if(Qsudoku[i][j] != ""){
              comp_ary[i][j]=[];
              }*/
            for(k=0; k<9; k++){
                i_index = comp_ary[i][k].indexOf(Qsudoku[i][j]);
                if(i_index != -1){
                    comp_ary[i][k].splice(i_index, 1);
                }
                j_index = comp_ary[k][j].indexOf(Qsudoku[i][j]);
                if(j_index != -1){
                    comp_ary[k][j].splice(j_index, 1);
                }
            }
            if(i < 3){
                i_min = 0;
                i_max = 2;
            }
            else if(i < 6){
                i_min = 3;
                i_max = 5;
            }
            else{
                i_min = 6;
                i_max = 8;
            }

            if(j < 3){
                j_min = 0;
                j_max = 2;
            }
            else if(j < 6){
                j_min = 3;
                j_max = 5;
            }
            else{
                j_min = 6;
                j_max = 8;
            }

            for(i_box=i_min; i_box<=i_max; i_box++){
                for(j_box=j_min; j_box<=j_max; 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(i=0; i<9; i++){
        for(j=0; j<9; j++){
            if(comp_ary[i][j].length == 1){
                if (Qsudoku[i][j] == ""){
                    Qsudoku[i][j] = comp_ary[i][j][0];
                    comp_ary[i][j] = [];
                }
            }
        }
    }
    return Qsudoku;
}

IsThereNullElement = function(Qsudoku){
    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            if(Qsudoku[i][j] == ""){
                return false;
            }
        }
    }
    return true;
}

InitEmptyArray = function(){
    empty_ary = Array();
    for(i=0; i<9; i++){
        empty_ary[i] = Array();
        for(j=0; j<9; j++){
            empty_ary[i][j] = Array();
            for(k=0; k<9; k++){
                empty_ary[i][j][k] = (k+1).toString();
            }
        }
    }
    return empty_ary;
}

DSSolve = function(Qsudoku){
    comp_ary = InitEmptyArray(); //Complementary Array
    window.comp_ary_old = comp_ary;
    IterationMax = 5000;

    while(true){
        IterationMax -= 1;
        comp_ary = CleanElements(comp_ary, Qsudoku);
        console.log(comp_ary);

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

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

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

        if(IterationMax == 0){
            return null;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You should generally avoid adding properties to window. \$\endgroup\$ – Shmiddty Oct 2 '13 at 15:20
  • \$\begingroup\$ It seems you are using the brute force approach ( en.wikipedia.org/wiki/Sudoku_solving_algorithms ), any other approach will be much faster. \$\endgroup\$ – konijn Dec 29 '13 at 23:45
  • \$\begingroup\$ Why did you declare all functions anonymously? \$\endgroup\$ – hkk Jan 2 '14 at 16:09
5
+50
\$\begingroup\$

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>=i_min; i_box--){
                    for(var j_box=j_max; j_box>=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!

\$\endgroup\$
  • \$\begingroup\$ Great input. I'm not going to award the bounty for a while yet as there may be other answers coming. Feel free to improve on your answer if you feel there are other things to add. \$\endgroup\$ – rolfl Dec 29 '13 at 16:30
  • \$\begingroup\$ Oh no worries, the bounty is whatever to me anyway, it just seemed weird that a question like this would go unanswered for so long without someone at least giving it a shot. A faster web is a better web, :) \$\endgroup\$ – PlantTheIdea Dec 29 '13 at 18:08
  • \$\begingroup\$ Wow, thanks for the great answer. A really fantastic one. \$\endgroup\$ – dhilipsiva Apr 12 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.