正确版本
int DFS(int x, int y)
{
if(x == 9)
return 1;
if(y == 9)
return DFS(x + 1, 0);
if(Map[x][y] != '0')
return DFS(x, y + 1);
for(int i = 0; i < 9; i++)
{
if(! RowUsed[x][i] && ! ColUsed[y][i] && ! BlockUsed[x / 3 * 3 + y / 3][i])
{
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 1;
Map[x][y] = i + '1';
if(DFS(x, y + 1))
return 1;
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 0;
Map[x][y] = '0';
}
}
return 0;
}
错误版本
void DFS(int x, int y) {
if(x == 9)
return ;
if(y == 9)
DFS(x + 1, 0);
if(Map[x][y] != '0')
DFS(x, y + 1);
for(int i = 0; i < 9; i++) {
if(!RowUsed[x][i] && !ColUsed[y][i] && !BlockUsed[x / 3 * 3 + y / 3][i]) {
Map[x][y] = i + '1';
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 1;
DFS(x, y + 1);
Map[x][y] = 0;
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 0;
}
}
}
完整正确程序
#include
#include
const int MAXN = 9;
char Map[MAXN + 1][MAXN + 1];
int RowUsed[MAXN][MAXN], ColUsed[MAXN][MAXN], BlockUsed[MAXN][MAXN];
int DFS(int x, int y)
{
if(x == 9)
return 1;
if(y == 9)
return DFS(x + 1, 0);
if(Map[x][y] != '0')
return DFS(x, y + 1);
for(int i = 0; i < 9; i++)
{
if(! RowUsed[x][i] && ! ColUsed[y][i] && ! BlockUsed[x / 3 * 3 + y / 3][i])
{
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 1;
Map[x][y] = i + '1';
if(DFS(x, y + 1))
return 1;
RowUsed[x][i] = ColUsed[y][i] = BlockUsed[x / 3 * 3 + y / 3][i] = 0;
Map[x][y] = '0';
}
}
return 0;
}
int main() {
int Cases;
scanf("%d", &Cases);
while(Cases--) {
memset(RowUsed, 0, sizeof(RowUsed));
memset(ColUsed, 0, sizeof(ColUsed));
memset(BlockUsed, 0, sizeof(BlockUsed));
for(int i = 0; i < 9; i++)
scanf("%s", Map[i]);
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(Map[i][j] != '0') {
RowUsed[i][Map[i][j] - '1'] = ColUsed[j][Map[i][j] - '1'] = BlockUsed[i / 3 * 3 + j / 3][Map[i][j] - '1'] = 1;
}
}
}
DFS(0, 0);
for(int i = 0; i < 9; i++)
printf("%s\n", Map[i]);
}
return 0;
