莫欺少年穷，修魔之旅在这开始—>算法提高课题解

剪枝与优化

1. 优化搜索顺序
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 记忆化搜索（dp）

思路：

1. 优化搜索顺序：每次选择分支最少的格子
2. 可行性剪枝：每行每列每个九宫格的数字不可重复
3. map1 表示：以 2 为底的对数，例如 map1[16] = 4;
4. ones[i] 表示：每个二进制数字可以存储的 1 的个数
5. 每次找到分支数最少的格子，再找到这个格子可以存放哪些数字
6. 存放数字：draw(x,y,t,true); 最后，不要放了恢复现场

#include<bits/stdc++.h>

using namespace std;

const int N = 9, M = 1 << N;

int map1[M],ones[M];
char str[100];
int row[N],col[N],cell[3][3];

//一开始都是 1，都没放
void init()
{
    for(int i=0;i<N;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]=t+'1';

    //不放数字
    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;
}

//求解二进制的最后一位 1 的位置
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,x,y;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(str[i*N+j]=='.'&&ones[get(i,j)]<minv)
            {
                minv=ones[get(i,j)];
                x=i,y=j;
            }

    //查看该格子可以放哪些数字
    int state=get(x,y);
    for(int i=state;i;i-=lowbit(i))
    {
        //可以存放的数字
        int t=map1[lowbit(i)];

        //放该数字
        draw(x,y,t,true);
        if(dfs(cnt-1)) return true;

        //不放该数字
        draw(x,y,t,false);
    }

    return false;
}

int main()
{
    //例如，map1[2 ^ 8] = 8;
    for(int i=0;i<N;i++) map1[1<<i]=i;

    //求解每个二进制数字都有多少个 1
    for(int i=0;i<M;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;i<N;i++)
            for(int j=0;j<N;j++)
                if(str[i*N+j]!='.') draw(i,j,str[i*N+j]-'1',true);
                else cnt++;

        dfs(cnt);

        cout<<str<<endl;
    }

    return 0;
}