首页 > ACM题库 > HDU-杭电 > HDU 3909-Sudoku[解题报告]HOJ
2015
04-14

HDU 3909-Sudoku[解题报告]HOJ

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 it`s 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
7ADC1GB4928F365E
F245EA73B61C98DG
3E6189CD7AG5F24B
E873461G59F2BDAC
492D3C5FA8EB7G61
15CF98AB6D7G43E2
B6AG2ED7C34189F5
8F3BG1E24CAD6579
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;
}
void link(int r,int c)
{
	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;
				link(x+1,y1+1);
				link(x+1,y2+1);
				link(x+1,y3+1);
				link(x+1,y4+1);
			}
		}
}
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
    不知道题目例子是怎么得出来的