Sudoku數獨問題

Posted on Edited on Views: Symbols count in article: 3.4k Reading time ≈ 3 mins.

題序

給定一個n*n的表格，保證原始表格合法，求字典序最小之解，若無解則輸出”NO SOLUTION”

限制範圍: n<= 3, 1<= digits<= n^2

題目： uva989、tioj 1025

題解

  • DFS(depth first search)

    紀錄原始表格、每一行、每一列及每一宮的狀況，DFS對每一格窮舉1~n^2個數字，遞迴求解

  • Dancing links

    一種資料結構，聽說可以解這題但是我不會，寫在這邊順便督促自己要快快把他學會

code (一組解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstring> 
#include<iostream> 
#include<vector> 
#include<algorithm>
#define n 10
using namespace std;
vector<vector<int> > m(n, vector<int>(n)); 
vector<vector<int> > row(n, vector<int>(n));
vector<vector<int> > col(n, vector<int>(n));
vector<vector<int> > mt(n, vector<int>(n));
vector<vector<int> > fix(n, vector<int>(n));
int f= 0, ans= 1, nn, gg= 0; 
void dfs(int x, int y){
	
	int flag= 0, z= y/nn, yu= y%(nn*nn); 
	if(x== nn*nn-1) yu++;
	if(x==y&&y==nn*nn-1&&fix[y][x]) f= 1;
	if(fix[y][x]) dfs((x+1)%(nn*nn), yu); 

	for(int i=1; i<nn*nn+1; i++){
		if(f||fix[y][x]) continue; 

		if(col[y][i]|| row[x][i]||mt[x/nn+z*nn][i]){
			flag++; 
			continue; 
		}
		col[y][i]= 1,row[x][i]= 1, mt[x/nn+z*nn][i]= 1;  
		m[y][x]= i; 
		dfs((x+1)%(nn*nn), yu); 

		col[y][i]= 0, row[x][i]= 0, mt[x/nn+z*nn][i]= 0; 
	}
	if(x==y&&y==nn*nn-1&&flag!= nn*nn) f= 1;
	if(flag== nn*nn) return; 

}
void solve(){
	while(cin>>nn){ 
		if(gg++) cout<<endl;
		for(int i=0;i<n; i++){
			for(int j=0; j<n; j++){
				col[i][j]= 0; 
				row[i][j]= 0; 
				mt[i][j]= 0; 
				fix[i][j]= 0; 
				f= 0; 
			}
		}
		for(int i=0; i<nn*nn; i++){
			int y= i/nn; 
			for(int j=0; j<nn*nn; j++) {
				cin>>m[i][j]; 
				fix[i][j]= m[i][j]; 
				if(m[i][j]== 0) continue; 
				col[i][m[i][j]]++;
				row[j][m[i][j]]++; 
				mt[j/nn+y*nn][m[i][j]]++; 
			}
		}
		dfs(0, 0);
		
		if(!f) cout<<"NO SOLUTION"<<endl; 
		else{
			for(int i=0; i<nn*nn; i++){
				for(int j=0; j<nn*nn; j++){
					if(j) cout<<" ";
					cout<<m[i][j]; 
				}
				cout<<endl;
			}
		}
	}
}
int main(){
	solve(); 
	return 0; 
}

code (全部解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstring> 
#include<iostream> 
#include<vector> 
#include<algorithm>
#define n 10
using namespace std;
int rec[10][10];  
vector<vector<int> > row(n, vector<int>(n));
vector<vector<int> > col(n, vector<int>(n));
vector<vector<int> > mt(n, vector<int>(n));
vector<vector<int> > fix(n, vector<int>(n));
int f= 0, ans= 0; 
void dfs(int x, int y){
	if(f){
		ans++; 
		for(int i=0; i<9; i++){
			for(int j=0; j<9; j++){
				if(j) cout<<" "; 
				cout<<rec[i][j];  
			}
			cout<<endl;
		}
		cout<<endl;
		f= 0; 
	}
	int flag= 0, z= y/3, yu= y%9; 
	if(x== 8) yu++;
	if(x==y&&y==8&&fix[y][x]) f= 1;

	if(fix[y][x]) dfs((x+1)%9, yu); 

	for(int i=1; i<10; i++){
		if(fix[y][x]||f) continue; 

		if(col[y][i]|| row[x][i]||mt[x/3+z*3][i]){
			flag++; 
			continue; 
		}
		col[y][i]= 1,row[x][i]= 1, mt[x/3+z*3][i]= 1;  
		rec[y][x]= i; 
		if(x==y&&y==8) f= 1; 
		dfs((x+1)%9, yu);
		col[y][i]= 0, row[x][i]= 0, mt[x/3+z*3][i]= 0; 
	}

	if(flag== 9) return; 
}
void solve(){

	for(int i=0; i<9; i++){
		int y= i/3; 
		for(int j=0; j<9; j++) {
			cin>>rec[i][j]; 
			fix[i][j]= rec[i][j]; 
			col[i][rec[i][j]]= 1;
			row[j][rec[i][j]]= 1; 
			mt[j/3+y*3][rec[i][j]]= 1; 
		}
	}
	dfs(0, 0);
	cout<<"there are a total of "<<ans<<" solution(s)."<<endl;
}

int main(){
	solve(); 
	return 0; 
}