Dancing Links ---- D - Sudoku

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

. 2 7 3 8 . . 1 .
. 1 . . . 6 7 3 5
. . . . . . . 2 9
3 . 5 6 9 2 . 8 .
. . . . . . . . .
. 6 . 1 7 4 5 . 3
6 4 . . . . . . .
9 5 1 8 . . . 7 .
. 8 . . 6 5 3 4 .
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.****.net/WhereIsHeroFrom/article/details/79220897
对于一个N阶的数独，由N^2×N2个格子组成，如图为一个3阶的数独。要求满足四个限制条件：

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

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

[0, 81)列分别对应了81个格子是否被放置了数字。
[82, 2*81)列分别对应了9行，每行[1, 9]个数字的放置情况；
[281, 381)列分别对应了9列，每列[1, 9]个数字的放置情况；
[381, 481)列分别对应了9个“宫”，每“宫”[1, 9]个数字的放置情况；
所以总的列数为4*81=324列。如图五-4-2所示。

举个例子，对于在数独棋盘的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，比较好理解；那么宫号我们定义如下图：

宫号的计算方式可以通过行号和列号得出。即宫号 = (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;
}

Dancing Links ---- D - Sudoku

相关推荐