In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.
Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input
The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output
For each test case, print a line representing the completed Sudoku puzzle.

Sample Input
.2738…1…1…6735…293.5692.8…6.1745.364…9518…7…8…6534.
…52…8.4…3…9…5.1…6…2…7…3…6…1…7.4…3.
end
Sample Output
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936

转载自:https://blog.csdn.net/WhereIsHeroFrom/article/details/79220897
对于一个N阶的数独,由N2个格子组成,如图为一个3阶的数独。要求满足四个限制条件:

  1. 每个格子只能填1个数;
  2. 每行的数字集合为[1, N^2],且不能重复;
  3. 每列的数字集合为[1, N^2],且不能重复;
  4. 每个“宫”的数字集合为[1, N^2],且不能重复(其中“宫”的意思就是N×N的格子。对于N=3的情况,就是“九宫格”);
    现在问题是给定一个已经填了一些数字的数独,求当N=3时的一种解,满足以上四个限制条件。
    Dancing Links ---- D - Sudoku-LMLPHP

转变为精确覆盖问题。行代表问题的所有情况,列代表问题的约束条件。每个格子能够填的数字为[1,9],并且总共有9×9(即32)个格子,所以总的情况数为729种。也就是DancingLinks的行为729行。
列则分为四种:

  1. [0, 81)列 分别对应了81个格子是否被放置了数字。
  2. [82, 2*81)列 分别对应了9行,每行[1, 9]个数字的放置情况;
  3. [281, 381)列 分别对应了9列,每列[1, 9]个数字的放置情况;
  4. [381, 481)列 分别对应了9个“宫”,每“宫”[1, 9]个数字的放置情况;
    所以总的列数为4*81=324列。如图五-4-2所示。
    Dancing Links ---- D - Sudoku-LMLPHP
    举个例子,对于在数独棋盘的i行j列的格子(i, j)上放置一个数字k,那么对应的Dancing Links的01矩阵行,一行上有四个“1”,分别对应四种约束条件:
    1. 格子限制: 行号*9 + 列号
    2. 行不重复限制: 81 + 行号 *9 + (k-1)
    3. 列不重复限制: 2*81 + 列号 *9 + (k-1)
    4. “宫”不重复限制:3*81 + 宫号 *9 + (k-1)
      行号是i,列号是j,比较好理解;那么宫号我们定义如下图:
      Dancing Links ---- D - Sudoku-LMLPHP

宫号的计算方式可以通过行号和列号得出。即 宫号 = (i/3)*3 + (j/3);
那么构建01矩阵的时候,我们从上到下,从左到右遍历数独,对于在(i, j)上有数字k的只需要插入一行,这行上有四列为“1”。对于没有填写数字的需要枚举[1, 9],把在(i, j)位置上填[1, 9]的情况都进行插入,一共9行。
矩阵构建完毕,求一次精确覆盖即可。

上面的解释已经非常清晰了。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const double eps = 1e-8;
const double PI = acos(-1);

//最大行数
const int MN = 1005;
//最大列数
const int MM = 1005;
//最大点数
const int MNN = 1e5 + 5 + MM;

struct DLX
{
    //一共n行m列,s个节点
    int n,m,s;
    //交叉十字链表组成部分
    //第i个节点的上U下D左L右R,所在位置row行col列
    int U[MNN],D[MNN],L[MNN],R[MNN],row[MNN],col[MNN];
    //H数组记录行选择指针,S数组记录覆盖个数
    int H[MN],S[MM];
    //res记录行个数,ans数组记录可行解
    int res,ans[MN];
    //初始化空表
    void init(int x,int y)
    {
        n = x,m = y;
        //其中0节点作为head节点,其他作为列首节点
        for(int i = 0;i <= m;++i){
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        R[m] = 0;L[0] = m;
        s = m;
        memset(S,0,sizeof(S));
        memset(H,-1,sizeof(H));
    }
    void Insert(int r,int c)
    {
        //节点数加一,设置s节点所处位置,以及S列覆盖个数加一
        s++;row[s] = r;col[s] = c;S[c]++;
        //将s节点插入对应列中
        D[s] = D[c];U[D[c]] = s;
        U[s] = c;D[c] = s;
        if(H[r] < 0){//如果该行没有元素,H[r]标记该行起始节点
            H[r] = L[s] = R[s] = s;
        }else{
            //将该节点插入该行第一个节点后面
            R[s] = R[H[r]];
            L[R[H[r]]] = s;
            L[s] = H[r];
            R[H[r]] = s;
        }
    }
    //精确覆盖
    void Remove(int c)
    {
        //删除c列
        L[R[c]] = L[c];R[L[c]] = R[c];
        //删除该列上的元素对应的行
        for(int i = D[c];i != c;i = D[i]){//枚举该列元素
            for(int j = R[i];j != i;j = R[j]){//枚举列的某个元素所在行遍历
                U[D[j]] = U[j];
                D[U[j]] = D[j];
                //将该列上的S数组减一
                --S[col[j]];
            }
        }
    }
    void resume(int c)
    {
        //恢复c列
        for(int i = U[c];i != c;i = U[i]){//枚举该列元素
            for(int j = L[i];j != i;j = L[j]){
                U[D[j]] = j;D[U[j]] = j;
                ++S[col[j]];
            }
        }
        L[R[c]] = c;R[L[c]] = c;
    }
    bool dance(int deep)
    {
        if(res < deep) return false;
        //当矩阵为空时,说明找到一个可行解,算法终止
        if(R[0] == 0){
            res = deep;
            return true;
        }
        //找到节点数最少的列,枚举这列上的所有行
        int c = R[0];
        for(int i = R[0];i != 0;i = R[i]){
            if(S[i] < S[c]){
                c = i;
            }
        }
        //删除节点数最少的列
        Remove(c);
        for(int i = D[c];i != c;i = D[i]){
            //将行r放入当前解
            ans[deep] = row[i];
            //行上节点对应的列上进行删除
            for(int j = R[i];j != i;j = R[j])
                Remove(col[j]);
            //进入下一层
            if(dance(deep + 1)) return true;
            //对行上的节点对应的列进行恢复
            for(int j = L[i];j != i;j = L[j])
                resume(col[j]);
        }
        //恢复节点数最少列
        resume(c);
        return false;
    }

    //重复覆盖
    //将列与矩阵完全分开
    void Remove1(int c)
    {
        for(int i = D[c];i != c;i = D[i]){
            L[R[i]] = L[i];
            R[L[i]] = R[i];
        }
    }
    void resume1(int c)
    {
        for(int i = D[c];i != c;i = D[i]){
            L[R[i]] = R[L[i]] = i;
        }
    }
    int vis[MNN];
    //估价函数,模拟删除列,H(),函数返回的是至少还需要多少行才能完成重复覆盖
    int A()
    {
        int dis = 0;
        for(int i = R[0];i != 0;i = R[i]) vis[i] = 0;
        for(int i = R[0];i != 0;i = R[i]){
            if(!vis[i]){
                dis++;vis[i] = 1;
                for(int j = D[i];j != i;j = D[j]){
                    for(int k = R[j];k != j;k = R[k]){
                        vis[col[k]] = 1;
                    }
                }
            }
        }
        return dis;
    }

    bool dfs(int deep)
    {
        if(deep + A() > res) return false;
        if(!R[0]) return true;
        int c = R[0];
        for(int i = R[0];i != 0;i = R[i]){
            if(S[i] < S[c]){
                c = i;
            }
        }
        for(int i = D[c];i != c;i = D[i]){
            //每次将第i列其他节点删除,只保留第i节点,为了找该行的节点
            Remove1(i);
            //将列上的节点完全与矩阵脱离,只删列首节点是不行的
            for(int j = R[i];j != i;j = R[j]){
                Remove1(j);
            }
            if(dfs(deep + 1)) return true;
            for(int j = L[i];j != i;j = L[j]){
                resume1(j);
            }
            resume1(i);
        }
        return false;
    }
    int IDEA(int k)
    {
        res = 0;
        while(true)
        {
            if(res > k) break;
            //cout << res << endl;
            if(dfs(0)) return res;
            res++;
        }
        return -1;
    }
}dlx;

const int N = 105;
char s[N];
int p[10][10];
pair<pair<int,int>,int>ve[805];

void init()
{
    int len = strlen(s);
    dlx.init(729,4 * 81);
    int cnt = 1;
    for(int i = 0;i < len;++i){
        int x = i / 9,y = i % 9;
        if(s[i] != '.'){
            int k = s[i] - '0';
            p[x][y] = k;
            int z = (x / 3) * 3 + (y / 3);
            dlx.Insert(cnt,x * 9 + y + 1);
            dlx.Insert(cnt,81 + x * 9 + k);
            dlx.Insert(cnt,2 * 81 + 9 * y + k);
            dlx.Insert(cnt,3 * 81 + 9 * z + k);
            ve[cnt].fi = mp(x,y);ve[cnt].se = k;
            cnt++;
        }else{
            int z = (x / 3) * 3 + (y / 3);
            for(int j = 1;j <= 9;++j){
                dlx.Insert(cnt,x * 9 + y + 1);
                dlx.Insert(cnt,81 + x * 9 + j);
                dlx.Insert(cnt,2 * 81 + 9 * y + j);
                dlx.Insert(cnt,3 * 81 + 9 * z + j);
                ve[cnt].fi = mp(x,y);ve[cnt].se = j;
                cnt++;
            }
        }
    }
    dlx.res = inf;
    dlx.dance(0);
    //cout << dlx.res << endl;
    for(int i = 0;i < dlx.res;++i){
        p[ve[dlx.ans[i]].fi.fi][ve[dlx.ans[i]].fi.se] = ve[dlx.ans[i]].se;
    }
    for(int i = 0;i < 9;++i){
        for(int j = 0;j < 9;++j){
            printf("%d",p[i][j]);
        }
    }
    printf("\n");
}

int main()
{
    while(~scanf("%s",s))
    {
        if(strcmp(s,"end") == 0){
            break;
        }
        init();
    }
    return 0;
}

10-02 19:18