洛谷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+1
e[5][5]：九宫格约束，ex的二进制第k位表示第x行第y列九宫格能否填k+1
p[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;
}