DSSudokuSolver - A JavaScript Sudoku solving algorithm

Question

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; } } } 

Answer 1

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!