Sudoku Solver Using Backtracking in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sudoku Board After One Step of Backtracking

Given the initial Sudoku board and one step of the backtracking algorithm filling the first empty cell, what is the printed board state?

DSA Java

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}
};

// After one step of backtracking, the first empty cell (row 0, col 2) is filled with 4
board[0][2] = 4;

// Print board function
for (int r = 0; r < 9; r++) {
  for (int c = 0; c < 9; c++) {
    System.out.print(board[r][c] + " ");
  }
  System.out.println();
}

A [[5,3,1,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]]

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

C [[5,3,9,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]]

D [[5,3,4,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]]

💡 Hint

Focus on the first empty cell in the top-left corner and the valid number that can be placed there.

The first empty cell at row 0, column 2 can only be filled with 4 according to Sudoku rules. The other options either leave it empty or fill it with invalid numbers.

❓ Predict Output

intermediate

Final Solved Sudoku Board Output

What is the final solved Sudoku board printed by the backtracking solver for the given puzzle?

DSA Java

int[][] solvedBoard = {
  {5,3,4,6,7,8,9,1,2},
  {6,7,2,1,9,5,3,4,8},
  {1,9,8,3,4,2,5,6,7},
  {8,5,9,7,6,1,4,2,3},
  {4,2,6,8,5,3,7,9,1},
  {7,1,3,9,2,4,8,5,6},
  {9,6,1,5,3,7,2,8,4},
  {2,8,7,4,1,9,6,3,5},
  {3,4,5,2,8,6,1,7,9}
};

for (int r = 0; r < 9; r++) {
  for (int c = 0; c < 9; c++) {
    System.out.print(solvedBoard[r][c] + " ");
  }
  System.out.println();
}

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

B [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]

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

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

💡 Hint

Check for any zeros or missing numbers in the options; the solved board has no zeros.

Option B shows the fully solved Sudoku board with all cells filled correctly. Other options have zeros indicating incomplete or incorrect solutions.

🧠 Conceptual

advanced

Why Backtracking is Suitable for Sudoku Solver

Which reason best explains why backtracking is a good approach to solve Sudoku puzzles?

A Backtracking tries all possible numbers in empty cells and undoes choices when conflicts occur, ensuring all solutions are explored systematically.

B Backtracking uses random guesses to fill cells quickly without checking constraints, making it faster than other methods.

C Backtracking solves Sudoku by sorting rows and columns to find the solution directly without trial and error.

D Backtracking only fills cells with the smallest possible number and never revisits previous choices.

💡 Hint

Think about how backtracking handles wrong choices and explores alternatives.

Backtracking systematically tries numbers and backtracks when conflicts arise, which fits Sudoku's constraint-based nature.

🔧 Debug

advanced

Identify the Bug in Sudoku Validity Check

What is the bug in this Sudoku validity check method that causes incorrect validation?

DSA Java

boolean isValid(int[][] board, int row, int col, int num) {
  for (int i = 0; i < 9; i++) {
    if (board[row][i] == num && i != col) return false;
    if (board[i][col] == num && i != row) return false;
  }
  int boxRowStart = row - row % 3;
  int boxColStart = col - col % 3;
  for (int r = boxRowStart; r < boxRowStart + 3; r++) {
    for (int c = boxColStart; c < boxColStart + 3; c++) {
      if (board[r][c] == num && (r != row || c != col)) return false;
    }
  }
  return true;
}

A The method misses checking the diagonal cells which are required in Sudoku rules.

B The method does not check the 3x3 box correctly because it uses wrong indices for boxRowStart and boxColStart.

C The method incorrectly returns false if the number is found in the same row or column, even if it's at the current cell being checked.

D The method does not check if the number is zero before validating, causing false negatives.

💡 Hint

Consider what happens if the current cell already contains the number being checked.

The method returns false if the number is found anywhere in the row or column, including the current cell, which should be ignored during validation.

🚀 Application

expert

Optimizing Sudoku Solver Performance

Which optimization technique can significantly reduce the search space and improve the performance of a backtracking Sudoku solver?

A Implementing constraint propagation by tracking possible candidates for each empty cell and choosing the cell with the fewest candidates first.

B Using a brute force approach that tries numbers sequentially without any heuristics.

C Sorting the entire board rows and columns before starting backtracking to reduce complexity.

D Randomly filling empty cells with numbers and restarting the solver if conflicts occur.

💡 Hint

Think about how to reduce unnecessary trials by focusing on the most constrained cells.

Constraint propagation and choosing the cell with the fewest options first (minimum remaining value heuristic) reduces backtracking steps and speeds up solving.

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