1. C++, Evgeni Pavlidis

#include <iostream>
#include <string>

using namespace std;

int m[9][9];
int n,dim;


bool check(int r, int c, int num)
{
// check block
int baseC = c/n * n;
int baseR = r/n * n;
for(int dr = 0; dr < n; dr++)
for(int dc = 0; dc < n; dc++)
if(m[baseR + dr][baseC + dc] == num)
return false;


// check horizontaly
for(int i = 0; i < dim; i++)
if(m[i][c] == num)
return false;

// check vertically
for(int i = 0; i < dim; i++)
if(m[r][i] == num)
return false;

return true;
}

void printSolution()
{
for(int r=0; r < dim; r++)
{
for(int c=0; c < dim; c++)
{
cout << m[r][c];
if(c < dim-1)
cout << " ";
}
cout << endl;
}
}

bool solve()
{
for(int r=0; r < dim; r++)
for(int c=0; c < dim; c++)
if(m[r][c] == 0)
{
for(int n=1; n <= dim; n++)
if(check(r,c,n))
{
m[r][c] = n;
if(solve())
return true;
m[r][c] = 0;
}
return false;
}

printSolution();
return true;
}

bool isCorrupt()
{
// do we need that?
return false;
}

int main()
{
bool first = true;

while(true)
{
cin >> n;
dim = n*n;


// read matrix
for(int r=0; r < dim; r++)
for(int c=0; c < dim; c++)
cin >> m[r][c];

if(feof(stdin))
return 0;
else
if(!first)
cout << endl;

first = false;

if(isCorrupt() || !solve())
cout << "NO SOLUTION" << endl;

}

}