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 initial Sudoku board and one step of backtracking filling the first empty cell, what is the board state?

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

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

// Print the board row 0
printf("%d %d %d %d %d %d %d %d %d\n", board[0][0], board[0][1], board[0][2], board[0][3], board[0][4], board[0][5], board[0][6], board[0][7], board[0][8]);

A [5, 3, 9, 0, 7, 0, 0, 0, 0]

B [5, 3, 0, 4, 7, 0, 0, 0, 0]

C [5, 3, 1, 0, 7, 0, 0, 0, 0]

D [5, 3, 4, 0, 7, 0, 0, 0, 0]

💡 Hint

The first empty cell in the top-left 3x3 box is at row 0, column 2. The number 4 fits there without breaking Sudoku rules.

Backtracking tries numbers from 1 to 9 in the first empty cell. 4 is the first valid number that does not conflict with existing numbers in the row, column, or 3x3 box.

🧠 Conceptual

intermediate

Why Backtracking is Suitable for Sudoku Solving

Why is backtracking a good method to solve Sudoku puzzles?

A Because it tries all possible numbers in empty cells and backtracks when a conflict occurs.

B Because it sorts the numbers in each row before filling cells.

C Because it uses random guesses to fill the board quickly.

D Because it fills all cells with the same number first.

💡 Hint

Think about how backtracking explores choices and undoes wrong ones.

Backtracking systematically tries numbers in empty cells and undoes choices if they lead to conflicts, ensuring a valid solution.

🔧 Debug

advanced

Identify the Bug in Sudoku Validity Check Function

What is wrong with this validity check function for Sudoku?

DSA C

int isValid(int board[9][9], int row, int col, int num) {
  for (int x = 0; x < 9; x++) {
    if (board[row][x] == num && x != col) return 0;
    if (board[x][col] == num && x != row) return 0;
  }
  int startRow = row - row % 3;
  int startCol = col - col % 3;
  for (int i = startRow; i < startRow + 3; i++) {
    for (int j = startCol; j < startCol + 3; j++) {
      if (board[i][j] == num && (i != row || j != col)) return 0;
    }
  }
  return 1;
}

A It does not check if the current cell already contains num, causing false negatives.

B It checks the entire row and column including the current cell, causing false negatives.

C It incorrectly calculates the starting row and column of the 3x3 box.

D It returns 1 instead of 0 when a conflict is found.

💡 Hint

Check if the function compares the cell with itself when checking row and column.

The function checks the entire row and column including the current cell, so if the current cell already has num, it returns false incorrectly.

❓ Predict Output

advanced

Final Sudoku Board After Complete Backtracking

What is the final solved Sudoku board after running the backtracking solver on this puzzle?

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

// After solving, the board is:
// 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

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,4],[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,0],[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,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]]

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

💡 Hint

The final solved board has no zeros and respects Sudoku rules in all rows, columns, and boxes.

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

🚀 Application

expert

Time Complexity of Sudoku Solver Using Backtracking

What is the worst-case time complexity of a Sudoku solver using backtracking on a 9x9 board?

A O(9*81) because it tries 9 numbers for each of the 81 cells once

B O(81^9) because each number 1-9 is placed in 81 cells

C O(9^(81)) because each of the 81 cells can have up to 9 choices

D O(1) because Sudoku has a fixed size board

💡 Hint

Consider the maximum number of choices per empty cell and total empty cells.

Backtracking tries up to 9 numbers in each of the 81 cells in the worst case, leading to O(9^81) complexity.

Practice

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

easy

A. To sort the Sudoku grid before solving

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

C. To fill all empty cells with zeros

D. To randomly assign numbers to cells

Solution

1. Step 1: Understand backtracking role

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

2. Step 2: Compare other options

   Sorting or random assignment does not solve Sudoku logically; filling zeros is incorrect.

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 the grid
• Assuming backtracking fills zeros
• Believing numbers are assigned randomly

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(row, col, num)) { place num; }

B. if isSafe(row, col, num) { place num; }

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

D. if (isSafe[row, col, num]) { place num; }

Solution

1. Step 1: Understand C syntax for if condition

   In C, conditions must be inside parentheses and followed by braces for blocks.

2. Step 2: Analyze options

   if (isSafe(row, col, num)) { place num; } uses correct syntax: if(condition) { ... }. Others miss parentheses or use wrong brackets.

3. Final Answer:

   if (isSafe(row, col, num)) { place num; } -> Option A

4. Quick Check:

   C if syntax = if(condition) { } [OK]

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

Common Mistakes:

• Omitting parentheses in if condition
• Using square brackets instead of parentheses
• Adding semicolon after if condition

3. What will be the output of the following code snippet that tries to solve a Sudoku puzzle using backtracking?

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}
};
if (solveSudoku(board)) {
  printBoard(board);
} else {
  printf("No solution exists\n");
}

medium

A. Infinite loop occurs

B. No solution exists

C. Compilation error due to missing function

D. The completed Sudoku board printed correctly

Solution

1. Step 1: Understand the given board and solveSudoku function

   The board is a valid Sudoku puzzle with empty cells as 0. solveSudoku uses backtracking to fill it.

2. Step 2: Predict output of solveSudoku

   Since the puzzle is solvable, solveSudoku returns true and printBoard prints the completed board.

3. Final Answer:

   The completed Sudoku board printed correctly -> Option D

4. Quick Check:

   Solvable board = completed print [OK]

Hint: Valid puzzles print solved board, else print no solution [OK]

Common Mistakes:

• Assuming no solution exists for valid puzzles
• Expecting compilation error without full code
• Thinking infinite loop happens without base case

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

bool solveSudoku(int board[9][9]) {
  int row, col;
  if (!findEmptyCell(board, &row, &col))
    return true;
  for (int num = 1; num <= 9; num++) {
    if (isSafe(board, row, col, num)) {
      board[row][col] = num;
      if (solveSudoku(board))
        return true;
      board[row][col] = 0;
    }
  }
  return false;
}

medium

A. Incorrect loop range for numbers (should be 0 to 9)

B. Not resetting cell to 0 after backtracking

C. No bug; code works correctly

D. Missing base case to stop recursion

Solution

1. Step 1: Check base case and recursion

   Base case returns true if no empty cell found, stopping recursion correctly.

2. Step 2: Verify backtracking steps

   After trying a number, if it fails, cell resets to 0, allowing other tries.

3. Step 3: Confirm loop range

   Loop runs from 1 to 9, which is correct for Sudoku numbers.

4. Final Answer:

   No bug; code works correctly -> Option C

5. Quick Check:

   Backtracking code correct = no bug [OK]

Hint: Check base case, reset cell, and loop range carefully [OK]

Common Mistakes:

• Forgetting to reset cell after failed attempt
• Wrong loop range including 0
• Missing base case causing infinite recursion

5. Given a partially filled Sudoku board, which strategy improves backtracking efficiency the most?

hard

A. Use constraint propagation to reduce possible numbers before backtracking

B. Always try numbers 1 to 9 in order for each empty cell

C. Fill empty cells randomly and backtrack if conflict occurs

D. Skip checking row and column constraints to save time

Solution

1. Step 1: Understand backtracking efficiency

   Trying all numbers blindly is slow; skipping checks causes wrong solutions.

2. Step 2: Analyze constraint propagation

   Constraint propagation narrows choices before backtracking, reducing search space and speeding solving.

3. Step 3: Evaluate other options

   Random filling is inefficient; skipping constraints breaks Sudoku rules.

4. Final Answer:

   Use constraint propagation to reduce possible numbers before backtracking -> Option A

5. Quick Check:

   Constraint propagation = faster solving [OK]

Hint: Reduce choices first, then backtrack for speed [OK]

Common Mistakes:

• Trying numbers in fixed order without pruning
• Random filling wastes time
• Ignoring constraints breaks puzzle rules