[C++]填数独[9x9]

数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得图中每行、每列、每个 3×3 的九宫格内数字 1∼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用二进制位表示。一个坐标对应的行、列、块、三个做按位与运算，得到可用数字。每次从可用数字最少的位置深搜，用cnt记录未填方块个数，并作为dfs参数，为零时返回。
如何得到二进制中有多少个1？请参考这篇博文.

参数列表

const int N = 9;//数据二维范围
const int M = 1 << N;//数据线性范围
int numlist[M];//得到数字二进制形式下1的个数
int loglist[M];//将lowbit得到的二进制数转成有效位
int row[N], col[N], block[3][3];//表示行列块可用的bit组
char str[100];

函数列表

void init()//初始化“位图”为1，表示未用过
{
    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 ++ )
            block[i][j] = (1 << N) - 1;
}
/*
 * （ x , y ）: 坐标
 *  t : 要填写的数，范围1-9
 *  is_set: 
 *      true 为填数
 *      false 为恢复未填
 */
void setnum(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';
    int v = 1 << t;
    if (!is_set) v = -v;//根据bool，进行添数或恢复
    row[x] -= v;
    col[y] -= v;
    block[x / 3][y / 3] -= v;
}

int lowbit(int x) //得到只包含最低位1的二进制数
{
    return x & -x;
}
int useable(int x, int y)//行列块取交集，得到可用数的二进制表示
{
    return row[x] & col[y] & block[x / 3][y / 3];
}

bool dfs(int cnt)//cnt为未填方块个数
{
    if (!cnt) return true;
    //找到可选方案数最小的横纵坐标
    int choice = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.')
            {
                int state = useable(i, j);
                if (numlist[state] < choice)
                {
                    choice = numlist[state];
                    x = i, y = j;
                }
            }
    int state = useable(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = loglist[lowbit(i)];
        setnum(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        setnum(x, y, t, false);
    }
    return false;
}

int main()
{
    for (int i = 0; i < N; i ++ ) loglist[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            numlist[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e')
    {
        init();
        int cnt = 0;//记录未填数
        for (int i = 0, k = 0; i < N; i ++ )//k为原数据坐标
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    setnum(i, j, t, true);
                }
                else cnt ++ ;
        dfs(cnt);
        puts(str);
    }
    return 0;
}

本题来自acwing