数独

题目

166. 数独 - AcWing题库 数独 是一种传统益智游戏，你需要把一个 $9\times 9$ 的数独补充完整，使得数独中每行、每列、每个 $3\times 3$ 的九宫格内数字 $1\sim 9$ 均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 $81$ 个字符，代表数独的 $81$ 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字$（1-9）$或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

思路

对于一个数独问题： 求一种填数方案, 使得结果满足：

• 每行1~9只出现一次
• 每列1~9只出现一次
• 每个格子1~9只出现一次 当枚举其中任意一个空位时, 我们需要知道当前能填哪些数, 即需要记录此时行状态, 列状态, 格子状态。他们都是有9种选择, 故可以用9位二进制数, 表示当前行, 列, 格子内可以选那那些数。 比如 col[i], i=000001010, 则可以选2, 4两个数。 这样求三个条件的并集也很方便, 二进制与就可以。 可以先求出所有二进制对应的1的个数ones[N], 和 将lowbit运算返回的1转换为个位数对应的map[N]。

题目给的是一行输入, 也就是二维数组的一维形式, 即g[i][j]的一维形式为g[i*m+j] m为行长度。 搜索顺序为： 先随意选择一个空格子, 再枚举填某个数得到一个新的棋盘, 然后再进行之前的操作直到填满。

优化方法： 在选空格子时, 应该选择分支较少的, 也就是能选的数比较少的 怎么快速求出当前分支较少的空格子呢？没发, 直接暴力搜吧。

代码

const int N = 82, M = 9;
char g[N];
int row[M], col[M], cell[M][M];
int ones[1 << M], map[1 << M];
int cnt;
 
void draw(int x, int y, int t, bool isset)
{
    if (isset)
        g[x * 9 + y] = char(t + '1');
    else
        g[x * 9 + y] = '.';
 
    int v = 1 << t;
    if (isset)
        v = -v;
    row[x] += v;
    col[y] += v;
    cell[x / 3][y / 3] += v;
}
 
int lowbit(int x)
{
    return x & -x;
}
 
int get(int x, int y) // x,y位置上能填那些数
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}
 
bool dfs(int cnt)
{
    if (!cnt)
        return true;
    int x, y, minv = 10;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (g[i * 9 + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int v = map[lowbit(i)]; // 数
        draw(x, y, v, true);
        if (dfs(cnt - 1))
            return true;
        draw(x, y, v, false);
    }
    return false;
}
 
int main()
{
    for (int i = 0; i < 9; i++)
        map[1 << i] = i;
    for (int i = 0; i < 1 << 9; i++)
        for (int j = 0; j < 9; j++)
            ones[i] += i >> j & 1;
    while (cin >> g)
    {
        if (g[0] == 'e')
            break;
        // 初始化什么都能选
        for (int i = 0; i < 9; i++)
            row[i] = col[i] = (1 << M) - 1;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                cell[i][j] = (1 << M) - 1;
        cnt = 0;
        for (int i = 0, k = 0; i < 9; i++)
            for (int j = 0; j < 9; j++, k++)
            {
                char c = g[k];
                if (c != '.')
                    draw(i, j, c - '1', true);
                else
                    cnt++;
            }
 
        dfs(cnt);
        cout << g << endl;
    }
    return 0;
}