九宫格数独（深搜剪枝）

本文主要是介绍九宫格数独（深搜剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

在提瓦特大陆上，你作为一名旅行者发现了一个古老的神庙，里面有一块被称为“天地平衡板”的神秘石碑。为了解开石碑上的封印，你需要通过正确放置元素之力来恢复它的平衡。

天地平衡板是一个9x9的方格，每个方格可以填入代表不同元素力量的数字1-9。每种力量在每一行、每一列以及每一个由粗实线分隔的3x3宫格中必须恰好出现一次，这样才能保持元素之间的平衡。

部分格子中已经注入了元素力量（数字已知），而空白格用 '.' 表示，你的任务是找出如何在空白格中分配剩余的元素力量。

输入

一个表示天地平衡板当前状态的九宫格，每个数字对应不同的元素力量。

输出

完整的天地平衡板，每行9个字符，代表通过正确分配所有元素力量后的解决方案。

输入样例 1 

...1...57
..8.....4
4..37..2.
.......1.
...2.85..
...95....
32.7..64.
91..6..7.
..64.....

输出样例1

692184357
738592164
451376829
589637412
167248593
243951786
325719648
914863275
876425931（注意最后一行有一行空行）

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=9;
int g[N][N];
bool st_row[N][N+1],st_col[N][N+1],st_block[3][3][N+1];
bool dfs(int x,int y)
{if(y==9)x++,y=0;if(x==9){for(int i=0;i<9;i++){for(int j=0;j<9;j++)cout<<g[i][j];cout<<endl;}return true;}if(g[x][y]!=0)return dfs(x,y+1);for(int t=1;t<=9;t++){if(st_row[x][t]==0&&st_col[y][t]==0&&st_block[x/3][y/3][t]==0){st_row[x][t]=1,st_col[y][t]=1,st_block[x/3][y/3][t]=1;g[x][y]=t;if(dfs(x,y+1))return true;g[x][y]=0;st_row[x][t]=0,st_col[y][t]=0,st_block[x/3][y/3][t]=0;}}return false;
}
int main()
{std::ios::sync_with_stdio(false);//关闭输入输出缓冲，提升效率std::cin.tie(NULL),std::cout.tie(NULL);//解除cin和cout的默认绑定，降低IO的负担提升效率memset(st_row,0,sizeof(st_row));memset(st_col,0,sizeof(st_col));memset(st_block,0,sizeof(st_block));for(int i=0;i<9;i++)for(int j=0;j<9;j++){char ch;cin>>ch;int t=0;if(ch!='.')t=ch-'0';g[i][j]=t;if(t!=0)st_row[i][t]=st_col[j][t]=st_block[i/3][j/3][t]=true;//i/3,j/3正好对应i，j所在的三宫格}dfs(0,0);return 0;
}

这篇关于九宫格数独（深搜剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---