AcWing 1613. 数独简单版
原题链接
简单
作者:
wjie
,
2021-02-01 22:58:00
,
所有人可见
,
阅读 402
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1 << 9;
char arr[10][10];
int row[10], col[10], cell[3][3], one_number[N];
int init()
{
for (int i = 0; i < N; ++i)
{
int t = i;
while (t) one_number[i]++, t -= t & (-t);
}
int target = 0;
for (int i = 0; i < 9; ++i)
{
for (int j = 0; j < 9; ++j)
{
if (arr[i][j] == '.')
{
target++;
continue;
}
int t = arr[i][j] - '1';
row[i] |= (1 << t);
col[j] |= (1 << t);
cell[i/3][j/3] |= (1 << t);
}
}
return target;
}
bool dfs(int target)
{
if (!target) return true;
int x, y, k = -1;
for (int i = 0; i < 9; ++i)
{
for (int j = 0; j < 9; ++j)
{
if (arr[i][j] == '.')
{
int t = one_number[row[i]|col[j]|cell[i/3][j/3]];
if (t > k) x = i, y = j, k = t;
}
}
}
int cir = row[x]|col[y]|cell[x/3][y/3];
for (int i = 0; i < 9; ++i)
{
if (!((cir>>i)&1))
{
row[x] |= (1 << i), col[y] |= (1 << i), cell[x/3][y/3] |= (1 << i);
arr[x][y] = i + '1';
if (dfs(target-1)) return true;
row[x] -= (1 << i), col[y] -= (1 << i), cell[x/3][y/3] -= (1 << i);
arr[x][y] = '.';
}
}
return false;
}
int main()
{
for (int i = 0; i < 9; ++i)
scanf("%s", arr[i]);
int target = init();
dfs(target);
for (int i = 0; i < 9; ++i)
printf("%s\n", arr[i]);
return 0;
}