How to debug a recursive function in JS

Question

I've written the following recursive code, for solving a sudoku puzzle.

grid: a global matrix, representing the puzzle.
possible function: returns true or false for a given number and location
solve: a recursion that fills the grid.

However I have a bug, how can I debug it without being trapped in an endless loop.

Is there some sort of force exit? Can you spot the bug?

let grid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]];

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve();
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve();

Answer 1

Standard debugging techniques should generally work here. Learn to use your environment's debugger. For example, if this is running in your browser, you should be able to set a breakpoint in your browser's developer tools, and walk through the code line by line to try to understand what's happening.

Recursion always requires there to be some base condition that causes the recursion to end. In your case, if there are no unsolved squares you could indicate that by returning true, and then pass that "success" status up the call chain.

Also, your call to possible has switched the expected argument positions of x and y.

function solve() {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(x,y,n)){
            grid[y][x] = n;
            var solved = solve();
            if(solved) {
                return true;
            }
            grid[y][x] = 0;
          }
        }
        return false;
      }
    }
  }
  return true; // We didn't find any unsolved squares.
}

let grid = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]];

function possible(x, y, n) {
  for (let i = 0; i < 9; i++) {
    if (grid[y][i] === n) {
      return false
    }
  }
  for (let i = 0; i < 9; i++) {
    if (grid[i][x] === n) {
      return false
    }
  }
  let x0 = Math.floor(x / 3) * 3;
  let y0 = Math.floor(y / 3) * 3;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (grid[y0 + i][x0 + j] === n) {
        return false
      }
    }
  }
  return true;
}

function solve() {
  // find the first unsolved square.
  for (let y = 0; y < 9; y++) {
for (let x = 0; x < 9; x++) {
  if (grid[y][x] === 0) {
    // try every possible number in that square
    for (let n = 1; n < 10; n++) {
      if(possible(x,y,n)){
        grid[y][x] = n;
        var solved = solve();
        // if this led to a valid board, leave the board as-is and return success.
        if(solved) {
            return true;
        }
        grid[y][x] = 0;
      }
    }
    return false;
  }
}
  }
  console.log("all squares are solved");
  return true; // We didn't find any unsolved squares.
}

console.log(solve());
console.log(grid);

Answer 2

You Can Use Google Chrome Debug For Java Script

For Example You Can Creat Break Point In That:

Or Set Watch For Vars :

For Use It Press F12 And Select "Source" And Find Your JS File For Debug


For See More Go And Read https://www.w3schools.com/js/js_debugging.asp

Answer 3

When writing recursive functions, it is very possible that it may end up calling infinite with a stack overflow if it is repeating exactly the same again and again.

In your code, you are calling solve function which will loop from the start of grid up to the end. And again solve function called itself which caused to loop all over again and again... so it will never stops until stack overflow happens.

In below code, I am sure I did not solve your sudoku puzzle but at least it shows how to avoid calling infinitely by telling where to restart the loop so that it will not be looping all over again. Again, I did not solve your sudoku puzzle .. just a demo of recursive nature. I also added console.log so that you will be able to see how solve function is called with different parameters each time.

function solve(ystart, xstart) {
  console.log('solve(', ystart + ',' + xstart, ')');
  for (let y = ystart; y < 9; y++) {
    for (let x = xstart; x < 9; x++) {
      if (grid[y][x] === 0) {
        for (let n = 1; n < 10; n++) {
          if(possible(y,x,n)){
            grid[y][x] = n;
            solve(y, x);
            grid[y][x] = 0;
          }
        }
        return;
      }
    }
  }
}

solve(0, 0);