include

using namespace std;

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

// Check if the number exists in the current column
for (int i = 0; i < 9; i++) {
    if (grid[i][col] == num) {
        return false;
    }
}

// Check if the number exists in the current 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 (grid[i + startRow][j + startCol] == num) {
            return false;
        }
    }
}

return true;

}

// Function to solve the sudoku bool solveSudoku(int grid[9][9]) { int row, col;

// Find the next empty cell
bool isEmpty = false;
for (row = 0; row < 9; row++) {
    for (col = 0; col < 9; col++) {
        if (grid[row][col] == 0) {
            isEmpty = true;
            break;
        }
    }
    if (isEmpty) {
        break;
    }
}

// If there are no empty cells, the sudoku is solved
if (!isEmpty) {
    return true;
}

// Try different numbers in the empty cell
for (int num = 1; num <= 9; num++) {
    if (isSafe(grid, row, col, num)) {
        grid[row][col] = num;

        // Recursively solve the sudoku
        if (solveSudoku(grid)) {
            return true;
        }

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

return false;

}

// Function to print the solved sudoku grid void printGrid(int grid[9][9]) { for (int row = 0; row < 9; row++) { for (int col = 0; col < 9; col++) { cout << grid[row][col] << " "; } cout << endl; } }

// Main function int main() { int grid[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
if (solveSudoku(grid)) {
    // Print the solved grid
    printGrid(grid);
} else {
    cout << "No solution exists." << endl;
}

return 0;

}