AcWing 166. 数独(搜索)

深度优先搜索

原题链接

优化非常重要，在这题里更是如此

常见的优化技巧（本题前三种都有使用）

• 优化搜索顺序
• 排除冗余信息
• 可行性剪枝
• 最优性剪枝（这里没有）
• 记忆化（就是动态规划了）

本题思路：（剪枝很重要，不然很容易超时）

• 优先搜索的对象与顺序：可选方案最少的位置
• 枚举该位置可选的数字
• dfs搜索
• 关键 ：弄清楚代码编写时二进制与十进制的转换过程

lowbit（截取二进制最低位1对应的值）

 如 lowbit(6)返回2 ：110（6），可得10（2）
代码
int lowbit(int x) {
  return x&(-x);
}

本题的一些小技巧与细节：

• 开始创建两个小数组作为小抄，在后面做一些查找比较的时候会跟快，相当于空间换时间。
• 使用三个判断数组 row,col,cell来判断可选方案（用二进制或是二进制对应的十进制来存）。
• 然后循环当前的9*9，将存在的数在三个判断数组中剔除，并记录"."的个数，即需要搜索的位数数。
• 到dfs里了先找可选方案最少的位置，找到枚举方案，dfs递归，如果1-9都不行则失败，然后回溯（回溯的时候记得恢复现场）。

AC代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 9;
//map用于找二进制1的十进制对应的0-8
//ones用于方便找最优先搜索的位置，里面记录1的个数
int ones[1 << N], map[1 << N]; 
int row[N], col[N], cell[3][3];
char str[100];

// 求可选方案的交集
inline int lowbit(int x)
{
    return x & -x;
}

//初始化，令三个判断数组里全是二进制的1(实际存的是对应十进制的数)，表示原始状态1-9都有
inline void init()
{   //存的是0-8
    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;
}

// 求可选方案的交集
inline 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*9 + j] == '.')
            {
                int t = ones[get(i,j)];
                if(t < minv)
                {
                    minv = t;
                    x = i; y = j;
                }
            }
    
    for(int i = get(x,y); i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        cell[x/3][y/3] -= 1 << t;
        str[x*9 + y] = t + '1';
        
        if(dfs(cnt - 1)) return true;
        
        row[x] += 1 << t;
        col[y] += 1 << t;
        cell[x/3][y/3] += 1 << t;
        str[x*9 + y] = '.';
    }
    
    return false;
    
}

int main()
{
    //两个小抄
    for(int i = 0; i < N; i++) map[1 << i] = i; //二进制中某个1对应的0-8
    for(int i = 0; i < (1 << N); i++)
    {
        int s = 0;
        for(int j = i; j; j -= lowbit(j)) s++;
        ones[i] = s; //当前十进制数对应的二进制数有多少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'; //存的是0-8
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cell[i/3][j/3] -= 1 << t;
                }
                else cnt++;

        dfs(cnt);
        
        cout << str << endl;
    }
    
    return 0;
}