Sudoku Solver Using Backtracking in DSA Java - Build from Scratch

Sudoku Solver Using Backtracking

📖 Scenario: You have a partially filled Sudoku board. Your task is to complete the board so that every row, column, and 3x3 box contains all digits from 1 to 9 without repetition.Think of it like a puzzle where you fill empty cells with numbers following the rules.

🎯 Goal: Build a Sudoku solver that uses backtracking to fill the empty cells correctly.You will create the board, set up helper variables, write the backtracking logic, and finally print the solved board.

📋 What You'll Learn

Create a 9x9 integer array called board with the given Sudoku puzzle

Create a method isSafe to check if placing a number is valid

Create a method solveSudoku that uses backtracking to solve the puzzle

Print the solved Sudoku board in a readable format

💡 Why This Matters

🌍 Real World

Sudoku solvers help puzzle enthusiasts check solutions or generate puzzles. Backtracking is a common technique in constraint satisfaction problems.

💼 Career

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

1

Create the Sudoku board

Create a 9x9 integer array called board with the exact values given 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 Java

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

Hint

Use a 2D array with 9 rows and 9 columns. Use 0 for empty cells.

2

Create the isSafe method

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

DSA Java

public class SudokuSolver {
    static int[][] 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}
    };

    // Add the isSafe method below
    // Your code here
}

Hint

Check the row, column, and 3x3 box for the number. Return false if found, else true.

3

Create the solveSudoku method using backtracking

Add a static method called solveSudoku that returns boolean. It should find an empty cell (value 0), try numbers 1 to 9, check if safe using isSafe, place the number, and recursively call itself. If no number fits, reset cell to 0 and backtrack. Return true if solved, otherwise false.

DSA Java

public class SudokuSolver {
    static int[][] 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}
    };

    static boolean isSafe(int row, int col, int num) {
        for (int x = 0; x < 9; x++) {
            if (board[row][x] == num) return false;
            if (board[x][col] == num) return false;
        }
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[startRow + i][startCol + j] == num) return false;
            }
        }
        return true;
    }

    // Add the solveSudoku method below
    // Your code here
}

Hint

Use nested loops to find empty cells. Try numbers 1-9. Use recursion to continue solving. Backtrack if stuck.

4

Print the solved Sudoku board

Add a main method that calls solveSudoku(). If it returns true, print the solved board row by row with spaces between numbers. If not solved, print "No solution exists".

DSA Java

public class SudokuSolver {
    static int[][] 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}
    };

    static boolean isSafe(int row, int col, int num) {
        for (int x = 0; x < 9; x++) {
            if (board[row][x] == num) return false;
            if (board[x][col] == num) return false;
        }
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[startRow + i][startCol + j] == num) return false;
            }
        }
        return true;
    }

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

    // Add the main method below
    // Your code here
}

Hint

Call solveSudoku() in main. If true, print the board row by row with spaces. Else print "No solution exists".

Practice

1. What is the main purpose of backtracking in a Sudoku solver?

easy

A. To randomly fill the Sudoku board with numbers

B. To try possible numbers and undo choices if they lead to conflicts

C. To sort the Sudoku board numbers in ascending order

D. To count how many empty cells are in the Sudoku board

Solution

1. Step 1: Understand backtracking role

   Backtracking tries numbers in empty cells and removes them if they cause conflicts.

2. Step 2: Compare with other options

   Sorting or random filling does not solve Sudoku logically; counting empty cells is not solving.

3. Final Answer:

   To try possible numbers and undo choices if they lead to conflicts -> Option B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try and undo wrong moves [OK]

Common Mistakes:

• Thinking backtracking sorts numbers
• Assuming backtracking fills randomly
• Confusing backtracking with counting cells

2. Which of the following Java method signatures correctly represents a backtracking Sudoku solver method?

easy

A. public boolean solveSudoku(int[][] board)

B. void solveSudoku(int board[][])

C. public int solveSudoku(int[][] board, int row, int col)

D. boolean solveSudoku()

Solution

1. Step 1: Check method return type and parameters

   The solver should return boolean to indicate success and take the board as input.

2. Step 2: Validate options

   public boolean solveSudoku(int[][] board) matches this: returns boolean and takes int[][] board. void solveSudoku(int board[][]) returns void, not suitable. public int solveSudoku(int[][] board, int row, int col) returns int and has extra parameters, uncommon. boolean solveSudoku() has no parameters, so can't solve given board.

3. Final Answer:

   public boolean solveSudoku(int[][] board) -> Option A

4. Quick Check:

   Boolean return + board parameter = public boolean solveSudoku(int[][] board) [OK]

Hint: Solver returns boolean and takes board as int[][] [OK]

Common Mistakes:

• Using void return type for solver
• Missing board parameter
• Returning int instead of boolean

3. What will be the output of the following code snippet after calling solveSudoku(board) on a partially filled 9x9 Sudoku board?

int[][] 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}
};
boolean solved = solveSudoku(board);
System.out.println(solved);

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Understand the input board

   The given board is a valid Sudoku puzzle with empty cells (0) and solvable configuration.

2. Step 2: Analyze solveSudoku output

   Backtracking solver returns true if it finds a solution. Since this is a standard solvable puzzle, it returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Solvable board returns true [OK]

Hint: Valid puzzle solved returns true [OK]

Common Mistakes:

• Assuming false means no solution without checking
• Confusing output with board print
• Expecting exceptions on valid input

4. Identify the bug in this backtracking Sudoku solver snippet:

public boolean solveSudoku(int[][] board) {
  for (int row = 0; row < 9; row++) {
    for (int col = 0; col < 9; col++) {
      if (board[row][col] == 0) {
        for (int 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;
}

medium

A. Using wrong data type for board

B. Incorrect loop ranges for row and col

C. Not checking if board is already solved before recursion

D. Missing return false when no number fits in empty cell

Solution

1. Step 1: Analyze the nested loops and recursion

   The code tries numbers 1-9 in empty cells and recurses if safe.

2. Step 2: Identify missing return false

   If no number fits, the function should return false to backtrack, but here it continues loops and returns true at end incorrectly.

3. Final Answer:

   Missing return false when no number fits in empty cell -> Option D

4. Quick Check:

   Backtracking needs return false on failure [OK]

Hint: Return false if no valid number found in cell [OK]

Common Mistakes:

• Forgetting to return false to backtrack
• Returning true too early
• Ignoring base case for solved board

5. Given a 9x9 Sudoku board with multiple empty cells, which approach best improves the efficiency of the backtracking solver?

hard

A. Use a heuristic to select the empty cell with the fewest possible valid numbers first

B. Try numbers 1 to 9 in order for each empty cell without any checks

C. Fill all empty cells with 1 initially and then backtrack

D. Randomly assign numbers to empty cells and check if solved

Solution

1. Step 1: Understand naive backtracking

   Trying numbers 1-9 in order for each cell is simple but slow for complex puzzles.

2. Step 2: Identify heuristic improvement

   Selecting the empty cell with fewest valid options (minimum remaining value heuristic) reduces branching and speeds solving.

3. Step 3: Evaluate other options

   Filling all with 1 or random assignment leads to many conflicts and inefficiency.

4. Final Answer:

   Use a heuristic to select the empty cell with the fewest possible valid numbers first -> Option A

5. Quick Check:

   Heuristic cell choice speeds backtracking [OK]

Hint: Pick cell with fewest options first to speed solving [OK]

Common Mistakes:

• Trying numbers blindly without heuristics
• Filling cells with fixed number initially
• Random assignments causing many retries