Sudoku Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1271 Accepted Submission(s): 352
Problem Description
自从2006年3月10日至11日的首届数独世界锦标赛以后,数独这项游戏越来越受到人们的喜爱和重视。
据说,在2008北京奥运会上,会将数独列为一个单独的项目进行比赛,冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。
所以全球人民前仆后继,为了奖品日夜训练茶饭不思。当然也包括初学者linle,不过他太笨了又没有多少耐性,只能做做最最基本的数独题,不过他还是想得到那些奖品,你能帮帮他吗?你只要把答案告诉他就可以,不用教他是怎么做的。
数独游戏的规则是这样的:在一个9x9的方格中,你需要把数字1-9填写到空格当中,并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证,空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题,大家可以仔细观察一下,在这里面每行、每列,以及每个3x3的方格都包含1-9这九个数字。
Input
本题包含多组测试,每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵,同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数,问号(?)表示需要你填的数。
Output
对于每组测试,请输出它的解,同一行相邻的两个数用一个空格分开。两组解之间要一个空行。
对于每组测试数据保证它有且只有一个解。
Sample Input
7 1 2 ? 6 ? 3 5 8
? 6 5 2 ? 7 1 ? 4
? ? 8 5 1 3 6 7 2
9 2 4 ? 5 6 ? 3 7
5 ? 6 ? ? ? 2 4 1
1 ? 3 7 2 ? 9 ? 5
? ? 1 9 7 5 4 8 6
6 ? 7 8 3 ? 5 1 9
8 5 9 ? 4 ? ? 2 3
Sample Output
7 1 2 4 6 9 3 5 8
3 6 5 2 8 7 1 9 4
4 9 8 5 1 3 6 7 2
9 2 4 1 5 6 8 3 7
5 7 6 3 9 8 2 4 1
1 8 3 7 2 4 9 6 5
2 3 1 9 7 5 4 8 6
6 4 7 8 3 2 5 1 9
8 5 9 6 4 1 7 2 3
继续dfs,这题是数独游戏,要求把问号变成合适数字,使之符合题意: --- 在一个9x9的方格中,你需要把数字1-9填写到空格当中,并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证,空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题,大家可以仔细观察一下,在这里面每行、每列,以及每个3x3的方格都包含1-9这九个数字。---
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1426
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
char a[15][15];
int b[15][15], num;
bool flag;
struct point //表示"?"的坐标
{
int x;
int y;
}p[85];
void init() //初始化函数
{
flag = false;
num = 0;
}
bool search(int x, int y, int z) //判断z数是否可以满足在(x,y)
{
bool tar = true;
int i, j, xx, yy, xxx, yyy;
for(i = 0; i < 9; i++) //判断竖方向是否有相同
{
if(i == x) continue;
if(b[i][y] == z) return false;
}
for(j = 0; j < 9; j++) //判断横方向是否有相同
{
if(j == y) continue;
if(b[x][j] == z) return false;
}
xx = x/3*3; yy = y/3*3; //计算属于哪个9宫格
xxx = xx+3; yyy = yy+3;
for(i = xx; i < xxx; i++) //判断该点所在9宫格是否有相同
{
for(j = yy; j < yyy; j++)
{
if(i == x && j == y) continue;
if(b[i][j] == z) return false;
}
}
return tar; //都符合要求,z满足条件
}
void dfs(int nn) //nn参数代表第几个'?'
{
int k;
if(flag) return; //已找到,直接返回
if(nn == num) //若数量已经满足,成功找到全部
{
flag = true;
return;
}
for(k = 1; k <= 9; k++)
{
if(search(p[nn].x, p[nn].y, k)) //判断k能否放入(x,y)内
{
b[p[nn].x][p[nn].y] = k; //赋上该值
dfs(nn+1); //dfs 深搜!!!
if(flag) return; //已找到,直接返回
b[p[nn].x][p[nn].y] = 0; //若找不到,该数变回0,继续找
}
}
}
int main()
{
int i, j, zz = 0;
char ch[2];
while(scanf("%s", ch) != EOF) //输入是一个大问题,输入字符串来输入也是可以
{
init(); //记得初始化
if(ch[0] != '?')
b[0][0] = ch[0] - '0';
else
{
b[0][0] = 0;
p[num].x = 0; //记录x坐标
p[num].y = 0; //记录y坐标
num++; //'?'数量+1
}
//输入如果是'?',则b[][]变成0,否则变成ch[0]-'0'
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
{
if(i == 0 && j == 0) continue;
scanf("%s", ch);
if(ch[0] != '?')
b[i][j] = ch[0] - '0';
else
{
b[i][j] = 0;
p[num].x = i; //记录x坐标
p[num].y = j; //记录y坐标
num++; //'?'数量+1
}
}
}
dfs(0); //开始dfs深搜
if(zz++) printf("\n");
for(i = 0; i < 9; i++)
{
printf("%d", b[i][0]);
for(j = 1; j < 9; j++)
{
printf(" %d", b[i][j]);
}
printf("\n");
}
}
return 0;
}
分享到:
相关推荐
搜索 dfs 解题代码 hdu1241
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
自己做的HDU ACM已经AC的题目
HDU图论题目分类