洛谷P1074 靶形数独
url: https://www.luogu.com.cn/problem/P1074
tag:
NOIP2009 提高组，搜索，剪枝，位运算，NOIP提高组，2009
思路：
- 核心变量解析
a[10][10]：存储数独棋盘，ai表示第i行第j格的数字（0表示空格）r[10]：行约束，r[i]的二进制第k位表示第i行能否填数字k+1（1表示可用）c[10]：列约束，c[j]的二进制第k位表示第j列能否填数字k+1e[5][5]：九宫格约束，ex的二进制第k位表示第x行第y列九宫格能否填k+1p[1<<11]：位掩码到数字的映射，p[1<<k]=k+1（快速获取候选数字）o[1<<10]：预计算二进制中1的个数，o[mask]表示mask的候选数字个数ans：存储最终的最大得分
- 关键函数解析
gs()：根据位置计算得分，边缘得分低，中心得分高（计算公式：值*(6+距边缘距离)）init()：初始化约束为全可用状态，预处理o[]和p[]的映射关系dfs()：采用最小候选数优先的回溯算法，通过位运算快速枚举候选值
- 算法流程
- 预处理所有约束条件
- 优先选择候选数最少的格子进行填充（剪枝优化）
- 用位运算快速遍历所有候选数字
- 递归搜索时动态更新约束条件
- 达到填满状态时更新最大得分
- 位运算优化点
- 用异或操作快速增删约束条件（r[i]^=mask）
- 用lowbit技巧遍历候选数字（t&-t获取最低位的1）
- 预计算o[]避免重复计算候选数个数
参考： https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路，爱了爱了。
代码：
#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
for (int i = 0; i < (1 << 9); i ++)
{
int t = i;
while (t)
{
t &= t -1;
o[i] ++;
}
}
for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
if (cnt == 0)
{
ans = max(ans, sum);
}
int mi = 10, x, y;
for (int i = 0; i< 9; i++)
for (int j = 0; j < 9; j ++)
{
if (!a[i][j])
{
int t = r[i] & c[j] & e[i / 3][j / 3];
if (o[t] < mi)
{
mi = o[t], x = i, y = j;
}
}
}
int t = r[x] & c[y] & e[x / 3][y / 3];
while (t)
{
int l = (t & -t);
t -= l;
a[x][y] = p[l];
r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
dfs(cnt -1, sum + gs(x, y));
a[x][y] = 0;
r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
}
}
int main()
{
init();
int cnt = 0, sum = 0;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j ++)
{
cin >> a[i][j];
if (a[i][j])
{
r[i] -= 1 << a[i][j] - 1;
c[j] -= 1 << a[i][j] - 1;
e[i / 3][j / 3] -= 1 << a[i][j] -1;
sum += gs(i, j);
}else cnt ++;
}
dfs(cnt, sum);
cout << ans << endl;
return 0;
}