Sudoku Solver Using Backtracking in DSA C# - 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 backtracking filling the first empty cell, what is the printed state of the board?

DSA C#

int[,] board = new int[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 step of backtracking, the first empty cell (0,2) is filled with 1
board[0,2] = 1;

// Print board
for (int i = 0; i < 9; i++)
{
    for (int j = 0; j < 9; j++)
    {
        Console.Write(board[i,j] + " ");
    }
    Console.WriteLine();
}

A

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 

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

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

Look at the first empty cell in the top row and what number backtracking tries first.

Backtracking tries numbers 1 to 9 in order. The first empty cell is at (0,2). Number 1 is valid (no conflicts in row, column, or 3x3 subgrid) and placed.

🧠 Conceptual

intermediate

Understanding Backtracking in Sudoku Solver

Which of the following best describes the role of backtracking in solving Sudoku puzzles?

A Backtracking fills all empty cells with random numbers and then checks if the puzzle is solved.

B Backtracking tries numbers in empty cells and moves forward only if the number is valid, otherwise it goes back to try a different number.

C Backtracking solves Sudoku by sorting the numbers in each row and column.

D Backtracking removes numbers from the board until only one solution remains.

💡 Hint

Think about how backtracking explores possibilities and undoes choices.

Backtracking is a trial-and-error method that tries numbers in empty cells and backtracks if a conflict arises, ensuring only valid numbers remain.

🔧 Debug

advanced

Identify the Error in Sudoku Solver Code

What error will this code snippet cause when trying to solve Sudoku using backtracking?

DSA C#

bool IsSafe(int[,] board, 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 = startRow; i < startRow + 3; i++)
        for (int j = startCol; j < startCol + 3; j++)
            if (board[i, j] == num)
                return false;

    return true;
}

bool 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;
                        board[row, col] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

// Missing call to SolveSudoku(board) in main program

A The code will not solve the Sudoku because SolveSudoku is never called.

B The code will produce incorrect results because IsSafe does not check the entire board.

C The code will throw an IndexOutOfRangeException due to wrong loop bounds.

D The code will cause a stack overflow due to infinite recursion.

💡 Hint

Check if the main program actually starts the solving process.

The code defines the solving functions but never calls SolveSudoku, so the board remains unchanged.

📝 Syntax

advanced

Identify the Syntax Error in Sudoku Solver Code

Which option contains the syntax error preventing the Sudoku solver from compiling?

DSA C#

bool 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;
                        board[row, col] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

A All braces are correctly placed; no syntax error.

B Incorrect use of 'return false' inside the inner for loop without braces.

C The method header is missing a closing parenthesis.

D Missing semicolon after 'board[row, col] = num' line.

💡 Hint

Check each line carefully for missing punctuation or braces.

The code is syntactically correct with all braces and semicolons properly placed.

🚀 Application

expert

Final Sudoku Board After Complete Backtracking Solve

Given the initial Sudoku board below, what is the final solved board after running the complete backtracking solver?

DSA C#

int[,] board = new int[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 running SolveSudoku(board), print the board

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 0 
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 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 

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 fully solved Sudoku board has no zeros and respects all Sudoku rules.

Option C shows the fully solved Sudoku board with all cells filled correctly. Other options have zeros indicating incomplete cells.

Practice

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

easy

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

B. To randomly fill the Sudoku grid without checking rules

C. To sort the numbers in each row before solving

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

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

   Options A, B, and C do not describe backtracking's trial and error approach.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Try and undo choices [OK]

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

Common Mistakes:

• Thinking backtracking fills randomly without checks
• Confusing backtracking with sorting or counting
• Ignoring the undo step in backtracking

2. Which C# syntax correctly defines a method header for a Sudoku solver using backtracking that returns a boolean?

easy

A. public bool SolveSudoku(int[,] board)

B. bool SolveSudoku(int[][] board)

C. public void SolveSudoku(int[] board)

D. bool SolveSudoku(int[] board);

Solution

1. Step 1: Check method signature correctness

   public bool SolveSudoku(int[,] board) uses correct C# syntax: public access, bool return, 2D array parameter.

2. Step 2: Identify errors in other options

   bool SolveSudoku(int[][] board) uses wrong array syntax for C#, C uses void return instead of bool, D has semicolon ending which is invalid for method definition.

3. Final Answer:

   public bool SolveSudoku(int[,] board) -> Option A

4. Quick Check:

   Correct C# method header = public bool SolveSudoku(int[,] board) [OK]

Hint: Use public bool with int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax int[][] instead of int[,]
• Missing public keyword or wrong return type
• Ending method header with semicolon

3. What will be the output of the following code snippet when trying to solve a partially filled Sudoku board?

int[,] board = new int[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}
};
SudokuSolver solver = new SudokuSolver();
bool solved = solver.SolveSudoku(board);
Console.WriteLine(solved);

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand the input board

   The board is a valid partially filled Sudoku puzzle with zeros as empty cells.

2. Step 2: Analyze SolveSudoku method behavior

   Assuming correct backtracking implementation, the solver will find a solution and return true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Valid puzzle solved = true [OK]

Hint: Valid puzzles return true after solving [OK]

Common Mistakes:

• Assuming zeros cause errors instead of empty cells
• Thinking solver returns false without trying all options
• Confusing compilation/runtime errors with logic

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

bool IsSafe(int[,] board, 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[startRow + i, startCol + j] == num) return false;
    }
  }
  return true;
}

medium

A. The method does not check if the cell is already filled

B. The row and column checks are incomplete

C. No bug; the method correctly checks safety

D. The 3x3 box check uses wrong start indices calculation

Solution

1. Step 1: Review row and column checks

   The method checks all cells in the row and column for the number, which is correct.

2. Step 2: Review 3x3 box check

   Calculates startRow and startCol correctly using modulo, then checks all 3x3 cells.

3. Step 3: Confirm no missing checks

   Method returns true only if no conflicts found, so it is correct.

4. Final Answer:

   No bug; the method correctly checks safety -> Option C

5. Quick Check:

   Safety check correct = No bug; the method correctly checks safety [OK]

Hint: Check row, column, and 3x3 box carefully [OK]

Common Mistakes:

• Miscomputing start indices for 3x3 box
• Forgetting to check both row and column
• Assuming cell fill check is needed here

5. Given a Sudoku board with multiple empty cells, which strategy improves the backtracking solver's efficiency the most?

hard

A. Fill cells randomly to reduce search space

B. Always try numbers 1 to 9 in order without checks

C. Skip checking 3x3 boxes to save time

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

Solution

1. Step 1: Understand backtracking efficiency

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

2. Step 2: Evaluate other options

   Random filling (A) wastes time, trying numbers blindly (B) is inefficient, skipping box checks (D) breaks rules.

3. Final Answer:

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

4. Quick Check:

   Minimum options first = faster solving [OK]

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

Common Mistakes:

• Trying numbers in fixed order without heuristics
• Ignoring 3x3 box constraints
• Randomly filling cells hoping for quick solve