include <bits/stdc++.h>
define ll long long
using namespace std;
bool canPlace(int matrix[][9], int i, int j, int n, int number)
{
for (int x = 0; x < n; x++)
{
//Row and Column check
if (matrix[x][j] == number || matrix[i][x] == number)
{
return false;
}
}
int rn = sqrt(n);
int sx = (i / rn) * rn; //grid start row
int sy = (j / rn) * rn; //grid start column
for (int x = sx; x <= sx + rn; x++)
{
for (int y = sy; y <= sy + rn; y++)
{
if (matrix[x][y] == number)
{
return false;
}
}
}
//safe to place
return true;
}
bool solveSudoku(int matrix[][9], int i, int j, int n)
{
//Base case
if (i == n)
{
//solution exist print matrix
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
cout << matrix[j][k] << " ";
}
cout << endl;
}
return true;
}
//case row end
if (j == n)
{
return solveSudoku(matrix, i + 1, 0, n);
}
//skip the pre filled cells
if (matrix[i][j] != 0)
{
return solveSudoku(matrix, i, j + 1, n);
}
//recursive case
//fill the current case with possible options
for (int number = 1; number <= n; number++)
{
if (canPlace(matrix, i, j, n, number) == true)
{
//Assume
matrix[i][j] = number;
bool couldWeSolve = solveSudoku(matrix, i, j + 1, n);
if (couldWeSolve == true)
{
return true;
}
}
}
//Backtrack here
matrix[i][j] = 0;
return false;
}
int main()
{
int n;
cin >> n;
int matrix[9][9] = {};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> matrix[i][j];
}
}
cout << endl;
solveSudoku(matrix, 0, 0, n);
return 0;
}