Solving Sudoku Puzzles: A Step-by-Step Guide with JavaScript Code Examples

Solve a Sudoku puzzle by filling the empty cells in JavaScript

This solution uses a recursive backtracking approach. The solveSudoku function checks if the input is valid and then calls the helper function solveHelper with the starting position (row 0, column 0). The solveHelper function first checks if the current cell is already filled, in which case it moves to the next column. If the current cell is empty, it tries to fill it with a valid number (between 1 and 9) and recursively calls itself with the next column. If a solution is found (i.e., the function returns true), it stops the recursion and returns true. If no valid solution is found, it backtracks by resetting the current cell to ‘.’ and trying a different number. If all numbers have been tried without success, it backtracks further by returning false.

The isValid function checks if a given number can be placed in a given cell without violating the rules of Sudoku. It first checks if the number already exists in the same row or column. It then calculates the starting row and column of the 3x3 sub-box containing the cell and checks if the number already exists in that sub-box. If the number passes all these checks, it is considered valid and can be placed in the cell.

Intuition

One approach to solving this problem is to use backtracking. We can iterate over each cell of the board, and if the cell is empty, we can try to fill it with a number from 1 to 9. Then, we can check if the board is still valid after filling the cell with that number. If it is, we move on to the next empty cell and repeat the process. If at any point we find that we cannot fill a cell with any valid number, we backtrack to the previous cell and try a different number. We keep doing this until we have filled all the empty cells and the board is valid, or until we have exhausted all possibilities and determined that the board has no valid solution.

Approach

To solve the Sudoku puzzle, we will use a recursive approach known as backtracking. We will try to place digits one by one in empty cells, starting from 1 to 9. Whenever we place a digit, we will check if it is valid by checking if it follows the Sudoku rules mentioned in the problem statement. If the digit is valid, we will move on to the next empty cell and repeat the same process. If the digit is not valid, we will backtrack and try the next possible digit.

We will define a function solve sudoku that takes the Sudoku board as input and returns the solved Sudoku board. This function will call another recursive function to solve that will do the actual work of solving the Sudoku puzzle.

The solve function will take the Sudoku board, row number, and column number as input. It will check if the current cell is empty or not. If the cell is not empty, it will move on to the next cell. If the cell is empty, it will try to place digits one by one and check if the digit is valid or not. If the digit is valid, it will move on to the next cell and repeat the same process. If the digit is not valid, it will backtrack and try the next possible digit.

We will use a helper function isValid to check if a digit is valid or not. This function will take the Sudoku board, row number, column number, and digit as input and return a boolean value indicating if the digit is valid or not. The isValid function will check if the digit occurs in the same row, same column, or same 3x3 sub-box. If the digit does not occur in any of these locations, it is valid.

Once we have solved the Sudoku puzzle using the solve function, we will return the solved Sudoku board.

Complexity

• Time complexity:
  It’s difficult to give a precise time complexity without analyzing the implementation details of the algorithm used, but in general, the time complexity of solving a Sudoku puzzle using a backtracking algorithm is exponential, i.e. O(9^(n*n)), where n is the size of the Sudoku grid (9 for a standard 9x9 grid). This is because at each empty cell, the algorithm must try all possible values (1–9) until a valid solution is found.

However, in practice, the actual time complexity of the algorithm will depend on factors such as the number of empty cells in the initial grid and the efficiency of the implementation. In some cases, the algorithm may terminate much faster than the worst-case time complexity suggests.

Space complexity:
The space complexity of the backtracking algorithm is O(n²) because it requires a 2D array to represent the Sudoku grid. Additionally, the recursive stack used by the algorithm can also contribute to the space complexity, although it’s generally not a significant factor.

• Space complexity:
  The space complexity of the algorithm is also O(1). We are not using any extra space, except for the output array board which is given in the input and thus doesn’t count towards our space complexity. We are modifying the input board in place, which means we are not using any additional space.
• Summary
  The program aims to solve a Sudoku puzzle by filling the empty cells. It is guaranteed that the input board has only one solution. The solution must satisfy all the rules of Sudoku, which means that each digit from 1–9 must occur exactly once in each row, column, and each of the 9 3x3 sub-boxes of the grid. The solution is obtained through the backtracking algorithm, where the program repeatedly fills the empty cells with numbers that satisfy the Sudoku rules until a valid solution is found. The time complexity of this solution is
  �
  (
  9
  �
  )
  O(9
  m
  ), where m is the number of empty cells. The space complexity is
  �
  (
  1
  )
  O(1).

Code

function solveSudoku(board) {
  if (!board || board.length !== 9 || board[0].length !== 9) {
    return;
  }
  solveHelper(board, 0, 0);
}

function solveHelper(board, row, col) {
  if (col === 9) {
    row++;
    col = 0;
    if (row === 9) {
      return true; // the board is solved
    }
  }
  if (board[row][col] !== '.') {
    return solveHelper(board, row, col + 1);
  }
  for (let num = 1; num <= 9; num++) {
    if (isValid(board, row, col, num)) {
      board[row][col] = num.toString();
      if (solveHelper(board, row, col + 1)) {
        return true; // found a solution
      }
      board[row][col] = '.'; // backtrack
    }
  }
  return false; // no valid solution found
}
function isValid(board, row, col, num) {
  for (let i = 0; i < 9; i++) {
    if (board[row][i] === num.toString() || board[i][col] === num.toString()) {
      return false; // the number already exists in the row or column
    }
  }
  const rowStart = Math.floor(row / 3) * 3;
  const colStart = Math.floor(col / 3) * 3;
  for (let i = rowStart; i < rowStart + 3; i++) {
    for (let j = colStart; j < colStart + 3; j++) {
      if (board[i][j] === num.toString()) {
        return false; // the number already exists in the 3x3 sub-box
      }
    }
  }
  return true;
}

leetcode link: https://leetcode.com/problems/sudoku-solver/solutions/3375819/javascript-solution-solve-sudoku-puzzle-using-javascript/

github: https://github.com/itznur07

twitter: https://twitter.com/itznur07