0%

DFS解数独

发表于 更新于 分类于
学完DFS乱搞出的东西

Step.1 通过judge判断是否合法

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
bool judge(int now)
{
	int row = now / 9;
	//当前行
	int col = now % 9;
	//当前列
	int j;
	for(j = 0; j < 9; ++j)
	{
		if(maap[row][j] == maap[row][col] && j != col)
		{
			return false;
		}
	}//这是检查同一行中的重复
	for(j = 0; j < 9; ++j)
	{
		if(maap[j][col] == maap[row][col] && j != row)
		{
			return false;
		}
	}//这是检查同一列中的重复
	int tmp_row = row / 3 * 3;
	int tmp_col = col / 3 * 3;
	for(j = tmp_row; j < tmp_row + 3;++j)
	{
		for(int k = tmp_col; k < tmp_row + 3; ++k)
		{
			if(maap[j][k] == maap[row][col] && j != row && k != col)
			{
				return false;
			}
		}
	}//这是检查同一3*3小格中的重复
	//经过三个判断如果可以放那么则返回真
	return true;
}

Step.2 利用flowback回溯

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
void flowback(int now)
{
	if(now == 81)
	{
		print_map();
		return;
	}//输出
	int row = now / 9;
	int col = now % 9;
	if(!vis[row][col])
	{
		for(int i = 1; i <= 9; ++i)
		{
			vis[row][col]=true;
			maap[row][col] = i;//赋值
			if(judge(now))
			{//可以放
				flowback(now+1);//进入下一层
			}
		}
		vis[row][col]=false;//回溯
	}
	else
	{
		flowback(now+1);
	}
}

Step.3 轻松愉快的输出print_map

1
2
3
4
5
6
7
8
9
10
11
void print_map()
{
		for(int i = 0; i < 9; ++i)
		{
			for(int j =  0; j < 9; ++j)
			{
				cout<<maap[i][j]<<" ";
			}
			cout<<endl;
		}
}

其实就是很简单的回溯，判重也超级简单，只是有可能跑得比较慢鹅已……

最后还是良心的上个全代码，也请巨佬们在时间复杂度优化上加以指导！

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
int maap[9][9];
bool vis[9][9];
bool judge(int now)
{
	int row = now / 9;
	//当前行
	int col = now % 9;
	//当前列
	int j;
	//同一行
	for(j = 0; j < 9; ++j)
	{
		if(maap[row][j] == maap[row][col] && j != col)
		{
			return false;
		}
	}
	//同一列
	for(j = 0; j < 9; ++j)
	{
		if(maap[j][col] == maap[row][col] && j != row)
		{
			return false;
		}
	}
	//同一小格
	int tmp_row = row / 3 * 3;
	int tmp_col = col / 3 * 3;
	for(j = tmp_row; j < tmp_row + 3;++j)
	{
		for(int k = tmp_col; k < tmp_row + 3; ++k)
		{
			if(maap[j][k] == maap[row][col] && j != row && k != col)
			{
				return false;
			}
		}
	}
	//经过三个判断如果可以放那么则真的可以了
	return true;
}
void print_map()
{
		for(int i = 0; i < 9; ++i)
		{
			for(int j =  0; j < 9; ++j)
			{
				cout<<maap[i][j]<<" ";
			}
			cout<<endl;
		}
}
void flowback(int now)
{
	if(now == 81)
	{
		print_map();
		return;
	}
	int row = now / 9;
	int col = now % 9;
	if(!vis[row][col])
	{
		for(int i = 1; i <= 9; ++i)
		{
			vis[row][col]=true;
			maap[row][col] = i;//赋值
			if(judge(now))
			{//可以放
				flowback(now+1);//进入下一层
			}
		}
		vis[row][col]=false;//回溯
	}
	else
	{
		flowback(now+1);
	}
}
int main()
{
	for(int i = 0; i < 9; ++i)
	{
		for(int j = 0; j < 9; ++j)
		{
			cin>>maap[i][j];
			if(maap[i][j])
			{
				vis[i][j]=true;
				//有数的地方就不自己放了
			}
		}
	}
	flowback(0);
	//从第0个数开始回溯
	return 0;
}

#2

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define ri register int
using namespace std;
int maap[9][9];
int flg=0;
int num=0;

int read()
{
	int num=0;
	int flg=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')
		{
			flg=-1;
		}
		c=getchar();
	}
	while(isdigit(c))
	{
		num=(num<<1)+(num<<3)+(c^48);
		c=getchar();
	}
	return num*flg;
}

void print_map()
{
	printf("Scenario #%d:\n",++num);
	for(ri i=0;i<9;i++)
	{
		for(ri j=0;j<9;j++)
		{
			printf("%d",maap[i][j]);
		}
		printf("\n");
	}
}
bool judge(int x,int y,int k)
{
	for(ri i=0;i<9;i++)
	{
		if(maap[i][y]==k||maap[x][i]==k)
		{
			return 0;
		}
	}
	int x1=x/3*3;
	int y1=y/3*3;
	for(ri i=x1;i<x1+3;i++)
	{
		for(ri j=y1;j<y1+3;j++)
		{
			if(maap[i][j]==k)
			{
				return 0;
			}
		}
	}
	return 1;
}
void dfs(int x,int y)
{
	if(x==9&&y==0)
	{
		print_map();
		flg=1;
		return ;
	}
	if(maap[x][y]!=0)
	{
		if(y==8)
		{
			dfs(x+1,0);
		}
		else
		{
			dfs(x,y+1);
		}
	}
	else
	{
		for(ri i=1;i<=9;i++)
	    {
		    if(judge(x,y,i)!=0)
		    {
		    	maap[x][y]=i;
		    	if(y==8)
		    	{
		    		dfs(x+1,0);
				}
				else
				{
					dfs(x,y+1);
				}
				if(flg==1)
				return ;
				maap[x][y]=0;
			}
	    }
	}
}
int main()
{
	int t=read();
	while(t--)
	{
		memset(maap,0,sizeof(maap));
		for(ri i=0;i<9;i++)
		{
			for(ri j=0;j<9;j++)
			{
				scanf("%1d",&maap[i][j]);
			}
		}
		flg=0;//判断是否继续dfs
		dfs(0,0);
	}
	return 0;
}
/*
2
000000000
817965430
652743190
175439820
308102950
294856370
581697240
903504610
746321580

781654392
962837154
543219786
439182675
158976423
627543918
316728549
895461237
274395861
*/

撒花✿✿ヽ(°▽°)ノ✿