UVA1309 Sudoku

双倍经验：SP1110

题意

填一个 $16\times 16$ 的数独。多组数据。

题解

状压优化搜索+剪枝。

用 $16$ 位二进制数 $\text{ok}[i][j]$ 表示每个点可以填字母的情况。每次搜索之前先尽可能找到不合法，或只有一种填法的情况。

1. 某个点不能填任何字母则回溯；只能填一个字母则直接向下搜索，搜不到直接退出。
2. 某个字母不能填在某一行的任何位置则回溯；只能填在一个位置则向下搜索。
3. 列同理
4. $16$ 宫格同理

然后取能填的字母最少的点进行枚举搜索。

每次搜索前可以把 $\text{ok[]}$ 数组用局部变量 $\text{ok2[]}$ 存下来，最后还原即可。

注意输出格式，两个数据之间有一个空行，但最后不能有空行。

#include<bits/stdc++.h>

using namespace std;

const int N=1<<16;
char s[19][19];
int n,ok[19][19],num[N],cnt1[N],kase;

inline void upd(int x,int y,int z) //更新在 (x,y) 填了 z 后的状态
{
    for (int i=1;i<=16;i++) //更新行和列
    {
        ok[x][i]&=~(1<<z);
        ok[i][y]&=~(1<<z);
    }
    int stx=(x-1)/4*4+1,sty=(y-1)/4*4+1; //16宫格起点
    for (int i=stx;i<stx+4;i++) for (int j=sty;j<sty+4;j++) ok[i][j]&=~(1<<z); //更新16宫格
}

bool dfs(int left)
{
    if (!left)
    {
        for (int i=1;i<=16;i++) printf("%s\n",s[i]+1);
        return 1;
    }
    int ok2[19][19];
    memcpy(ok2,ok,sizeof(ok2));
    int mn=17,nxtx,nxty; //可填字母个数最小值，位置是 (nxtx,nxty)
    for (int i=1;i<=16;i++) //剪枝1，顺便求出当前搜索的点
    {
        for (int j=1;j<=16;j++)
        {
            if (s[i][j]!='-') continue;
            if (!ok[i][j]) return 0;
            if (cnt1[ok[i][j]]==1)
            {
                s[i][j]=num[ok[i][j]]+'A';
                upd(i,j,num[ok[i][j]]);
                if (dfs(left-1)) return 1;
                s[i][j]='-';
                memcpy(ok,ok2,sizeof(ok2));
                return 0;
            }
            if (cnt1[ok[i][j]]<mn)
            {
                mn=cnt1[ok[i][j]];
                nxtx=i; nxty=j;
            }
        }
    }
    for (int i=1;i<=16;i++) //剪枝2，枚举行
    {
        int vis=0,now_left=0;
        for (int j=1;j<=16;j++) //列
        {
            if (s[i][j]=='-') now_left++;
            else vis|=1<<(s[i][j]-'A'); //已填的状态
        }
        if (!now_left) continue; //填满了
        for (int j=0;j<16;j++) //枚举字母
        {
            if (vis>>j&1) continue; //已填
            int cnt=0,last;
            for (int k=1;k<=16;k++) //枚举列
            {
                if (s[i][k]!='-') continue; //不是空格
                if (!(ok[i][k]>>j&1)) continue; //无法填
                cnt++;
                last=k;
                if (cnt>=2) break; //如果 cnt>=2 就显然无法剪枝了，直接退出
            }
            if (!cnt) return 0;
            if (cnt==1)
            {
                s[i][last]=j+'A';
                upd(i,last,j);
                if (dfs(left-1)) return 1;
                s[i][last]='-';
                memcpy(ok,ok2,sizeof(ok2));
                return 0;
            }
        }
    }
    for (int i=1;i<=16;i++) //剪枝3 ，枚举列
    {
        int vis=0,now_left=0;
        for (int j=1;j<=16;j++) //行
        {
            if (s[j][i]=='-') now_left++;
            else vis|=1<<(s[j][i]-'A'); //已填
        }
        if (!now_left) continue; //填满了
        for (int j=0;j<16;j++) //字母
        {
            if (vis>>j&1) continue; //已填
            int cnt=0,last;
            for (int k=1;k<=16;k++) //行
            {
                if (s[k][i]!='-') continue; //不是空格
                if (!(ok[k][i]>>j&1)) continue; //无法填
                cnt++;
                last=k;
                if (cnt>=2) break;
            }
            if (!cnt) return 0;
            if (cnt==1)
            {
                s[last][i]=j+'A';
                upd(last,i,j);
                if (dfs(left-1)) return 1;
                s[last][i]='-';
                memcpy(ok,ok2,sizeof(ok2));
                return 0;
            }
        }
    }
    for (int x=1;x<=13;x+=4) //16宫格，枚举起点 (x,y)
    {
        for (int y=1;y<=13;y+=4)
        {
            int vis=0,now_left=0;
            for (int i=x;i<x+4;i++) //遍历所有点
            {
                for (int j=y;j<y+4;j++)
                {
                    if (s[i][j]=='-') now_left++;
                    else vis|=1<<(s[i][j]-'A'); //已填
                }
            }
            if (!now_left) continue; //填满
            for (int k=0;k<16;k++) //枚举字母
            {
                if (vis>>k&1) continue;
                int cnt=0,lastx,lasty;
                for (int i=x;i<x+4;i++)
                {
                    for (int j=y;j<y+4;j++)
                    {
                        if (s[i][j]!='-') continue;
                        if (!(ok[i][j]>>k&1)) continue;
                        cnt++;
                        lastx=i; lasty=j;
                    }
                }
                if (!cnt) return 0;
                if (cnt==1)
                {
                    s[lastx][lasty]=k+'A';
                    upd(lastx,lasty,k);
                    if (dfs(left-1)) return 1;
                    s[lastx][lasty]='-';
                    memcpy(ok,ok2,sizeof(ok2));
                    return 0;
                }
            }
        }
    }
    for (int i=ok[nxtx][nxty];i;i-=i&-i) //对可填字母最少的点进行枚举搜索
    {
        int z=num[i&-i];
        s[nxtx][nxty]=z+'A';
        upd(nxtx,nxty,z);
        if (dfs(left-1)) return 1;
        s[nxtx][nxty]='-';
        memcpy(ok,ok2,sizeof(ok));
    }
    return 0;
}

signed main()
{
    for (int i=0;i<16;i++) num[1<<i]=i; //整数幂对应关系
    for (int i=0;i<N;i++) for (int j=i;j;j-=j&-j) cnt1[i]++; //二进制数中 1 的个数
    while (~scanf("%s",s[1]+1))
    {
        if (kase) puts(""); //注意输出格式
        kase++;
        for (int i=2;i<=16;i++) scanf("%s",s[i]+1);
        for (int i=1;i<=16;i++) for (int j=1;j<=16;j++) ok[i][j]=N-1;
        int left=0;
        for (int i=1;i<=16;i++)
        {
            for (int j=1;j<=16;j++)
            {
                if (s[i][j]=='-') left++;
                else upd(i,j,s[i][j]-'A'); //更新初始状态
            }
        }
        dfs(left);
    }
    return 0;
}