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.