Sudoku Solver Using Backtracking in DSA Typescript - Build from Scratch

Sudoku Solver Using Backtracking

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Sudoku solvers are examples of constraint satisfaction problems used in AI and logic programming. Understanding backtracking helps solve puzzles and complex decision problems.

💼 Career

Backtracking algorithms are used in software engineering for solving puzzles, scheduling, and optimization problems. This project builds problem-solving and algorithmic thinking skills valuable for coding interviews and real-world tasks.

1

Setup the Sudoku board

Create a 9x9 two-dimensional array called board with the exact values given below. Use 0 to represent empty cells.

Row 0: [5, 3, 0, 0, 7, 0, 0, 0, 0]
Row 1: [6, 0, 0, 1, 9, 5, 0, 0, 0]
Row 2: [0, 9, 8, 0, 0, 0, 0, 6, 0]
Row 3: [8, 0, 0, 0, 6, 0, 0, 0, 3]
Row 4: [4, 0, 0, 8, 0, 3, 0, 0, 1]
Row 5: [7, 0, 0, 0, 2, 0, 0, 0, 6]
Row 6: [0, 6, 0, 0, 0, 0, 2, 8, 0]
Row 7: [0, 0, 0, 4, 1, 9, 0, 0, 5]
Row 8: [0, 0, 0, 0, 8, 0, 0, 7, 9]

DSA Typescript

# Create the 9x9 board array with the given values
# Your code here

Hint

Use a constant named board and assign it a 2D array with the exact rows and values given.

2

Create the isSafe helper function

Create a function called isSafe that takes board, row, col, and num as parameters and returns true if placing num in board[row][col] does not break Sudoku rules. Check the row, column, and 3x3 box for duplicates.

DSA Typescript

const board: number[][] = [
  [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]
];

// Create the isSafe function below
# Your code here

Hint

Check the row and column for the number, then check the 3x3 box using the starting row and column calculated by row - (row % 3) and col - (col % 3).

3

Create the solveSudoku function using backtracking

Create a function called solveSudoku that takes board as a parameter and returns true if the Sudoku is solved. Use nested loops to find an empty cell (value 0). For each empty cell, try numbers 1 to 9. Use isSafe to check if the number can be placed. If yes, place the number and recursively call solveSudoku. If recursion returns false, reset the cell to 0 and try the next number. Return true if the board is solved, otherwise false.

DSA Typescript

const board: number[][] = [
  [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 isSafe(board: number[][], row: number, col: number, num: number): boolean {
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) return false;
    if (board[x][col] === num) return false;
  }
  const startRow = row - (row % 3);
  const startCol = col - (col % 3);
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[startRow + i][startCol + j] === num) return false;
    }
  }
  return true;
}

// Create the solveSudoku function below
# Your code here

Hint

Use nested loops to find empty cells. Try numbers 1 to 9. Use recursion to continue solving. Backtrack by resetting cells if needed.

4

Print the solved Sudoku board

Call solveSudoku(board) to solve the puzzle. Then print the solved board row by row. Use console.log to print each row as a space-separated string of numbers.

DSA Typescript

const board: number[][] = [
  [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 isSafe(board: number[][], row: number, col: number, num: number): boolean {
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) return false;
    if (board[x][col] === num) return false;
  }
  const startRow = row - (row % 3);
  const startCol = col - (col % 3);
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[startRow + i][startCol + j] === num) return false;
    }
  }
  return true;
}

function solveSudoku(board: number[][]): boolean {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        for (let num = 1; num <= 9; num++) {
          if (isSafe(board, row, col, num)) {
            board[row][col] = num;
            if (solveSudoku(board)) {
              return true;
            } else {
              board[row][col] = 0;
            }
          }
        }
        return false;
      }
    }
  }
  return true;
}

// Call solveSudoku and print the board
# Your code here

Hint

Call solveSudoku(board). If it returns true, print each row of board using console.log(board[row].join(' ')).