Sudoku Solver Using Backtracking in DSA C - Build from Scratch

Sudoku Solver Using Backtracking

📖 Scenario: You have a Sudoku puzzle with some numbers filled in and empty cells represented by 0. Your task is to write a program that solves the Sudoku puzzle by filling in the empty cells following Sudoku rules.Sudoku rules: Each row, each column, and each 3x3 box must contain the numbers 1 to 9 without repetition.

🎯 Goal: Build a Sudoku solver in C that uses backtracking to fill the empty cells and prints the solved Sudoku grid.

📋 What You'll Learn

Create a 9x9 integer array called board with the given Sudoku puzzle values

Create a function isSafe that checks if placing a number in a cell is valid

Create a function solveSudoku that uses backtracking to solve the puzzle

Print the solved Sudoku board in a 9x9 grid format

💡 Why This Matters

🌍 Real World

Sudoku solvers are used in puzzle games and apps to provide hints or verify solutions. Backtracking algorithms are also used in many constraint satisfaction problems like scheduling and resource allocation.

💼 Career

Understanding backtracking and constraint checking is important for software engineers working on algorithms, game development, AI, and optimization problems.

1

Create the Sudoku board

Create a 9x9 integer array called board and initialize it with the following Sudoku puzzle values exactly as shown (0 represents empty cells): { {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} }

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}
};
// Your code here

Hint

Use a 2D array with 9 rows and 9 columns. Use 0 for empty cells.

2

Create the isSafe function

Create a function called isSafe that takes four parameters: board (9x9 int array), row (int), col (int), and num (int). This function should return 1 if placing num at board[row][col] is valid according to Sudoku rules, otherwise return 0. Check the row, column, and 3x3 box for duplicates.

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

int isSafe(int board[9][9], int row, int col, int num) {
    // Your code here
}

Hint

Check the row and column for the number. Then check the 3x3 box by calculating the starting row and column of the box.

3

Create the solveSudoku function

Create a function called solveSudoku that takes board (9x9 int array) as a parameter and returns 1 if the Sudoku is solved, otherwise 0. Use backtracking: find an empty cell (0), try numbers 1 to 9, check if safe using isSafe, place the number, recursively call solveSudoku, and backtrack if needed.

DSA C

int solveSudoku(int board[9][9]) {
    // Your code here
}

Hint

Find the first empty cell. Try numbers 1 to 9. If safe, place the number and call solveSudoku recursively. If it fails, reset the cell to 0 and try next number.

4

Print the solved Sudoku board

Write code to call solveSudoku(board) and if it returns 1, print the solved Sudoku board in a 9x9 grid format. Print each number separated by a space and each row on a new line.

DSA C

int main() {
    if (solveSudoku(board)) {
        // Print the solved board here
    } else {
        printf("No solution exists\n");
    }
    return 0;
}

Hint

Call solveSudoku(board). If it returns 1, print the board row by row with spaces between numbers. Otherwise, print "No solution exists".