在本蒟的不断探索发现下，我意识到DFS似乎可以用来做数独……
于是乎就上手操作了一下，然后就做出来了？
其实思路很简单，就是简单的DFS
(废话，本蒟蒻都想出来了能不简单吗)
就是模仿人填数独的过程，只是更加无脑。
一个个试起走，放不了就回溯，直到解出答案，输出
真的就只有那么简单了，秒杀人脑啊有没有
上干货！
Step.1 通过judge判断是否合法
1 bool judge(int now)
2 {
3 int row = now / 9;
4 //当前行
5 int col = now % 9;
6 //当前列
7 int j;
8 for(j = 0; j < 9; ++j)
9 {
10 if(maap[row][j] == maap[row][col] && j != col)
11 {
12 return false;
13 }
14 }//这是检查同一行中的重复
15 for(j = 0; j < 9; ++j)
16 {
17 if(maap[j][col] == maap[row][col] && j != row)
18 {
19 return false;
20 }
21 }//这是检查同一列中的重复
22 int tmp_row = row / 3 * 3;
23 int tmp_col = col / 3 * 3;
24 for(j = tmp_row; j < tmp_row + 3;++j)
25 {
26 for(int k = tmp_col; k < tmp_row + 3; ++k)
27 {
28 if(maap[j][k] == maap[row][col] && j != row && k != col)
29 {
30 return false;
31 }
32 }
33 }//这是检查同一3*3小格中的重复
34 //经过三个判断如果可以放那么则返回真
35 return true;
36 }
Step.2 利用flowback回溯
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
void print_map()
{
for(int i = 0; i < 9; ++i)
{
for(int j = 0; j < 9; ++j)
{
cout<<maap[i][j]<<" ";
}
cout<<endl;
}
}
其实就是很简单的回溯，判重也超级简单，只是有可能跑得比较慢鹅已……
最后还是良心的上个全代码，也请巨佬们在时间复杂度优化上加以指导！
#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;
}
撒花✿✿ヽ(°▽°)ノ✿