POJ3074 Sudoku —— Dancing Links 精确覆盖-白红宇

POJ3074 Sudoku —— Dancing Links 精确覆盖

阅读量：5070 次

发布时间：2019-06-12

本文共 3750 字，大约阅读时间需要 12 分钟。

题目链接：

Sudoku

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10451		Accepted: 3776

Description

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

527389416819426735436751829375692184194538267268174593643217958951843672782965341416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

题解：

（来自万仓一黍）

Dancing Links的一些特点：

1.矩阵中每个元素的值只能是0或1（在实际操作中只记录1）。

2.行代表着放置情况，列代表着约束条件。其中矩阵中的行和列的编号从1开始。

3.选择若干行，使得其满足所有约束条件。

对于此题：

1.行：9*9*9，表明有9*9个格子，每个格子有9中情况。

2.列：9*9*4，首先每个格子能且仅能放1个数字，其次每一行的九个数字能且仅能被放一次，再者列如行者，最后每个九宫格的九个数字能且仅能被放一次。

3.所以构成了(9*9*9) * (9*9*4)的矩阵，然后直接套模板。

代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 #define ms(a,b) memset((a),(b),sizeof((a))) 13 using namespace std; 14 typedef long long LL; 15 const int N = 9; 16 const int MaxN = N*N*N+10; 17 const int MaxM = N*N*4+10; 18 const int maxnode = MaxN*4 + MaxM + 10; 19 20 char g[MaxN]; 21 struct DLX //矩阵的行和列是从1开始的 22 { 23 int n, m, size; //size为结点数 24 int U[maxnode], D[maxnode], L[maxnode], R[maxnode], Row[maxnode], Col[maxnode]; 25 int H[MaxN], S[MaxM]; //H为每一行的头结点，但不参与循环。S为每一列的结点个数 26 int ansd, ans[MaxN]; 27 28 void init(int _n, int _m) //m为列 29 { 30 n = _n; 31 m = _m; 32 for(int i = 0; i<=m; i++) //初始化列的头结点 33 { 34 S[i] = 0; 35 U[i] = D[i] = i; 36 L[i] = i-1; 37 R[i] = i+1; 38 } 39 R[m] = 0; L[0] = m; 40 size = m; 41 for(int i = 1; i<=n; i++) H[i] = -1; //初始化行的头结点 42 } 43 44 void Link(int r, int c) 45 { 46 size++; //类似于前向星 47 Col[size] = c; 48 Row[size] = r; 49 S[Col[size]]++; 50 D[size] = D[c]; 51 U[D[c]] = size; 52 U[size] = c; 53 D[c] = size; 54 if(H[r]==-1) H[r] = L[size] = R[size] = size; //当前行为空 55 else //当前行不为空： 头插法，无所谓顺序，因为Row、Col已经记录了位置 56 { 57 R[size] = R[H[r]]; 58 L[R[H[r]]] = size; 59 L[size] = H[r]; 60 R[H[r]] = size; 61 } 62 } 63 64 void remove(int c) //c是列的编号， 不是结点的编号 65 { 66 L[R[c]] = L[c]; R[L[c]] = R[c]; //在列的头结点的循环队列中， 越过列c 67 for(int i = D[c]; i!=c; i = D[i]) 68 for(int j = R[i]; j!=i; j = R[j]) 69 { 70 //被删除结点的上下结点仍然有记录 71 U[D[j]] = U[j]; 72 D[U[j]] = D[j]; 73 S[Col[j]]--; 74 } 75 } 76 77 void resume(int c) 78 { 79 L[R[c]] = R[L[c]] = c; 80 for(int i = U[c]; i!=c; i = U[i]) 81 for(int j = L[i]; j!=i; j = L[j]) 82 { 83 U[D[j]] = D[U[j]] = j; 84 S[Col[j]]++; 85 } 86 } 87 88 bool Dance(int d) 89 { 90 if(R[0]==0) 91 { 92 for(int i = 0; i

View Code

转载于:https://www.cnblogs.com/DOLFAMINGO/p/7538574.html

你可能感兴趣的文章

.	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	.

.	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	.

.	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	.