Sudoku Solver Using Backtracking in DSA C#

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number doesn't fit until the puzzle is solved.

Analogy: It's like trying keys on a locked door: you try one key, if it doesn't open, you try another, and if none work, you go back and try a different key for the previous lock.

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9
↑

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku grid with empty cells as 0

Goal: Fill all empty cells with digits 1-9 so that each row, column, and 3x3 box contains all digits without repetition

Step 1: Find first empty cell at row 0, column 2; try number 1

5 3 [1] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try smallest number to see if it fits in the empty cell

Step 2: Check if 1 is valid in row 0, column 2; it's valid, so place it

5 3 1 | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 1 does not violate Sudoku rules here

Step 3: Move to next empty cell at row 0, column 3; try number 1

5 3 1 | [1] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try placing 1 in next empty cell

Step 4: Check if 1 is valid in row 0, column 3; it's invalid (already in row), try next number 2

5 3 1 | [2] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 1 conflicts, so try next number

Step 5: Check if 2 is valid in row 0, column 3; it's valid, place it

5 3 1 | 2 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 2 fits without conflicts

Step 6: Continue this process recursively until all empty cells are filled correctly

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

Why: Backtracking ensures all constraints are met and puzzle is solved

Result:

5 3 4 -> 6 7 8 -> 9 1 2 -> null
6 7 2 -> 1 9 5 -> 3 4 8 -> null
1 9 8 -> 3 4 2 -> 5 6 7 -> null
8 5 9 -> 7 6 1 -> 4 2 3 -> null
4 2 6 -> 8 5 3 -> 7 9 1 -> null
7 1 3 -> 9 2 4 -> 8 5 6 -> null
9 6 1 -> 5 3 7 -> 2 8 4 -> null
2 8 7 -> 4 1 9 -> 6 3 5 -> null
3 4 5 -> 2 8 6 -> 1 7 9 -> null

Annotated Code

DSA C#

using System;

class SudokuSolver
{
    private const int Size = 9;

    public static bool SolveSudoku(int[,] board)
    {
        for (int row = 0; row < Size; row++)
        {
            for (int col = 0; col < Size; col++)
            {
                if (board[row, col] == 0) // find empty cell
                {
                    for (int num = 1; num <= 9; num++)
                    {
                        if (IsValid(board, row, col, num))
                        {
                            board[row, col] = num; // place number

                            if (SolveSudoku(board))
                                return true; // solved

                            board[row, col] = 0; // backtrack
                        }
                    }
                    return false; // no valid number found
                }
            }
        }
        return true; // no empty cells left
    }

    private static bool IsValid(int[,] board, int row, int col, int num)
    {
        // check row
        for (int x = 0; x < Size; x++)
            if (board[row, x] == num)
                return false;

        // check column
        for (int y = 0; y < Size; y++)
            if (board[y, col] == num)
                return false;

        // check 3x3 box
        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;
    }

    public static void PrintBoard(int[,] board)
    {
        for (int i = 0; i < Size; i++)
        {
            for (int j = 0; j < Size; j++)
            {
                Console.Write(board[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main()
    {
        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}
        };

        if (SolveSudoku(board))
            PrintBoard(board);
        else
            Console.WriteLine("No solution exists");
    }
}

if (board[row, col] == 0) // find empty cell

locate next empty cell to fill

for (int num = 1; num <= 9; num++)

try all possible numbers 1 to 9

if (IsValid(board, row, col, num))

check if placing num breaks Sudoku rules

board[row, col] = num; // place number

tentatively place number in cell

if (SolveSudoku(board)) return true; // solved

recurse to solve rest of board

board[row, col] = 0; // backtrack

undo placement if dead end reached

return false; // no valid number found

trigger backtracking if no number fits

return true; // no empty cells left

all cells filled correctly, puzzle solved

Output

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 

Complexity Analysis

Time: O(9^(n)) where n is number of empty cells, because each empty cell tries up to 9 numbers recursively

Space: O(n) due to recursion stack depth proportional to number of empty cells

vs Alternative: Backtracking is more efficient than brute force checking all possible boards (9^81), but worst case can still be high; heuristic improvements can speed it up

Edge Cases

Empty board (all zeros)

Solver tries all possibilities, may take long but eventually finds a valid solution

DSA C#

if (board[row, col] == 0) // find empty cell

Already solved board

Solver quickly returns true without changes

DSA C#

return true; // no empty cells left

No solution board (contradictory clues)

Solver backtracks fully and returns false

DSA C#

return false; // no valid number found

When to Use This Pattern

When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it systematically tries options and undoes wrong choices.

Common Mistakes

Mistake: Not resetting the cell to zero when backtracking
Fix: Add 'board[row, col] = 0;' after recursive call fails to undo the tentative placement

Mistake: Checking only row or column but not 3x3 box for validity
Fix: Include 3x3 box check in IsValid function to ensure Sudoku rules

Summary

It fills empty Sudoku cells by trying numbers and backtracking on conflicts.

Use it when you need to solve puzzles with constraints and multiple choices.

The key insight is to try a choice, move forward, and undo if it leads to a dead end.

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