# DSSudokuSolver - A JavaScript Sudoku solving algorithm

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

• You should generally avoid adding properties to window. – Shmiddty Oct 2 '13 at 15:20
• It seems you are using the brute force approach ( en.wikipedia.org/wiki/Sudoku_solving_algorithms ), any other approach will be much faster. – konijn Dec 29 '13 at 23:45
• Why did you declare all functions anonymously? – hkk Jan 2 '14 at 16:09

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!

• 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. – rolfl Dec 29 '13 at 16:30
• 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, :) – PlantTheIdea Dec 29 '13 at 18:08
• Wow, thanks for the great answer. A really fantastic one. – dhilipsiva Apr 12 '14 at 22:06