首页 > 代码库 > HDU 3909 数独

HDU 3909 数独

2024-07-02 13:30:14   224人阅读

Sudoku

Time Limit: 50000/20000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 501    Accepted Submission(s): 208


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

 

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.
 

Output
For each case:
If the grid is not a puzzle, and has no solution, print “No Solution”, or has multiple solutions print “Multiple Solutions”.
If the grid is a puzzle, but not a minimal, print “Not Minimal”, or print N lines represent the answer in the same format in the input, and ‘.’ should be replaced with the right characters. You can get more information from the sample output.

 

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.
 

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


先判断是否有解，无解或者多解直接返回，唯一解的话判断是否为最小解，加入是最小解的话输出最小解。

判断前面的部分只需要dfs跑一次，假如解数为0，无解，解数大于1，多解，判断是否为最小解需要枚举把给定的矩阵里面的字母换成‘.‘,然后dlx判定

是否为多解，假如存在不是多解的情况，直接break，说明不是最小解，否则输出

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/1 18:36:44
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
int tmp[100100];
int change1(char ch){
	if(ch>=‘0‘&&ch<=‘9‘)return ch-‘0‘;
	else return 10+ch-‘A‘;
}
char change2(int x){
	if(x>=0&&x<=9)return x+‘0‘;
	return (x-10)+‘A‘;
}
struct DLX{  
    const static int maxn=2001000;  
    #define FF(i,A,s) for(int i = A[s];i != s;i = A[i])  
    int L[maxn],R[maxn],U[maxn],D[maxn];  
    int size,col[maxn],row[maxn],s[maxn],H[maxn];  
    bool vis[10000];  
    int ans[maxn],cnt,tot; 
    void init(int m){  
        for(int i=0;i<=m;i++){  
            L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;  
        }  
        memset(H,-1,sizeof(H));  
        L[0]=m;R[m]=0;size=m+1;  
		tot=0;
    }  
    void link(int r,int c){  
         U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;  
         if(H[r]<0)H[r]=L[size]=R[size]=size;  
         else {  
             L[size]=H[r];R[size]=R[H[r]];  
             L[R[H[r]]]=size;R[H[r]]=size;  
         }  
         s[c]++;col[size]=c;row[size]=r;size++;  
     }  
    void del(int c){//精确覆盖  
        L[R[c]]=L[c];R[L[c]]=R[c];    
        FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];    
    }    
    void add(int c){  //精确覆盖  
        R[L[c]]=L[R[c]]=c;    
        FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];    
    }    
    int dfs(int k){//精确覆盖  
        if(!R[0]&&k){    
			memcpy(ans,tmp,sizeof(tmp));cnt=k;
			return ++tot;
        }    
        int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;    
        del(c);    
        FF(i,D,c){    
            FF(j,R,i)del(col[j]);    
            tmp[k]=row[i];
			if(dfs(k+1)==2)return 2;    
            FF(j,L,i)add(col[j]);    
        }    
        add(c);    
        return 0;
    }      
    void remove(int c){//重复覆盖  
        FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];  
    }  
     void resume(int c){//重复覆盖  
         FF(i,U,c)L[R[i]]=R[L[i]]=i;  
     }  
    int A(){//估价函数  
        int res=0;  
        memset(vis,0,sizeof(vis));  
        FF(i,R,0)if(!vis[i]){  
                res++;vis[i]=1;  
                FF(j,D,i)FF(k,R,j)vis[col[k]]=1;  
            }  
        return res;  
    }  
    void dfs(int now,int &ans){//重复覆盖  
        if(R[0]==0)ans=min(ans,now);  
        else if(now+A()<ans){  
            int temp=INF,c;  
            FF(i,R,0)if(temp>s[i])temp=s[i],c=i;  
            FF(i,D,c){  
                remove(i);FF(j,R,i)remove(j);  
                dfs(now+1,ans);  
                FF(j,L,i)resume(j);resume(i);  
            }  
        }  
    }  
}dlx;  
const int SLOT=0;
const int ROW=1;
const int COL=2;
const int SUB=3;
int encode(int a,int b,int c,int n){
	if(n==2)return 16*a+4*b+c+1;
	if(n==3)return 81*a+9*b+c+1;
	if(n==4)return 256*a+16*b+c+1;
}
void decode(int code,int &a,int &b,int &c,int n){
	code--;int pp=n*n;
	c=code%pp;code/=pp;
	b=code%pp;code/=pp;
	a=code;
}
char str[20][20];
int build(int n){
	dlx.init(4*n*n*n*n);
	for(int r=0;r<n*n;r++)
		for(int c=0;c<=n*n;c++)
			for(int k=1;k<=n*n;k++)
				if(str[r][c]==‘.‘||str[r][c]==change2(k)){
					int p=encode(r,c,k-1,n);
					int a1,a2,a3,a4;
                         dlx.link(p,a1=encode(SLOT,r,c,n));  
                         dlx.link(p,a2=encode(ROW,r,k-1,n));  
                         dlx.link(p,a3=encode(COL,c,k-1,n));  
                         dlx.link(p,a4=encode(SUB,(r/n)*n+c/n,k-1,n));  
					//	 cout<<"han: "<<p<<" "<<a1<<" "<<a2<<" "<<a3<<" "<<a4<<endl;
				}
	return dlx.dfs(0);
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int n;
	 while(~scanf("%d",&n)){
		 for(int i=0;i<n*n;i++)scanf("%s",str[i]);
		 int hh=build(n);
		 //cout<<"hh="<<hh<<" "<<dlx.tot<<" "<<dlx.cnt<<endl;
		 if(dlx.tot==0)puts("No Solution");
		 else if(dlx.tot==2)puts("Multiple Solutions");
		 else{
			 int flag=1;
			 for(int i=0;i<n*n;i++)
				 for(int j=0;j<n*n;j++){
					 if(str[i][j]==‘.‘)continue;
					 char ch=str[i][j];str[i][j]=‘.‘;
					 build(n);
					 if(dlx.tot!=2){
						 flag=0;
						 break;
					 }
					 str[i][j]=ch;
				 }
			 if(!flag)puts("Not Minimal");
			 else {
				 build(n);
				 for(int i=0;i<dlx.cnt;i++){
					 int r,c,v;
					 decode(dlx.ans[i],r,c,v,n);
					 str[r][c]=change2(v+1);
				 }
				 for(int i=0;i<n*n;i++)printf("%s\n",str[i]);
			 }
		 }
	 }
     return 0;
}



联系
我们