Objective

The objective of this program is to provide a solution for a given Sudoku puzzle using a backtracking algorithm. The program will take a partially filled 9×9 Sudoku grid as input and attempt to fill it according to the rules of Sudoku, ensuring that each row, column, and 3×3 subgrid contains all digits from 1 to 9 without repetition.

C Code for Sudoku Solver

#include 
#include 

#define N 9

bool isSafe(int grid[N][N], int row, int col, int num) {
    for (int x = 0; x < N; x++) {
        if (grid[row][x] == num || grid[x][col] == num || 
            grid[row - row % 3 + x / 3][col - col % 3 + x % 3] == num) {
            return false;
        }
    }
    return true;
}

bool solveSudoku(int grid[N][N]) {
    int row, col;
    bool empty = true;

    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (grid[row][col] == 0) {
                empty = false;
                break;
            }
        }
        if (!empty) break;
    }

    if (empty) return true;

    for (int num = 1; num <= N; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;

            if (solveSudoku(grid)) {
                return true;
            }

            grid[row][col] = 0; // backtrack
        }
    }
    return false;
}

void printGrid(int grid[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            printf("%d ", grid[row][col]);
        }
        printf("\n");
    }
}

int main() {
    int grid[N][N] = {
        {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(grid)) {
        printGrid(grid);
    } else {
        printf("No solution exists\n");
    }
    
    return 0;
}
    

Program Structure Explanation

The program consists of several key functions:

• isSafe: This function checks if it’s safe to place a number in a given cell by ensuring that the number does not already exist in the current row, column, and 3×3 subgrid.
• solveSudoku: This function implements the backtracking algorithm. It looks for an empty cell (represented by 0) and attempts to place each number (1-9) in that cell. If a number leads to a solution, it returns true; if not, it backtracks and tries the next number.
• printGrid: This function prints the Sudoku grid to the console.
• main: This function initializes a sample Sudoku grid and calls the solver function. It also handles the output of the solved grid or a message indicating that no solution exists.

How to Run the Program

1. Copy the C code into a text file and save it as sudoku_solver.c.
2. Open a terminal (command prompt) and navigate to the directory where the file is saved.
3. Compile the program using a C compiler, such as gcc:

   gcc sudoku_solver.c -o sudoku_solver

4. Run the compiled program:

   ./sudoku_solver

5. The program will display the solved Sudoku grid in the terminal.