Sudoku Solver Program in C++

Introduction

Sudoku is a logic-based number placement puzzle. The goal of the puzzle is to fill a 9×9 grid with digits
so that each column, each row, and each of the nine 3×3 subgrids contain all of the digits from 1 to 9.

In this tutorial, we will create a program in C++ to solve a Sudoku puzzle using the Backtracking algorithm.
The backtracking approach tries to solve the puzzle by filling in the numbers and backtracking when it hits a dead-end.

Objective

The objective of this C++ program is to implement a Sudoku solver that can efficiently solve a given Sudoku puzzle.
This program will take a partially filled 9×9 Sudoku grid and attempt to solve it. If the puzzle is solvable, the program
will display the solved grid, otherwise, it will indicate that the puzzle cannot be solved.

Program Code

        #include 
        using namespace std;

        // Function to check if a number can be placed in the current cell
        bool isSafe(int board[9][9], int row, int col, int num) {
            // Check if the number is in the current row or column
            for (int i = 0; i < 9; i++) {
                if (board[row][i] == num || board[i][col] == num) {
                    return false;
                }
            }

            // Check the 3x3 subgrid
            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;
        }

        // Function to solve the Sudoku puzzle using backtracking
        bool solveSudoku(int board[9][9]) {
            int row, col;
            bool emptyCell = false;

            // Search for an empty cell in the grid
            for (row = 0; row < 9; row++) {
                for (col = 0; col < 9; col++) {
                    if (board[row][col] == 0) {
                        emptyCell = true;
                        break;
                    }
                }
                if (emptyCell) break;
            }

            // If there are no empty cells, the puzzle is solved
            if (!emptyCell) return true;

            // Try all possible numbers for the empty cell
            for (int num = 1; num <= 9; num++) {
                if (isSafe(board, row, col, num)) {
                    // If it's safe to place the number, place it
                    board[row][col] = num;

                    // Recursively solve the rest of the board
                    if (solveSudoku(board)) {
                        return true;
                    }

                    // If placing the number doesn't lead to a solution, backtrack
                    board[row][col] = 0;
                }
            }

            // If no number can be placed, return false to trigger backtracking
            return false;
        }

        // Function to print the Sudoku board
        void printBoard(int board[9][9]) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    cout << board[i][j] << " ";
                }
                cout << endl;
            }
        }

        // Main function to test the Sudoku solver
        int main() {
            // Sample Sudoku puzzle (0 represents empty cells)
            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}
            };

            // Solve the Sudoku puzzle
            if (solveSudoku(board)) {
                cout << "Solved Sudoku puzzle: \n";
                printBoard(board);
            } else {
                cout << "No solution exists." << endl;
            }

            return 0;
        }

Program Explanation

The program solves a Sudoku puzzle using a Backtracking algorithm. The structure of the program is as follows:

• isSafe() function: This function checks if a given number can be placed in a specific cell by checking its row, column, and 3×3 subgrid.
• solveSudoku() function: This is the main backtracking function. It searches for empty cells (cells with a value of 0) and tries to fill them with numbers from 1 to 9. If placing a number doesn’t lead to a solution, it backtracks.
• printBoard() function: This function prints the Sudoku board to the console in a readable format.
• main() function: This is where the program starts. It initializes a sample Sudoku board and calls the solveSudoku() function to solve it. If a solution is found, it prints the solved board, otherwise, it indicates that no solution exists.

How to Run the Program

To run the program:

1. Install a C++ compiler like GCC or use an IDE like Code::Blocks or Visual Studio.
2. Copy and paste the above code into a new C++ file (e.g., SudokuSolver.cpp).
3. Compile the program using the C++ compiler.
4. Run the executable to see the solved Sudoku puzzle or a message indicating that no solution exists.