大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
题解
剪枝策略：
- 有限分支数较少的节点。
- 排除等价冗余
- 可行性减枝
- 最优性减枝
- 记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N = 9;
char g[N][N];
int col[N],row[N],grid[3][3];
int ones[1 << N];
int Map[1 << N];
int res = 0;
int sum = 0;
string line;
int get(int x,int y){
return ones[row[x] & col[y] & grid[x / 3][y / 3]];
}
int lowbit(int x){
return (x & (-x));
}
void push(int x,int y,int v){
col[y] -= (1 << v);
row[x] -= (1 << v);
grid[x / 3][y / 3] -= (1 << v);
int in = x * 9 + y;
line[in] = '1' + v;
g[x][y] = '1' + v;
}
void back(int x,int y,int v){
col[y] += (1 << v);
row[x] += (1 << v);
grid[x / 3][y / 3] += (1 << v);
int in = x * 9 + y;
line[in] = '.';
g[x][y] = '.';
}
bool dfs(int k){
// cout<<k<<endl;
if(k == sum){
cout<<line<<endl;
return true;
}
int x, y, v = 10;
for(int i = 0;i < N;i ++){
for(int j = 0;j < N;j ++){
if(g[i][j] == '.'){
if(v > get(i,j)){
v = get(i , j);
x = i,y = j;
}
}
}
}
int t = col[y] & row[x] & grid[x / 3][y / 3];
while(t > 0){
int tt = lowbit(t);
t -= tt;
push(x,y,Map[tt]);
if(dfs(k + 1))return true;
back(x,y,Map[tt]);
}
return false;
}
int main(){
for(int i = 0;i < 1 << N;i ++){
for(int j = 0;j < N;j ++){
if((i >> j) & 1)ones[i] ++;
}
}
for(int i = 0;i < N;i ++)Map[1 << i] = i;
while(cin>>line,line != "end"){
for(int i = 0;i < line.size();i ++){
int x = i / N,y = i % N;
g[x][y] = line[i];
}
memset(col,0,sizeof col);
memset(row,0,sizeof row);
memset(grid,0,sizeof grid);
sum = 0;
for(int i = 0;i < N;i ++){
col[i] = (1 << N) - 1;
row[i] = (1 << N) - 1;
grid[i / 3][i % 3] = (1 << N) - 1;
}
for(int i = 0;i < N;i ++){
for(int j = 0;j < N;j ++){
if(g[i][j] != '.'){
int x = g[i][j] - '1';
col[j] -= (1 << x);
row[i] -= (1 << x);
grid[i / 3][j / 3] -= (1 << x);
}else sum ++;
}
}
dfs(0);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168847.html原文链接：https://javaforall.net
