Sudoku Solver Using Backtracking in DSA Javascript - Build from Scratch

Sudoku Solver Using Backtracking

📖 Scenario: You have a Sudoku puzzle that is partially filled. Your task is to complete the puzzle by filling in the empty cells with numbers from 1 to 9 so that every row, column, and 3x3 box contains all digits from 1 to 9 without repetition.This is like solving a Sudoku puzzle on paper, but you will teach the computer to do it using a method called backtracking.

🎯 Goal: Build a Sudoku solver that takes a 9x9 grid with some empty cells (represented by 0) and fills it correctly using backtracking.

📋 What You'll Learn

Create a 9x9 two-dimensional array called board with the given Sudoku puzzle.

Create a helper function called isSafe to check if placing a number in a cell is valid.

Create a function called solveSudoku that uses backtracking to fill the board.

Print the solved Sudoku board in a readable format.

💡 Why This Matters

🌍 Real World

Sudoku solvers are used in puzzle games and apps to provide hints or check solutions automatically.

💼 Career

Understanding backtracking and constraint checking is useful in many fields like AI, game development, and solving complex problems.

1

Create the Sudoku board

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

[[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]]

DSA Javascript

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

Hint

Use const board = [ ... ] and copy the exact 9x9 array with zeros for empty cells.

2

Create the isSafe function

Create a function called isSafe that takes board, row, col, and num as parameters. It should return true if placing num at board[row][col] does not break Sudoku rules (no duplicates in the same row, column, or 3x3 box), otherwise false.

DSA Javascript

const board = [
  [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 duplicates, then check the 3x3 box using the start row and column.

3

Create the solveSudoku function using backtracking

Create a function called solveSudoku that takes board as a parameter. It should find the first empty cell (where value is 0), try numbers 1 to 9, check if placing the number is safe using isSafe, and recursively continue. If no number fits, backtrack by resetting the cell to 0 and return false. Return true if the board is solved.

DSA Javascript

const board = [
  [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, row, col, num) {
  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-9, check safety, and use recursion to solve. 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 using console.log. Each row should be printed as numbers separated by spaces.

DSA Javascript

const board = [
  [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, row, col, num) {
  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) {
  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) first. Then use a loop to print each row with numbers separated by spaces.

Practice

1. What is the main idea behind using backtracking to solve a Sudoku puzzle?

easy

A. Try placing numbers one by one and backtrack if a conflict occurs

B. Fill all empty cells randomly and check if the puzzle is solved

C. Use a sorting algorithm to arrange numbers in order

D. Replace all zeros with the number 9 directly

Solution

1. Step 1: Understand backtracking approach

   Backtracking tries numbers in empty cells one by one and checks if they fit the Sudoku rules.

2. Step 2: Handle conflicts by backtracking

   If a number causes a conflict, the algorithm removes it and tries the next number, going back if needed.

3. Final Answer:

   Try placing numbers one by one and backtrack if a conflict occurs -> Option A

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, check, undo if wrong [OK]

Common Mistakes:

• Thinking backtracking fills cells randomly
• Assuming sorting solves Sudoku
• Replacing zeros without checks

2. Which of the following is the correct way to check if a number can be placed in a Sudoku cell in JavaScript?

easy

A. if isSafe(board, row, col, num) { placeNumber(); }

B. if isSafe(board, row, col, num) then placeNumber();

C. if (isSafe board, row, col, num) { placeNumber(); }

D. if (isSafe(board, row, col, num)) { placeNumber(); }

Solution

1. Step 1: Understand JavaScript if syntax

   JavaScript requires parentheses around the condition in an if statement.

2. Step 2: Check function call syntax

   Function calls need parentheses with arguments inside, like isSafe(board, row, col, num).

3. Final Answer:

   if (isSafe(board, row, col, num)) { placeNumber(); } -> Option D

4. Quick Check:

   if(condition) with parentheses [OK]

Hint: Use parentheses around conditions in if statements [OK]

Common Mistakes:

• Missing parentheses in if condition
• Using 'then' keyword in JavaScript
• Incorrect function call syntax

3. What will be the output of the following code snippet when solving a Sudoku board?

const board = [
  [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]
];
solveSudoku(board);
console.log(board);

medium

A. An error because solveSudoku is not defined

B. The original board unchanged with zeros intact

C. A fully solved Sudoku board with no zeros

D. A partially solved board with some zeros replaced

Solution

1. Step 1: Understand solveSudoku function purpose

   solveSudoku uses backtracking to fill all empty cells correctly, solving the puzzle.

2. Step 2: Check console.log output after solving

   After solveSudoku runs, the board is fully solved with no zeros remaining.

3. Final Answer:

   A fully solved Sudoku board with no zeros -> Option C

4. Quick Check:

   Backtracking solves all cells [OK]

Hint: Backtracking fills all empty cells correctly [OK]

Common Mistakes:

• Expecting original board unchanged
• Thinking partial fill is final
• Assuming function is undefined

4. Consider this buggy code snippet for checking if a number can be placed in a Sudoku cell:

function isSafe(board, row, col, num) {
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num || board[x][col] === num) {
      return false;
    }
  }
  // Missing 3x3 box check
  return true;
}

What is the main problem here?

medium

A. It returns false too early

B. It does not check the 3x3 subgrid for duplicates

C. It uses wrong loop variable x

D. It modifies the board inside the function

Solution

1. Step 1: Analyze row and column checks

   The code correctly checks if num exists in the same row or column.

2. Step 2: Identify missing 3x3 subgrid check

   Sudoku rules require checking the 3x3 box; this code does not do that, causing errors.

3. Final Answer:

   It does not check the 3x3 subgrid for duplicates -> Option B

4. Quick Check:

   3x3 box check missing = bug [OK]

Hint: Always check row, column, and 3x3 box [OK]

Common Mistakes:

• Ignoring 3x3 box validation
• Thinking loop variable causes error
• Assuming early return is wrong

5. You want to optimize the Sudoku solver by choosing the next empty cell with the fewest possible valid numbers to try. Which technique does this describe?

hard

A. Heuristic with Minimum Remaining Value (MRV) strategy

B. Random guessing of empty cells

C. Depth-first search without pruning

D. Sorting the board rows before solving

Solution

1. Step 1: Understand MRV heuristic

   MRV chooses the empty cell with the fewest valid options to reduce branching and speed up solving.

2. Step 2: Compare with other options

   Random guessing and depth-first search without pruning are less efficient; sorting rows does not help solving.

3. Final Answer:

   Heuristic with Minimum Remaining Value (MRV) strategy -> Option A

4. Quick Check:

   MRV = choose cell with fewest options [OK]

Hint: Pick cell with fewest choices first [OK]

Common Mistakes:

• Confusing random guessing with heuristics
• Ignoring pruning benefits
• Thinking sorting helps solving