Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【POJ - 2676】Sudoku(数独 dfs+回溯)

Sky丨Star 2019-07-16 19:15:00 阅读数:81 评论数:0 点赞数:0 收藏数:0

-->Sudoku

直接中文

Descriptions:

Sudoku对数独非常感兴趣,今天他在书上看到了几道数独题: 
给定一个由3*3的方块分割而成的9*9的表格(如图),其中一些表格填有1-9的数字,其余的则为空白(数字0为空白)。请在空白表格中填入数字1-9使得9*9表格的每行、每列、每个3*3块内无重复数字。 

Input

第一行输入一个整数T,表示样例数量。对于每个样例, 一共9行, 表示数独表格的每一行。接下来每一行输入一个字符串表示数独表格的每一行的9个数字。数独表格中空白用数字0表示。

Output

对于每组样例,输出完整的数独表格,即数独表格的每一个空白都按规定填满数字。如果答案不唯一,输出任何一个答案就行。

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

提示可能会有多组解,输出其中一种即可。

题目链接:

https://vjudge.net/problem/POJ-2676

 

1~9 一个一个枚举

dfs试探,失败则回溯

用三个数组进行标记每行、每列、每个子网格已用的数字,用于剪枝

bool row[10][10];    //row[i][x]  标记在第i行中数字x是否出现了

bool col[10][10];    //col[j][y]  标记在第j列中数字y是否出现了

bool grid[10][10];   //grid[k][x] 标记在第k个3*3子格中数字z是否出现了

row 和 col的标记比较好处理,关键是找出grid子网格的序号与 行i列j的关系

即要知道第i行j列的数字是属于哪个子网格的

 

首先我们假设子网格的序号如下编排:

 

由于1<=i、j<=9,我们有: (其中“/”是C++中对整数的除法)

 

令a= i/3 , b= j/3  ,根据九宫格的 行列 与 子网格 的 关系,我们有:

 

不难发现 3a+b=k

即 3*(i/3)+j/3=k

 

又我在程序中使用的数组下标为 1~9,grid编号也为1~9

因此上面的关系式可变形为 3*((i-1)/3)+(j-1)/3+1=k
以上论述转自https://blog.csdn.net/lyy289065406/article/details/6647977

AC代码:

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 15
using namespace std;
int result;
int T,h,w;
int mp[Maxn][Maxn];//地图
bool row[Maxn][Maxn];//row[i][x] 标记在第i行中数字x是否出现了
bool col[Maxn][Maxn];//col[j][y] 标记在第j列中数字y是否出现了
bool grid[Maxn][Maxn];//grid[k][x] 标记在第k个3*3子格中数字z是否出现了
int dfs(int x,int y)
{
if(x==)
return ;
int f=;
if(mp[x][y])
{
if(y==)
f=dfs(x+,);
else
f=dfs(x,y+);
if(f)//回溯
return ;
else
return ;
}
else
{
int k=*((x-)/)+(y-)/+;
for(int i=; i<=; i++)//枚举1~9填空
if(!row[x][i]&&!col[y][i]&&!grid[k][i])
{
mp[x][y]=i;
row[x][i]=;
col[y][i]=;
grid[k][i]=;
if(y==)
f=dfs(x+,);
else
f=dfs(x,y+);
if(!f)//回溯,继续枚举
 {
mp[x][y]=;
row[x][i]=;
col[y][i]=;
grid[k][i]=;
}
else
return ;
}
}
return ;
}
int main()
{
int h=w=;
cin>>T;
while(T--)
{
MEM(row,);
MEM(col,);
MEM(grid,);
for(int i=; i<=h; i++)
for(int j=; j<=w; j++)
{
char ch;//注意,这里一定要用char类型,不然读不进去
cin>>ch;
mp[i][j]=ch-'';
if(mp[i][j])
{
int k=*((i-)/)+(j-)/+;
row[i][mp[i][j]]=;
col[j][mp[i][j]]=;
grid[k][mp[i][j]]=;
}
}
//从(1,1)开始搜索
dfs(,);
//输出
for(int i=; i<=h; i++)
{
for(int j=; j<=w; j++)
cout<<mp[i][j];
cout<<endl;
}
}
}

 

版权声明
本文为[Sky丨Star]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sky-stars/p/11196903.html