题目描述

小明最近迷上了数独游戏，他想借助程序完成这件事情，请你帮帮他。

数独游戏：在9X9的矩阵中填入1-9的数字，使得每行每列每个宫（3X3的小区域）中每个数字只出现一次。

输入

• 输入9行9列的数独矩阵，0表示待填

输出

• 输出9行9列的数独矩阵，表示解（数据保证解唯一）

样例

输入数据 1

0 0 2 0 7 8 4 3 1
0 0 8 6 0 0 9 0 0
0 0 0 5 0 1 0 0 0
0 2 0 0 0 3 5 0 6
0 3 6 8 5 0 0 0 7
1 0 0 4 9 6 0 2 0
0 8 3 2 4 5 6 0 9
6 9 4 1 0 7 0 0 2
0 5 1 3 0 9 0 8 4

输出数据 1

5 6 2 9 7 8 4 3 1 
3 1 8 6 2 4 9 7 5 
9 4 7 5 3 1 2 6 8 
8 2 9 7 1 3 5 4 6 
4 3 6 8 5 2 1 9 7 
1 7 5 4 9 6 8 2 3 
7 8 3 2 4 5 6 1 9 
6 9 4 1 8 7 3 5 2 
2 5 1 3 6 9 7 8 4

这道题的样例很复杂，不会数独的都康不懂，如果不会做数独题的话不妨康康这个戳我 

好了，大家都会做数独了叭，让我们来看这道题，根据数独的解法不难看出我们可以用深搜来搞这道题（

这道题和一般模板不同，它要修改的地方很多，毕竟自己解都很难，何况写个代码让计算机来解捏，不过大体上和dfs模板没有差多少

直接上代码，大家自行观看（）

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int n = 9;
pair<int, int> xy[100];
int m;
void dfs(int x, int y, int u) {if(u == m + 1) {for(int i = 1; i <= n; i ++) {for(int j = 1; j <= n; j ++) {cout << a[i][j] << ' ';} cout << endl;}exit(0);}int l, r;if(x <= 3) l = 1;else if(x <= 6) l = 4;else l = 7;if(y <= 3) r = 1;else if(y <= 6) r = 4;else r = 7;int st1[10], st2[10], st3[10];for(int i = 1; i <= n; i ++) st1[i] = st2[i] = st3[i] = 0;for(int i = l; i <= l + 2; i ++) {for(int j = r; j <= r + 2; j ++) {st1[a[i][j]] = 1;}} for(int i = 1; i <= n; i ++) st2[a[x][i]] = 1;for(int i = 1; i <= n; i ++) st3[a[i][y]] = 1;for(int i = 1; i <= n; i ++) {if(!st1[i] && !st2[i] && !st3[i]) {st1[i] = 1;st2[i] = 1;st3[i] = 1;a[x][y] = i;dfs(xy[u + 1].first, xy[u + 1].second, u + 1);st1[i] = 0;st2[i] = 0;st3[i] = 0;a[x][y] = 0;}}
}
int main() {for(int i = 1; i <= n; i ++) {for(int j = 1; j <= n; j ++) {cin >> a[i][j];if(a[i][j] == 0) xy[++m] = {i, j}; }}int x = xy[1].first, y = xy[1].second;dfs(x, y, 1);return 0;
}

大概就是这样的搜索，结束撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。