Sudoku
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2015-04-18)
System Crawler (2015-04-18)
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 用dancing links解数独，DLX专题的终极目标，手机上的数独玩了两天后终于A了，等下把记录用这个程序刷一遍，想象下小伙伴看到我最高难度下的耗时记录的表情，啊哈哈~~
难点在于怎么建立模型，一共有9行，每行有9个数字，所以就是9 * 9，同理，列也是9 * 9，小格子也是有9个，每个也是9个数字，所以也是9 * 9，另外整个图有9 * 9 = 81的格子。所以要覆盖的列就是 9 * 9 + 9 * 9 + 9 * 9 + 81。至于行，一共有81个格子，每个格子有9种取法，所以就有81 * 9行，行和列相乘就是开的数组的大小。还有个剪枝要注意下，如果某个格子的数字已经给出，那么这一行，这一列，这一个小格子，就没必要再填这个数了，不剪枝的话会T。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <map>
#include <cctype>
using namespace std; const int HEAD = ;
const int SIZE = ( * ) * ( * );
const int COL = * ;
int U[SIZE],D[SIZE],L[SIZE],R[SIZE],S[SIZE],C[SIZE],N[SIZE],P_H[SIZE],P_C[SIZE];
int COUNT;
int TEMP[][];
bool VIS_I[][],VIS_J[][],VIS_G[][];
struct Node
{
int i;
int j;
int num;
}ANS[]; void ini(void);
void link(int,int,int,int,int,int,int);
bool dancing(int);
void remove(int);
void resume(int);
void debug(int);
int main(void)
{
char s[];
while(scanf(" %s",s + ) && strcmp(s + ,"end"))
{
ini();
for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
{
int k = s[(i - ) * + j];
int c_1,c_2,c_3,c_4;
if(k != '.')
{
VIS_I[i][k - ''] = VIS_J[j][k - ''] = true;
VIS_G[(i - ) / * + (j - ) / + ][k - ''] = true;
c_1 = * + (i - ) * + k - '';
c_2 = * + (j - ) * + k - '';
c_3 = * + ((i - ) / * + (j - ) / ) * + k - '';
c_4 = * + (i - ) * + j;
link(c_1,c_2,c_3,c_4,k - '',i,j);
}
} for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
{
if(s[(i - ) * + j] != '.')
continue;
int c_1,c_2,c_3,c_4;
for(int k = ;k <= ;k ++)
{
if(VIS_I[i][k] || VIS_J[j][k] ||
VIS_G[(i - ) / * + (j - ) / + ][k])
continue;
c_1 = * + (i - ) * + k;
c_2 = * + (j - ) * + k;
c_3 = * + ((i - ) / * + (j - ) / ) * + k;
c_4 = * + (i - ) * + j;
link(c_1,c_2,c_3,c_4,k,i,j);
}
}
dancing();
} return ;
} void ini(void)
{
L[HEAD] = COL;
R[HEAD] = ;
for(int i = ;i <= COL;i ++)
{
L[i] = i - ;
R[i] = i + ;
U[i] = D[i] = C[i] = i;
S[i] = ;
}
R[COL] = HEAD; fill(&VIS_I[][],&VIS_I[][],false);
fill(&VIS_J[][],&VIS_J[][],false);
fill(&VIS_G[][],&VIS_G[][],false);
COUNT = COL + ;
} void link(int c_1,int c_2,int c_3,int c_4,int num,int r,int c)
{
int first = COUNT;
int col; for(int i = ;i < ;i ++)
{
switch(i)
{
case :col = c_1;break;
case :col = c_2;break;
case :col = c_3;break;
case :col = c_4;break;
} L[COUNT] = COUNT - ;
R[COUNT] = COUNT + ;
U[COUNT] = U[col];
D[COUNT] = col; D[U[col]] = COUNT;
U[col] = COUNT;
C[COUNT] = col;
N[COUNT] = num;
P_H[COUNT] = r;
P_C[COUNT] = c;
S[col] ++;
COUNT ++;
}
L[first] = COUNT - ;
R[COUNT - ] = first;
} bool dancing(int k)
{
if(R[HEAD] == HEAD)
{
for(int i = ;i < k;i ++)
TEMP[ANS[i].i][ANS[i].j] = ANS[i].num;
int count = ;
for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
printf("%d",TEMP[i][j]);
puts("");
return true;
} int c = R[HEAD];
for(int i = R[HEAD];i != HEAD;i = R[i])
if(S[c] > S[i])
c = i; remove(c);
for(int i = D[c];i != c;i = D[i])
{
ANS[k].i = P_H[i];
ANS[k].j = P_C[i];
ANS[k].num = N[i];
for(int j = R[i];j != i;j = R[j])
remove(C[j]);
if(dancing(k + ))
return true;
for(int j = L[i];j != i;j = L[j])
resume(C[j]);
}
resume(c); return false;
} void remove(int 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])
{
D[U[j]] = D[j];
U[D[j]] = U[j];
S[C[j]] --;
}
} void resume(int c)
{
L[R[c]] = c;
R[L[c]] = c;
for(int i = D[c];i != c;i = D[i])
for(int j = L[i];j != i;j = L[j])
{
D[U[j]] = j;
U[D[j]] = j;
S[C[j]] ++;
}
}