Uncaught RangeError: Maximum call stack size exceeded with sudoku solver

Question

// global variable
// accessible to all functions
var sol =
    [[0, 7, 0, 2, 3, 8, 0, 0, 0],
    [0, 0, 0, 7, 4, 0, 8, 0, 9],
    [0, 6, 8, 1, 0, 9, 0, 0, 2],
    [0, 3, 5, 4, 0, 0, 0, 0, 8],
    [6, 0, 7, 8, 0, 2, 5, 0, 1],
    [8, 0, 0, 0, 0, 5, 7, 6, 0],
    [2, 0, 0, 6, 0, 3, 1, 9, 0],
    [7, 0, 9, 0, 2, 1, 0, 0, 0],
    [0, 0, 0, 9, 7, 4, 0, 8, 0]];
//this function prints the board
var printBoard = function () {
    for (let row = 0; row < sol.length; row += 1) {
        for (let col = 0; col < sol[row].length; col += 1) {
            let id = 'r' + (row + 1) + (col + 1);
            let elem = document.getElementById(id);
            elem.innerHTML = sol[row][col];
        }
    }
};

function isValid(sol, row, col, k) {
    for (let i = 0; i < 9; i++) {
        const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
        const n = 3 * Math.floor(col / 3) + i % 3;
        if (sol[row][i] == k || sol[i][col] == k || sol[m][n] == k) {
          return false;
        }
    }
    return true;
}

var solve = function() {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (sol[row][col] == 0) {
                for (let k = 1; k <= 9; k++) {
                    if (isValid(sol, row, col, k) == true) {
                        sol[row][col] == '${k}';
                        if(solve() == true) {
                            return true;
                        } else {
                            sol[row][col] == 0;
                        }
                    }
                }
                return false;
            }
        }
    }
    return true;
}

printBoard();
   

I am having trouble debugging this. I keep getting an error message when I click on my solve button, which will take the grid and complete a sudoku puzzle: "Uncaught RangeError: Maximum call stack size exceeded". Looking at the file, it seems that my isValid() function, is causing the issues here. I think I am stuck in a continuous loop somewhere? Any help would be appreciated. It also says the error lies on lines 40 and 24, which are:

function isValid(sol, row, col, k) {

and

if (isValid(sol, row, col, k) == true) {

Please help, as I am not even a CS major and this is for a class requirement, and I am not exactly experience with this type of stuff. I tried to search for help thorugh other resources but it is just confusing me even more.

EDIT:

//global variable
//accesible to all functions
var sol =
    [[0, 7, 0, 2, 3, 8, 0, 0, 0],
    [0, 0, 0, 7, 4, 0, 8, 0, 9],
    [0, 6, 8, 1, 0, 9, 0, 0, 2],
    [0, 3, 5, 4, 0, 0, 0, 0, 8],
    [6, 0, 7, 8, 0, 2, 5, 0, 1],
    [8, 0, 0, 0, 0, 5, 7, 6, 0],
    [2, 0, 0, 6, 0, 3, 1, 9, 0],
    [7, 0, 9, 0, 2, 1, 0, 0, 0],
    [0, 0, 0, 9, 7, 4, 0, 8, 0]];
//this function prints the board
var printBoard = function () {
    for (let row = 0; row < sol.length; row += 1) {
        for (let col = 0; col < sol[row].length; col += 1) {
            let id = 'r' + (row + 1) + (col + 1);
            let elem = document.getElementById(id);
            elem.innerHTML = sol[row][col];
        }
    }
};

function isValid(sol, row, col, k) {
    for (let i = 0; i < 9; i++) {
        const m = 3 * Math.floor(row / 3) + Math.floor(i / 3);
        const n = 3 * Math.floor(col / 3) + i % 3;
        if (sol[row][i] == k || sol[i][col] == k || sol[m][n] == k) {
          return false;
        }
    }
    return true;
}

var solve = function(sol) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
          if (sol[row][col] == 0) {
              //set the check for the row and column
            for (let k = 1; k <= 9; k++) {
              if (isValid(sol, row, col, k) == true) {
                sol[row][col] == k;
                //check if its not true, then check the row and column again
              if(solve() == true) {
               return true;
              } else {
               sol[row][col] = 0;
              }
             }
           }
           return false;
         }
       }
     }
     return true;
    };

printBoard();
    

Answer 1

You never change sol before recursively calling solve() again.

if (isValid(sol, row, col, k) == true) {
    sol[row][col] == '${k}'; // <- does not update sol
    if(solve() == true) {
        return true;
    } else {
        sol[row][col] == 0; // <- does not update sol
    }
}

When you find an option for k that is a valid you should update sol before calling solve() again. Otherwise you will create an endless recursive loop which will eventually exceed the maximum stack size and result in the error you receive.

Use the assignment operator (=) instead of the equality operator (==) to assign a new value. Furthermore '${k}' will result in the literal ${k} use backticks (`) if you want to use string interpolation. I don't see a reason to use a string here, simply assigning k would be sufficient.

if (isValid(sol, row, col, k) == true) {
    sol[row][col] = k; // <- assign k to a cell in the matrix
    if(solve() == true) {
        return true;
    } else {
        sol[row][col] = 0; // <- reset the cell back to 0 if it cannot be solved
    }
}

---

I would also suggest using guard clauses. Instead of nesting the whole body of the for-loop inside an if-statement, use a guard and skip to the next iteration with continue:

for (...) {
    if (check) {
        // code
    }
}

Can be changed to:

for (...) {
    if (!check) continue;
    // code
}

This generally improves the code indention and readability.