数独(1)
描述
为了找到百年沉睡的原因,寻回百年前与公主一起的记忆碎片,明白自己是谁,林克必须激活成功教程数独谜题。
林克需要在限定时间内,把9×9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
林克需要寻回失去的记忆碎片,你,作为林克的朋友,需要帮忙林克寻回9×9棋盘中失去的数字。
或许有一天,林克也能帮助你,寻回关于你是谁,你从哪里来的记忆碎片。
这是数独试炼I(解密成功可以解锁林克前25%的记忆碎片)
输入
输入为9×9的数据。一共9行,每行有9个数字。
数字为0表示对应的数字盘为空。
输出
对于每个测试用例,程序应以与输入数据相同的格式打印解决方案(9×9)。
空单元格必须根据规则进行填充。
如果解决方案不是唯一的,则程序可以打印其中任何一种。
样例
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
难度
高,深搜
解法
数独数据结构设计如上
Sudu[ N ] [ N ] 存放数独棋盘中的数字,0代表还没有填
row[ N ] [ N ],col [ N ] [ N ],grid[ N ] [ N ] 为三个标志位,用于判断数字是否重复摆放。例如上述图中(0,0)号位置为1,它的所在行为0,所在列为0,所在grid为0 (把每个3*3的九宫格看成一个grid)按行至列排序为 0-8,转换方法为:
第r行第c列的元素在 第k个grid里(k = (r/3) * 3 + c/3)
紧接着进行常规法深搜。
代码
#include<bits/stdc++.h>
using namespace std;
const int N9 = 9; //递归9层
const int N = 10;
int Sudu[N][N];
bool row[N][N],col[N][N],grid[N][N];
//每一行每一列扫描
bool dfs(int r,int c){
if(r==N9) return true; //[0-8]
bool flag = false; //是否找到可行解
if(Sudu[r][c]){
//Sudu中数字不为1
if(c==8) flag = dfs(r+1,0); //搜索下一行
else flag = dfs(r,c+1);
return flag;
}
//每一个3*3的grid,寻找第k个grid
int k = (r/3)*3 + c/3;
for(int i=1;i<=9;i++){
//尝试在Sudu[r][c]摆下1-9的数字
if(!row[r][i] && !col[c][i] && !grid[k][i]){
//如果该数字还没有被摆放
row[r][i] = true; col[c][i] = true; grid[k][i] = true; //每行每列每grid标志
Sudu[r][c] = i; //从1-9开始尝试摆下数字
if(c==8) flag = dfs(r+1,0); //搜索下一行
else flag = dfs(r,c+1);
if(flag) return true;
//还原状态
Sudu[r][c]=0;
row[r][i] = false; col[c][i] = false; grid[k][i] = false;
}
}
return false;
}
int main()
{
//输入输出加速
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
memset(row,false,sizeof(row));
memset(col,false,sizeof(col));
memset(grid,false,sizeof(grid));
for(int i=0;i<N9;i++)
for(int j=0;j<N9;j++){
char ch;
cin>>ch;
Sudu[i][j] = ch - '0';
if(Sudu[i][j]){
row[i][Sudu[i][j]] = true; //第i行中Sudu中的数字已经被使用
col[j][Sudu[i][j]] = true; //第j行中Sudu中的数字已经被使用
grid[(i/3)*3 + j/3][Sudu[i][j]] = true; //第grid方块中Sudu中的数字已经被使用
}
}
dfs(0,0);
cout<<"解为:"<<endl;
for(int i=0;i<N9;i++){
for(int j=0;j<N9;j++)
cout<<Sudu[i][j];
cout<<endl;
}
}
今天的文章算法实践:数独(1)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/11447.html