Problem 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
527389416819426735436751829375692184194538267268174593643217958951843672782965341 416837529982465371735129468571298643293746185864351297647913852359682714128574936
这题得用DLX来做。由于0较多故DFS会t。
之前由于会了DLX但还是不知道如何将数独转换为01矩阵而不会做这题。
经过了2天的沉淀和翻阅了网上大大小小的解题思路。终于搞明白了!
首先我们需要知道的是这题有4个限制条件
1.一格只能填一格数。
2.一行1~9不能重复。
3.一列1~9不能重复。
4.一个3*3九宫格1~9不能重复。
然后由于有81个格子。每个格子是1~9。故一共有9*81=729行。代表729种可能。
由于精准覆盖问题是选择行,令每一列上都恰好有一个1.
即我们选择81行,令每一列上都恰好有一个1,并令其表示为这81个格子满足上述4个条件。
每9行表示一个数的9个取值(如第1~9行表示第一行第一列数表示1~9的情况)
然后分析列(即如何表示限制条件)
对于第一个限制条件。
我们需要81列,表示81个位置,每一行在这81列中只有一个1,代表该数所在的位子。(如第1~9行的第1列为1其他为0,10~18行的第2列都为1其他为0)
对于第二个限制条件。
我们需要81列。表示9行上的1~9。1~9列表示第一行的1~9,10~18列表示第2行的1~9.
(如1行的第1列为1,表示原数独第一行第一列的值取1,第2行的第2列为1,表示原数独第一行第一列取2,第10行的第5列为1,表示原数独第一行第二列取5)
对于第三个限制条件。
我们还是需要81列。表示9列上的9个数。与行同理。
对于第四个限制条件。
由于一共有9个九宫格,每个九宫格都有9个数。故跟行,列同理。也是81列。
故我们一共需要81*4=324列来表示限制条件。
可以观察到当找到精准覆盖的解后。所得到的行数是每9行取一个值。
每9行代表一个位置。该行所在的行数相对于9行的位置即该行所对应的值。
根据此我们也可以很轻松的获得数独的解。
对于数独中已经填好的数。我们只要在那一行填入相应的信息,另外8行为空即可。
由于前81列中的某一列只有这一行有1,故为了找出答案这一行必须加入考虑。
为了更方便与理解,我们将第一个样例中前3个点所表示的矩阵表示一下。(一个……表示填0,数量为直到下一个限制条件(即81-已经填好的部分),即被……隔开的部分分别代表位置行列九宫格的限制条件)
前3个点为.27
1……1……1……1(第一行第1列第一个九宫格取1)
1……01……01……01(第一行第一列第一个九宫格取2)
1……001……001……01(取3)
1……0001……0001……0001(取4)
1……00001……00001……00001(取5)
1……000001……000001……000001(取6)
1……0000001……0000001……0000001(取7)
1……00000001……00000001……00000001(取8)
1……000000001……000000001……000000001(取9)
……………………
01……01……00000000001……01(第1行第2列第1个九宫格取2)
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
……………………
001……0000001……0000000000000000000000001……0000001(第1行第3列第1个九宫格取7)
……………………
……………………
AC代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define mx 250505 using namespace std; int n,m,cnt; int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//定义一个点的左右上下以及行数列数。 int h[mx],s[mx];//一行的第一个数 ,一列有几个数 int ansk[mx],a[10][10];//答案 inline void Init(int m){//初始化m列。m+1个数,0为head(无实际意义,是最后用来判断的 for(int i=0;i<=m;i++){ r[i]=i+1; l[i]=i-1; u[i]=d[i]=i; } r[m]=0,l[0]=m; memset(h,-1,sizeof(h)); memset(s,0,sizeof(s)); cnt=m+1;//之后录入的数从m+1的下标开始,且1~m的列标在最下面 } inline void link(int R,int C){//插入一个在R行C列的点 s[C]++; row[cnt]=R,col[cnt]=C;//记录行和列 d[cnt]=C;//cnt的下面为c,即1~m u[cnt]=u[C];//cnt的上面变为原先C的上面面 d[u[C]]=cnt;//原先c的上面的下面变为cnt u[C]=cnt; //c的上面变为cnt。一系列操作即将cnt插入C和C下面一个数之间,让cnt成为最接近c的那个数 if(h[R]<0)//如果这一行没有数的话就将该数作为第一个数录入 h[R]=r[cnt]=l[cnt]=cnt; else{//有数的话 l[cnt]=h[R];//将cnt的左边连接到h[R]的右边 r[cnt]=r[h[R]];//将cnt的右边连接到h[R]的右边 l[r[h[R]]]=cnt;//将原来h[R]的右边连接到cnt的右边 r[h[R]]=cnt;//将cnt连接到h[R]的右边 } cnt++; return; } inline void remove(int C){//删除c列和c列上有点的行 r[l[C]]=r[C],l[r[C]]=l[C];//删除这一列的存在。 for(int i=u[C];i!=C;i=u[i])//找每个在该列上的数 for(int j=r[i];j!=i;j=r[j]){//找该列上的数所在的那行 ,并删除整行 u[d[j]]=u[j]; d[u[j]]=d[j]; s[col[j]]--;//该数所在列内数量-1 } return; } inline void resume(int C){//恢复c列和c列上有点的行 r[l[C]]=C,l[r[C]]=C; for(int i=u[C];i!=C;i=u[i]) for(int j=r[i];j!=i;j=r[j]){ u[d[j]]=j; d[u[j]]=j; s[col[j]]++; } return; } bool dance(int deep){ if(r[0]==0){//如果列删光了且除了head没有元素留下来。则表示该情况成立 int x,y,v; for(int i=0;i<deep;i++){ x=(ansk[i]-1)/9/9; y=(ansk[i]-1)/9%9; v=ansk[i]%9; if(v==0) v=9; a[x][y]=v; } return 1; } int c=r[0]; for(int i=r[0];i!=0;i=r[i])//优先从列中数最少的开始找。缩小查找范围 if(s[i]<s[c]) c=i; remove(c);//删除c列 for(int i=d[c];i!=c;i=d[i]){//从c列当中选1行进行查找 ansk[deep]=row[i];//记录当前被删的行数 for(int j=r[i];j!=i;j=r[j])//删除被c列i行影响而不能选择的列 remove(col[j]); if(dance(deep+1)) return 1; for(int j=l[i];j!=i;j=l[j]) resume(col[j]); } resume(c); return 0; } int main(){ while(1){ Init(324); //729行*324列。81个数*9种填法=729行。第几行记录填谁,列为填的位置。 memset(a,0,sizeof(a)); char temp; int x,o; for(int i=0;i<=8;i++) for(int j=0;j<=8;j++){ temp=getchar(); if(temp==‘ ‘||temp==‘\n‘){ j--; continue; }if(temp==‘e‘) return 1; else if(temp==‘.‘) x=0; else x=temp-‘0‘; a[i][j]=x; for(int k=1;k<=9;k++){ if(x&&x!=k)//如果该空已经填好了,就只填那一行即可。 continue; o=i*9*9+j*9+k;//填在矩阵的第几行 link(o,i*9+j+1);//填在原数独的哪个位置 link(o,i*9+81+k);//填在原数独的哪一行 link(o,j*9+81*2+k);//填在原数独的哪一列 link(o,81*3+(i/3*3+j/3)*9+k);//填在原数独的哪一个九宫格 } } dance(0); for(int i=0;i<=8;i++){ for(int j=0;j<=8;j++) printf("%d",a[i][j]); } printf("\n"); } return 0; }
2020 BIT冬训-图&&DFS&&BFS E - Sudoku POJ - 3074
原文:https://www.cnblogs.com/mikku39/p/14457138.html