#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=