1. 

/*

* ACM Programming Contest

* Problem: 989 - Su Doku

* Status: Accepted

* Language: C

* Runtime: 0.020

* Date: 2009-05-10 12:06:46

* Author: Axel Fiedler

*/
#include <stdio.h>

#define MAX_SIZE 9
#define TRUE 1
#define FALSE 0

#define boxStart(x, n) (((int)((double)x/(double)n)*n))

int field[MAX_SIZE][MAX_SIZE];
int n;
int nQuad;

int check(int x, int y, int number)
{
int i, j;

/* Horizontal */
for (i = 0; i < nQuad; i++)
if (field[i][y] == number)
return TRUE;

/* Vertical */
for (i = 0; i < nQuad; i++)
if (field[x][i] == number)
return TRUE;

/* Box n*n */
for (i = boxStart(x, n); i < boxStart(x, n) + n; i++)
for (j = boxStart(y, n); j < boxStart(y, n) + n; j++)
if (field[i][j] == number)
return TRUE;

return FALSE;
}

int solveBacktrack(int x, int y)
{
int i;

if (y >= nQuad)
{
x++;

if (x >= nQuad)
return TRUE;

y = 0;
}

if (field[x][y])
return solveBacktrack(x, y + 1);

for (i = 1; i < nQuad + 1; i++)
{
if (!check(x, y, i))
{
field[x][y] = i;

if (solveBacktrack(x, y + 1))
return TRUE;
}
}

field[x][y] = 0;

return FALSE;
}

int main()
{
int x, y;

while (scanf("%d", &n) > 0)
{
nQuad = n*n;

for (x = 0; x < nQuad; x++)
for (y = 0; y < nQuad; y++)
scanf("%d", &field[x][y]);

if (solveBacktrack(0, 0))
{
for (x = 0; x < nQuad; x++)
{
for (y = 0; y < nQuad; y++)
{
if (y < (nQuad - 1))
printf("%d ", field[x][y]);
else
printf("%d\n", field[x][y]);
}
}

printf("\n");
}
else
printf("NO SOLUTION\n");
}

return 0;
}

2.

/*
* ACM Programming Contest
*
* Problem: 989 - Su Doku
* Status: Accepted
* Language: C
* Runtime: 0.012
* Date: 2009-05-18 15:39:07
* Author: Axel Fiedler
*
*/
#include <stdio.h>

#define MAX_SIZE 9
#define TRUE 1
#define FALSE 0

#define boxStart(x, n) (((int)((double)x/(double)n)*n))

int field[MAX_SIZE][MAX_SIZE];
int n;
int nQuad;

int check(int x, int y, int number)
{
int i, j;

/* Horizontal */
for (i = 0; i < nQuad; i++)
if (field[i][y] == number)
return TRUE;

/* Vertical */
for (i = 0; i < nQuad; i++)
if (field[x][i] == number)
return TRUE;

/* Box n*n */
for (i = boxStart(x, n); i < boxStart(x, n) + n; i++)
for (j = boxStart(y, n); j < boxStart(y, n) + n; j++)
if (field[i][j] == number)
return TRUE;

return FALSE;
}

int countPlaces(int x, int y)
{
int i, j, max;
int list[10] = {FALSE};

for(i = 0; i < nQuad; i++)
{
if(field[x][i] > 0)
list[field[x][i]] = TRUE;

if(field[i][y] > 0)
list[field[i][y]] = TRUE;
}

for(i = boxStart(x, n); i < boxStart(x, n) + n; i++)
{
if(i != x)
{
for(j = boxStart(y, n); j < boxStart(y, n) + n; j++)
{
if((field[i][j] > 0) && (j != y))
list[field[i][j]] = TRUE;
}
}
}

max = 0;

for(i = 1; i <= nQuad; i++)
if(!list[i])
max++;

return max;
}

void bestPlace(int* x, int* y)
{
int i, j, count, minCount;

minCount = nQuad;

for(i = 0; i < nQuad; i++)
{
for(j = 0; j < nQuad; j++)
{
if(field[i][j] == 0)
{
count = countPlaces(i, j);

if(count <= minCount)
{
minCount = count;
*x = i;
*y = j;
}
}
}
}
}

int solveBacktrack()
{
int i, x, y;

x = y = -1;
bestPlace(&x, &y);

if((x < 0) && (y < 0))
return TRUE;

for(i = 1; i < nQuad + 1; i++)
{
if(!check(x, y, i))
{
field[x][y] = i;

if(solveBacktrack())
return TRUE;
}
}

field[x][y] = 0;

return FALSE;
}

int main()
{
int x, y;

while (scanf("%d", &n) > 0)
{
nQuad = n*n;

for (x = 0; x < nQuad; x++)
for (y = 0; y < nQuad; y++)
scanf("%d", &field[x][y]);

if (solveBacktrack())
{
for (x = 0; x < nQuad; x++)
{
for (y = 0; y < nQuad; y++)
{
if (y < (nQuad - 1))
printf("%d ", field[x][y]);
else
printf("%d\n", field[x][y]);
}
}

printf("\n");
}
else
printf("NO SOLUTION\n");
}

return 0;
}