数独 AcWing 166
解决方案介绍:
dfs思考方式:
首先随意选择空格子。然后开始枚举,直到没有空格子。(题目保证有唯一解)
核心思想:
剪枝
优化搜索顺序(每次从可选方案数最少的空格开始搜索)
可行性剪枝 (每次枚举的数字,不能与所在的行所在的列所在方块中的数字有重复)
实现方案
位运算优化:lowbit()算法
用int row[N], col[N], cell[3][3];这几个数组的中的每一个数字代表行,列,块中
** 1~9数字的使用情况例如:000001001(9)代表数字1 和 数字 4 没有使用 **
代码展示:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
int map[M], ones[M];//预处理 map 数组代表每个数字的下标数字 对应的是这个数是第几位数
//例如 下标(8)对应的是第3位(000001000)数字就是代表数独中的数字4 map[8] = 3
//ones 代表每个下标数字中拥有1的个数 例如 下标(8) 中有1个1 ones[8] = 1
int row[N], col[N], cell[3][3];
char str[100];
void init()
{
for (int i = 0; i < 9; i ++) row[i] = col[i] = (1 << N) - 1;
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 3; j ++)
cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool is_set)
{
if (is_set) str[x * N + y] = '1' + t;
else str[x * N + y] = '.';
int v = 1 << t;
if (!is_set) v = -v;
row[x] -= v;
col[y] -=v;
cell[x / 3][y / 3] -= v;
}
int lowbit(int x)
{
return x & -x;
}
int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];//
}
bool dfs(int cnt)
{
if (!cnt) return true;
int minv= 10;
int x, y;
for (int i = 0; i< N; i ++)
for (int j = 0; j < N; j ++)
if (str[i * N + j] == '.')
{
int state = get(i, j);
if (ones[state] < minv)
{
minv = ones[state];
x = i, y = j;
}
}
int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = map[lowbit(i)];
draw(x, y, t, true);
if (dfs(cnt - 1)) return true;
draw(x, y, t, false);
}
return false;
}
int main(void)
{
for (int i = 0; i < N; i ++) map[1 << i] = i;
for (int i = 0; i < 1 << N; i ++)
for (int j = 0; j < N; j ++)
ones[i] += i >> j & 1;
while (cin >> str , str[0] != 'e')
{
init();
int cnt = 0;
for (int i = 0, k = 0;i < N; i ++)
for (int j = 0; j < N; j ++ , k ++)
if (str[k] != '.')
{
int t = str[k] - '1';
draw(i, j, t, true);
}
else
cnt ++;
dfs(cnt);
cout << str<< endl;
}
return 0;
}