How to save the return in recursive function to a variable?

Question

I wrote a JavaScript to solve a Sudoku Puzzle using backtracking. My goal is to save the solution in a variable. Right now, I only can call the solution once.

var grid = [
  [0,1],
  [1,0]
]

function solve() {
  /// ... the recursive function that change the value of the grid variable.
  data = console.log(grid);
  return data;
}

var result = solve();

console.log(result);

My expected output for the console.log(result) is [[0,1], [1,0]] but instead, the output is undefined.

=== tl:dr

the sudoku solver in javascript

/// a string of digits, 1 - 9, and '.' as spaces. Each character represent a square, e.g.,
/// 5 3 . | . 7 . | . . .
/// 6 . . | 1 9 5 | . . .
/// . 9 8 | . . . | . 6 .
/// ------+-------+------
/// 8 . . | . 6 . | . . 3
/// 4 . . | 8 . 3 | . . 1
/// 7 . . | . 2 . | . . 6
/// ------+-------+------
/// . 6 . | . . . | 2 8 .
/// . . . | 4 1 9 | . . 5
/// . . . | . 8 . | . . .

var 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(r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

function solve() {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(r,c,n)) { 
              /// there is a possibility of the selected solution is a bad one.
              /// to solve this, use backtracking: try -> if it turns out the solution is a bad one, we go back to 0.
              grid[r][c] = n;
              /// recursion
              solve();
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
  data = console.log(grid);
  return data;
}

var result = solve()
console.log(result)

edit: using JSON.stringify and calling the solve() function does print the solution once but the return is still not saved to the variable.

...
      data = console.log(JSON.stringify(grid));
      return data;
    }
    
    var result = solve()
    console.log(result)

Answer 1

You have no check to see if you're completed. If you want to return the grid, then you should be checking to see whether it's complete before you backtrack. To do this, it makes much more sense to pass the grid around as a parameter, to solve, both from the outside and from the recursive call, and to possible. And writing an isSolved function is fairly trivial. I would just use const isComplete = grid => grid.every(row => !row.includes(0)), but the sample below shows one more similar to the rest of the code. These minimal changes should make it work for you:

function possible(grid, r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

// or just
// const isComplete = grid => grid.every(row => !row.includes(0))
const isComplete = function(grid) {
  return grid.every(function (row) {
    return row.every(function (cell) {
      return cell !== 0
    })
  })
} 

function solve(grid) {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(grid,r,c,n)) { 
              grid[r][c] = n;
              /// recursion
              grid = solve(grid) || grid; // keep the original if the recursive call returns nothing
              if (isComplete(grid)) {return grid} // *** This is what was really missing ***
              // backtrack
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
}

var 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],
];

var result = solve(grid)
console.log(result.map(r => r.join('')).join('\n')) // Format the output more readably

.as-console-wrapper {max-height: 100% !important; top: 0}

Answer 2

This resolves the error

/// a string of digits, 1 - 9, and '.' as spaces. Each character represent a square, e.g.,
/// 5 3 . | . 7 . | . . .
/// 6 . . | 1 9 5 | . . .
/// . 9 8 | . . . | . 6 .
/// ------+-------+------
/// 8 . . | . 6 . | . . 3
/// 4 . . | 8 . 3 | . . 1
/// 7 . . | . 2 . | . . 6
/// ------+-------+------
/// . 6 . | . . . | 2 8 .
/// . . . | 4 1 9 | . . 5
/// . . . | . 8 . | . . .

var 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(r,c,n) {
  /// check the row
  for (let i=0;i<9;i++) if (grid[r][i] == n) return false;
  /// check the column
  for (let i=0;i<9;i++) if (grid[i][c] == n) return false;
  /// check the 3x3 grid
  let r0 = Math.floor(r/3)*3;
  let c0 = Math.floor(c/3)*3;
  for (let i=0;i<3;i++) {
    for (let j=0;j<3;j++) {
      if (grid[r0+i][c0+j] == n) return false;
    }
  }
  /// all check passed
  return true;
}

function solve() {
    for (let r=0;r<9;r++) {
      for (let c=0;c<9;c++) {
        /// check grid with value of 0
        if (grid[r][c] === 0) {
          /// check for possible solution
          for (let n=1;n<10;n++) {
            if (possible(r,c,n)) { 
              /// there is a possibility of the selected solution is a bad one.
              /// to solve this, use backtracking: try -> if it turns out the solution is a bad one, we go back to 0.
              grid[r][c] = n;
              /// recursion
              solve();
              grid[r][c] = 0;
            }
          }
          /// if there is no solution, we have to return.
          return;
        }
      }
    }
  console.log(grid);
  

}
 
 var result = solve()


/// Difficulty represent the number of squares with digits.
/// "easy":      62
/// "easy-2":    53
/// "easy-3":    44
/// "medium":    35
/// "hard":      26
/// "very-hard": 17

Answer 3

You are assingning the variable data to the function console.log() which returns a non-object.You should instead return the value of grid from the function.

var grid = [
  [0,1],
  [1,0]
]

function solve() {
  /// ... the recursive function that change the value of the grid variable.
  return grid;
}

var result = solve();

console.log(result);

this should solve the issue.