#include <iostream>
#include <vector>
using namespace std;
 
#define N 9
 
bool isSafe(int grid[N][N], int row, int col, int num) {
    for (int i = 0; i < N; i++) {
        if (grid[row][i] == num || grid[i][col] == num)
            return false;
    }
 
    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;
}
 
bool findEmptyLocation(int grid[N][N], int &row, int &col) {
    for (row = 0; row < N; row++) {
        for (col = 0; col < N; col++) {
            if (grid[row][col] == 0) 
                return true;
        }
    }
    return false; 
}
 
bool solveSudoku(int grid[N][N]) {
    int row, col;
 
    // If there is no empty cell, puzzle is solved
    if (!findEmptyLocation(grid, row, col))
        return true;
 
    for (int num = 1; num <= 9; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;
 
            if (solveSudoku(grid))
                return true;
 
            grid[row][col] = 0;
        }
    }
 
    return false;
}
 
void printGrid(int grid[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++)
            cout << grid[row][col] << " ";
        cout << endl;
    }
}
 
int main() {
    int grid[N][N];
 
    cout << "Enter the initial Sudoku puzzle (use 0 for empty cells):\n";
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            cin >> grid[row][col];
        }
    }
 
    if (solveSudoku(grid))
        printGrid(grid);
    else
        cout << "No solution exists" << endl;
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBOIDkKCmJvb2wgaXNTYWZlKGludCBncmlkW05dW05dLCBpbnQgcm93LCBpbnQgY29sLCBpbnQgbnVtKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgIGlmIChncmlkW3Jvd11baV0gPT0gbnVtIHx8IGdyaWRbaV1bY29sXSA9PSBudW0pCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KCiAgICBpbnQgc3RhcnRSb3cgPSByb3cgLSByb3cgJSAzOwogICAgaW50IHN0YXJ0Q29sID0gY29sIC0gY29sICUgMzsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMzsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCAzOyBqKyspIHsKICAgICAgICAgICAgaWYgKGdyaWRbaSArIHN0YXJ0Um93XVtqICsgc3RhcnRDb2xdID09IG51bSkKICAgICAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIHRydWU7Cn0KCmJvb2wgZmluZEVtcHR5TG9jYXRpb24oaW50IGdyaWRbTl1bTl0sIGludCAmcm93LCBpbnQgJmNvbCkgewogICAgZm9yIChyb3cgPSAwOyByb3cgPCBOOyByb3crKykgewogICAgICAgIGZvciAoY29sID0gMDsgY29sIDwgTjsgY29sKyspIHsKICAgICAgICAgICAgaWYgKGdyaWRbcm93XVtjb2xdID09IDApIAogICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGZhbHNlOyAKfQoKYm9vbCBzb2x2ZVN1ZG9rdShpbnQgZ3JpZFtOXVtOXSkgewogICAgaW50IHJvdywgY29sOwoKICAgIC8vIElmIHRoZXJlIGlzIG5vIGVtcHR5IGNlbGwsIHB1enpsZSBpcyBzb2x2ZWQKICAgIGlmICghZmluZEVtcHR5TG9jYXRpb24oZ3JpZCwgcm93LCBjb2wpKQogICAgICAgIHJldHVybiB0cnVlOwoKICAgIGZvciAoaW50IG51bSA9IDE7IG51bSA8PSA5OyBudW0rKykgewogICAgICAgIGlmIChpc1NhZmUoZ3JpZCwgcm93LCBjb2wsIG51bSkpIHsKICAgICAgICAgICAgZ3JpZFtyb3ddW2NvbF0gPSBudW07CgogICAgICAgICAgICBpZiAoc29sdmVTdWRva3UoZ3JpZCkpCiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKCiAgICAgICAgICAgIGdyaWRbcm93XVtjb2xdID0gMDsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIGZhbHNlOwp9Cgp2b2lkIHByaW50R3JpZChpbnQgZ3JpZFtOXVtOXSkgewogICAgZm9yIChpbnQgcm93ID0gMDsgcm93IDwgTjsgcm93KyspIHsKICAgICAgICBmb3IgKGludCBjb2wgPSAwOyBjb2wgPCBOOyBjb2wrKykKICAgICAgICAgICAgY291dCA8PCBncmlkW3Jvd11bY29sXSA8PCAiICI7CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGludCBncmlkW05dW05dOwogICAgCiAgICBjb3V0IDw8ICJFbnRlciB0aGUgaW5pdGlhbCBTdWRva3UgcHV6emxlICh1c2UgMCBmb3IgZW1wdHkgY2VsbHMpOlxuIjsKICAgIGZvciAoaW50IHJvdyA9IDA7IHJvdyA8IE47IHJvdysrKSB7CiAgICAgICAgZm9yIChpbnQgY29sID0gMDsgY29sIDwgTjsgY29sKyspIHsKICAgICAgICAgICAgY2luID4+IGdyaWRbcm93XVtjb2xdOwogICAgICAgIH0KICAgIH0KCiAgICBpZiAoc29sdmVTdWRva3UoZ3JpZCkpCiAgICAgICAgcHJpbnRHcmlkKGdyaWQpOwogICAgZWxzZQogICAgICAgIGNvdXQgPDwgIk5vIHNvbHV0aW9uIGV4aXN0cyIgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQo=