Sudoku Solver Using Backtracking in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partial Sudoku Board After One Backtracking Step

Given the partial Sudoku board and the backtracking step shown, what is the state of the board after placing the first valid number in the empty cell at row 0, column 2?

DSA C++

int board[9][9] = {
  {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}
};
// First empty cell at (0,2) tries numbers 1 to 9
// Number 1 is valid and placed
board[0][2] = 1;

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

B [[5,3,2,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,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]]

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

💡 Hint

Check which numbers can be placed in the empty cell without breaking Sudoku rules.

The first empty cell at (0,2) can accept number 1 without conflicts in row, column, or 3x3 box. So the board updates with 1 at that position.

🧠 Conceptual

intermediate

Why Backtracking Works for Sudoku Solving

Why is backtracking a suitable method to solve Sudoku puzzles?

A Because it uses random guesses to fill cells quickly without checking conflicts.

B Because it tries all possible numbers in empty cells and backtracks when a conflict occurs, ensuring all possibilities are explored.

C Because it fills all cells with the same number and then adjusts the board.

D Because it sorts the numbers in each row to find the solution.

💡 Hint

Think about how the algorithm handles wrong choices.

Backtracking tries numbers one by one in empty cells. If a number causes a conflict later, it goes back and tries another number. This systematic trial and error ensures the puzzle is solved correctly.

🔧 Debug

advanced

Identify the Bug in Sudoku Validity Check Function

What is the bug in this validity check function for Sudoku, and what error will it cause? bool isValid(int board[9][9], 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; }

A The startRow and startCol calculations are incorrect, causing out-of-bound errors.

B The function does not check the entire row and column, causing incomplete validation.

C The assignment operator '=' is used instead of '==' in the 3x3 box check, causing the board to be modified and always returning false.

D The function returns true too early before checking all conditions.

💡 Hint

Look carefully at the condition inside the nested loops for the 3x3 box.

Using '=' instead of '==' assigns num to the cell, corrupting the board and causing the function to return false incorrectly.

📝 Syntax

advanced

Correct Syntax for Recursive Sudoku Solver Function

Which option shows the correct syntax for the recursive call in a Sudoku solver function that tries to fill the board?

DSA C++

bool solveSudoku(int board[9][9]) {
  int row, col;
  if (!findEmptyCell(board, row, col)) return true;
  for (int num = 1; num <= 9; num++) {
    if (isValid(board, row, col, num)) {
      board[row][col] = num;
      // recursive call here
      ...
      board[row][col] = 0;
    }
  }
  return false;
}

A if (solveSudoku(board)) return true;

B if solveSudoku(board) return true;

C if (solveSudoku(board)); return true;

D if solveSudoku(board); return true;

💡 Hint

Remember the syntax for if statements in C++.

Option A uses correct syntax with parentheses and no extra semicolon after the if condition.

🚀 Application

expert

Number of Recursive Calls in Worst Case for Empty Sudoku Board

If the Sudoku solver uses backtracking on an empty 9x9 board (all cells empty), approximately how many recursive calls will it make in the worst case before finding a solution or concluding none exists?

A More than 1,000,000 calls

B Around 10,000 calls

C Less than 1,000 calls

D Exactly 81 calls

💡 Hint

Consider the branching factor and depth of recursion in backtracking.

Backtracking tries many possibilities for each empty cell. With 81 empty cells and up to 9 choices each, the worst case is exponential, leading to over a million calls.

Practice

1. What is the main idea behind the backtracking technique used in a Sudoku solver?

easy

A. Use a fixed pattern to fill the board

B. Fill the board randomly without checking rules

C. Try placing numbers and undo if they lead to conflicts

D. Only fill cells with a single possible number

Solution

1. Step 1: Understand backtracking in Sudoku

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

2. Step 2: Undo if conflict arises

   If a number causes a conflict later, it is removed (backtracked) and another number is tried.

3. Final Answer:

   Try placing numbers and undo if they lead to conflicts -> Option C

4. Quick Check:

   Backtracking = Try and undo [OK]

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

Common Mistakes:

• Thinking backtracking fills randomly
• Assuming backtracking fills only once without undo
• Believing backtracking uses fixed patterns

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

easy

A. if (isSafe(board, row, col, num)) { board[row][col] = num; }

B. if (board[row][col] == num) { placeNumber(); }

C. if (num > 9) { board[row][col] = num; }

D. if (board[row][col] != 0) { board[row][col] = num; }

Solution

1. Step 1: Understand the safety check function

   The function isSafe checks if placing num at board[row][col] follows Sudoku rules.

2. Step 2: Place number only if safe

   Only if isSafe returns true, the number is placed in the cell.

3. Final Answer:

   if (isSafe(board, row, col, num)) { board[row][col] = num; } -> Option A

4. Quick Check:

   Use isSafe before placing number [OK]

Hint: Always check safety before placing number [OK]

Common Mistakes:

• Placing number without checking rules
• Checking if cell already has the number incorrectly
• Using invalid conditions for placement

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

int board[9][9] = {
  {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);

Assuming solveSudoku correctly solves the puzzle, what will be the value at board[0][2] after solving?

medium

A. 9

B. 4

C. 7

D. 1

Solution

1. Step 1: Identify the empty cell at (0,2)

   The cell at row 0, column 2 is initially 0 (empty).

2. Step 2: Solve Sudoku and find correct number

   After solving, the number 4 fits at (0,2) without conflicts in row, column, or box.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   board[0][2] = 4 after solve [OK]

Hint: Check solved board cell for correct number [OK]

Common Mistakes:

• Guessing without checking Sudoku rules
• Confusing row and column indices
• Assuming initial zeros remain zeros

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

bool isSafe(int board[9][9], int row, int col, int num) {
  for (int x = 0; x < 9; x++) {
    if (board[row][x] == num || 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[i][j] == num)
        return false;
    }
  }
  return true;
}

What is the bug in this code?

medium

A. The 3x3 box check uses wrong indices; should use startRow + i and startCol + j

B. The row and column checks are missing

C. The function does not return false when number is found

D. The modulo operation is incorrect

Solution

1. Step 1: Analyze 3x3 box checking loop

   The inner loop checks board[i][j] instead of board[startRow + i][startCol + j], so it checks wrong cells.

2. Step 2: Correct indices for box check

   To check the correct 3x3 box, add startRow and startCol offsets to i and j.

3. Final Answer:

   The 3x3 box check uses wrong indices; should use startRow + i and startCol + j -> Option A

4. Quick Check:

   Box check indices must include startRow/startCol [OK]

Hint: Add startRow/startCol offsets when checking 3x3 box [OK]

Common Mistakes:

• Checking wrong cells in 3x3 box
• Ignoring row or column checks
• Incorrect modulo usage

5. You want to optimize a Sudoku solver using backtracking by adding a heuristic. Which of the following strategies best reduces the search space?

hard

A. Fill cells row-wise ignoring constraints until stuck

B. Try numbers in random order for each empty cell

C. Always fill the first empty cell found without checking possibilities

D. Choose the empty cell with the fewest possible valid numbers first

Solution

1. Step 1: Understand heuristic to reduce search space

   Choosing the cell with the fewest valid options first reduces branching and speeds up solving.

2. Step 2: Compare other strategies

   Filling first empty cell or random tries increase backtracking steps; ignoring constraints causes errors.

3. Final Answer:

   Choose the empty cell with the fewest possible valid numbers first -> Option D

4. Quick Check:

   Minimum remaining values heuristic = choose cell with fewest options [OK]

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

Common Mistakes:

• Filling cells without checking possibilities
• Trying numbers randomly wastes time
• Ignoring constraints leads to wrong solutions