Program Structure

This program utilizes a backtracking algorithm to solve Sudoku puzzles. It recursively attempts to place digits in the empty cells while checking for valid placements according to Sudoku rules.

Key Components

• isSafe: A function that checks if a digit can be placed in a specific cell without violating Sudoku rules.
• solveSudoku: The main recursive function that implements the backtracking algorithm.
• printBoard: A utility function to display the Sudoku board.
• main: The entry point of the program where the Sudoku puzzle is initialized and solved.

Code

#include <iostream>
#include <vector>

using namespace std;

// Function to check if placing num at (row, col) is safe
bool isSafe(vector<vector<int>> &board, int row, int col, int num) {
    // Check the row and column
    for (int x = 0; x < 9; x++) {
        if (board[row][x] == num || board[x][col] == num)
            return false;
    }
    
    // Check the 3x3 grid
    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i + startRow][j + startCol] == num)
                return false;
        }
    }
    return true;
}

// Backtracking function to solve Sudoku
bool solveSudoku(vector<vector<int>> &board) {
    int row, col;
    bool isEmpty = true;

    // Find an empty cell
    for (row = 0; row < 9; row++) {
        for (col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
                isEmpty = false;
                break;
            }
        }
        if (!isEmpty) break;
    }

    // If there is no empty cell, the Sudoku is solved
    if (isEmpty) return true;

    // Try numbers 1 to 9
    for (int num = 1; num <= 9; num++) {
        if (isSafe(board, row, col, num)) {
            board[row][col] = num; // Place the number

            // Recursively try to solve the Sudoku
            if (solveSudoku(board)) return true;

            // If not successful, backtrack
            board[row][col] = 0;
        }
    }
    return false; // Triggers backtracking
}

// Function to print the Sudoku board
void printBoard(const vector<vector<int>> &board) {
    for (const auto &row : board) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

// Main function
int main() {
    // Initial Sudoku board (0 represents empty cells)
    vector<vector<int>> board = {
        {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 {
        cout << "No solution exists." << endl;
    }

    return 0;
}

Explanation of the Program Structure

• Functions:
  • isSafe: Validates if a number can be placed in a specific cell based on Sudoku rules (checking row, column, and 3×3 grid).
  • solveSudoku: Implements the backtracking algorithm to fill the board.
  • printBoard: Displays the current state of the Sudoku board.
• Main Logic:
  • The program initializes a Sudoku puzzle and calls solveSudoku. If a solution is found, it prints the solved board; otherwise, it indicates that no solution exists.

How to Run the Program

1. Copy the code into a file named SudokuSolver.cpp.
2. Compile the program using a C++ compiler, e.g., g++ SudokuSolver.cpp -o SudokuSolver.
3. Run the compiled program: ./SudokuSolver.

Conclusion

This Sudoku solver demonstrates the use of backtracking, a common algorithmic technique for solving constraint satisfaction problems. The program can be easily modified to accept different Sudoku puzzles by changing the initial board configuration.