2015
04-14

# Sudoku

AmazingCaddy likes Sudoku very much. One day, he got some Sudoku problems and he wondered whether these problems are well designed. He needs your help now.

Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9 × 9 grid with digits so that each column, each row, and each of the nine 3 × 3 regions contain all of the digits from 1 to 9.
– Wikipedia

In this problem, the grid has three different sizes, with the formal (N^2) × (N^2), and N will be one in 2, 3 and 4. The rule is the same. The objective is to fill the (N^2) × (N^2) grid with characters so that each column, each row, and each of the N^2 regions (each size is N × N) contains all of the characters from 1 to 4(N = 2), 1 to 9(N = 3) or 1 to G (N = 4).

You task is that when you got a grid, you should tell the grid whether a puzzle or not. If its a puzzle, you should tell whether it is a minimal puzzle; else you should tell it has no solution or has multiple solutions.

A puzzle is a partially completed grid (the size is (N^2) × (N^2), N = 2, 3, 4), and has one and only one solution. If remove any character from a puzzle, it will lead to multiple solutions, then it is called a minimal puzzle.

The input contains several cases. For each case, the first line of the input is the N (2<= N <=4). The next N^2 lines will contain the grid. Each line will have N^2 characters, represent the grid. The empty cell will be represented as ’.’. All input data is legal, and you can get more information from the sample input.

The input contains several cases. For each case, the first line of the input is the N (2<= N <=4). The next N^2 lines will contain the grid. Each line will have N^2 characters, represent the grid. The empty cell will be represented as ’.’. All input data is legal, and you can get more information from the sample input.

2
4312
12.4
....
...1
3
5...9.31.
71.8...9.
32...6...
........3
.8.5.3...
4....1.5.
8..9...4.
...1..9..
.....7...
4
...86.....D.A...
.A.C.G.49....65E
.......3B61C..DG
3...89.D7....24.
....4..G.9F2BD..
49...C5.....7...
1.C..8.B6.......
.6A.2.D...4.89.5
8F3BG.E24.A...7.
...6.3.A.1......
D.........5.1E2.
.G...D.9........
......F6.7.....3
6D.9.7..EG...B..
51B.A..8........
........F.C..71.

Not Minimal
Multiple Solutions
9BG86F253ED4A1C7
F245EA73B61C98DG
3E6189CD7AG5F24B
E873461G59F2BDAC
492D3C5FA8EB7G61
15CF98AB6D7G43E2
B6AG2ED7C34189F5
C756F38A219EG4BD
D49A7B6CGF531E28
2G1E5D498B67CF3A
GCE4D5F617B82A93
6DF9C731EG2A5B84
51B7A298D436ECGF
A382B4GEF5C9D716

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define max_node 16*16*16*16*16*4+100
#define inf 0xfffffff
int total;
int R[max_node];
int L[max_node];
int U[max_node];
int D[max_node];
int col[max_node];
int row[max_node];
int h[16*16*16+10];
int s[16*16*4+10];
int ans[16*16*16+10];
void initDL(int c)
{
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
for(int i=0;i<=c;i++)
{
D[i]=U[i]=i;
L[i+1]=i;
R[i]=i+1;
}
R[c]=0;
total=c+1;
}
{
s[c]++;
row[total]=r;
col[total]=c;
U[total]=U[c];
D[U[c]]=total;
D[total]=c;
U[c]=total;
if(h[r] == -1)
h[r]=L[total]=R[total]=total;
else
{
L[total]=L[h[r]];
R[L[h[r]]]=total;
R[total]=h[r];
L[h[r]]=total;
}
total++;
}
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])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
s[col[j]]--;
}
}
void resume(int 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 flag[max_node];
int num;
void dance(int dep)
{
if(num == 2)
return;
if(R[0] == 0)
{
num++;
if(num == 1)
{
memset(flag,false,sizeof(flag));
for(int i=0;i<dep;i++)
flag[ans[i]]=true;
}
return;
}
int mm=inf;
int c;
for(int i=R[0];i;i=R[i])
if(s[i] < mm)
{
mm=s[i];
c=i;
}
remove(c);
for(int i=D[c];i!=c;i=D[i])
{
ans[dep]=row[i];
for(int j=R[i];j!=i;j=R[j])
remove(col[j]);
dance(dep+1);
if(num == 2)
return;
for(int j=L[i];j!=i;j=L[j])
resume(col[j]);
}
resume(c);
return;
}
int N,M;
void build(char str[][110])
{
initDL(M*M*4);
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
{
int begin,end;
if(str[i][j] == '.')
{
begin=0;
end=M-1;
}
else
{
if('A' <= str[i][j] && str[i][j] <= 'Z')
begin=end=str[i][j]-'A'+9;
else
begin=end=str[i][j]-'1';
}
for(int k=begin;k<=end;k++)
{
int x=i*M*M+j*M+k;
int y1=i*M+j;
int y2=M*M+i*M+k;
int y3=M*M+M*M+j*M+k;
int y4=M*M+M*M+M*M+((i/N)*N+(j/N))*M+k;
}
}
}
char g[110][110];
char str[110][110];
void get_num()
{
build(str);
num=0;
dance(0);
}
int main()
{
while(scanf("%d",&N)!=EOF)
{
M=N*N;
for(int i=0;i<M;i++)
scanf("%s",g[i]);
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
str[i][j]=g[i][j];
get_num();
if(num == 0)
printf("No Solution\n");
else if(num == 2)
printf("Multiple Solutions\n");
else
{
bool ok=true;
for(int i=0;i<M && ok;i++)
for(int j=0;j<M && ok;j++)
{
if(g[i][j] != '.')
{
str[i][j]='.';
get_num();
if(num != 2)
ok=false;
str[i][j]=g[i][j];
}
}
if(ok)
{
get_num();
for(int i=0;i<M;i++)
{
for(int j=0;j<M;j++)
for(int k=1;k<=M;k++)
if(flag[i*M*M+j*M+k])
{
if(k >= 10)
printf("%c",'A'+(k-10));
else
printf("%c",'0'+k);
break;
}
printf("\n");
}
}
else
printf("Not Minimal\n");
}
}
return 0;
}`

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的