Сегодня на контесте писал как раз эту задачу. Работает мгновенно (меньше 10 мс), но при условии, что решение есть. Если решения нет, то может работать порядка полусекунды. Вот код:
| Код | int a[9][9]; // входные данные; a[i][j] = 0 если клетка пустая; на выходе здесь будет ответ
int freex[9], freey[9], freeb[9];
int sumx[9], sumy[9], sumb[9];
bool usedx[9][10], usedy[9][10], usedb[9][10];
int bl (int x, int y) {
return x / 3 * 3 + y / 3;
}
bool brute (int x = 0) {
while (x<9 && freex[x]==0) ++x;
if (x==9)
return true;
for (int y=0; y<9; ++y)
if (a[x][y] == 0) {
int b = bl(x,y);
if (freex[x] == 1)
a[x][y] = 45 - sumx[x];
else if (freey[y] == 1)
a[x][y] = 45 - sumy[y];
else if (freeb[b] == 1)
a[x][y] = 45 - sumb[b];
else {
--freex[x], --freey[y], --freeb[b];
for (a[x][y]=1; a[x][y]<=9; ++a[x][y])
if (!usedx[x][a[x][y]] && !usedy[y][a[x][y]] && !usedb[b][a[x][y]]) {
usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = true;
sumx[x]+=a[x][y], sumy[y]+=a[x][y], sumb[b]+=a[x][y];
if (brute (x))
return true;
usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = false;
sumx[x]-=a[x][y], sumy[y]-=a[x][y], sumb[b]-=a[x][y];
}
a[x][y] = 0;
++freex[x], ++freey[y], ++freeb[b];
return false;
}
if (usedx[x][a[x][y]] || usedy[y][a[x][y]] || usedb[b][a[x][y]]) {
a[x][y] = 0;
return false;
}
--freex[x], --freey[y], --freeb[b];
usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = true;
sumx[x]+=a[x][y], sumy[y]+=a[x][y], sumb[b]+=a[x][y];
if (brute (x))
return true;
usedx[x][a[x][y]] = usedy[y][a[x][y]] = usedb[b][a[x][y]] = false;
sumx[x]-=a[x][y], sumy[y]-=a[x][y], sumb[b]-=a[x][y];
a[x][y] = 0;
++freex[x], ++freey[y], ++freeb[b];
return false;
}
return (bool) 314159265; // never get there :)
}
int main() {
freopen ("input.txt", "rt", stdin);
freopen ("output.txt", "wt", stdout);
char s[11];
for (int i=0; i<9; ++i) {
gets (s);
for (int j=0; j<9; ++j)
a[i][j] = s[j]-'0';
}
for (int i=0; i<9; ++i)
for (int j=0; j<9; ++j)
if (a[i][j] == 0)
++freex[i], ++freey[j], ++freeb[bl(i,j)];
else {
sumx[i]+=a[i][j], sumy[j]+=a[i][j], sumb[bl(i,j)]+=a[i][j];
usedx[i][a[i][j]] = usedy[j][a[i][j]] = usedb[bl(i,j)][a[i][j]] = true;
}
if (!brute())
puts ("NO SOLUTION");
else
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j)
cout << a[i][j];
cout << endl;
}
} |
|
)