2924 数独挑战

2924 数独挑战

 时间限制: 1 s

 空间限制: 1000 KB

 题目等级 : 钻石 Diamond

题解

 查看运行结果

题目描述 Description

“芬兰数学家因卡拉,花费3个月时间设计出了世界上迄今难度最大的数独游戏,而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”这是英国《每日邮报》2012年6月30日的一篇报道。这个号称“世界最难数独”的“超级游戏”,却被扬州一位69岁的农民花三天时间解了出来。

看到这个新闻后,我激动不已,证明我们OI的实力的机会来了,我们虽然不是思考能力最快、头脑最聪明的人,但是我们可以保证在1s之内解题。

好了废话不多说了……

数独是一种填数字游戏,英文名叫Sudoku,起源于瑞士,上世纪70年代由美国一家数学逻辑游戏杂志首先发表,名为Number Place,后在日本流行,1984年将Sudoku命名为数独,即“独立的数字”的省略,解释为每个方格都填上一个个位数。2004年,曾任中国香港高等法院法官的高乐德(Wayne Gould)把这款游戏带到英国,成为英国流行的数学智力拼图游戏。

玩家需要根据9×9盘面上的已知数字,推理出所有剩余位置(数据表示为数字0)的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。

现在给你一个数独,请你解答出来。每个数独保证有解且只有一个。

输入描述 Input Description

9行9列。

每个数字用空格隔开。0代表要填的数

行末没有空格,末尾没有回车。

输出描述 Output Description

输出答案。

排成9行9列。

行末没有空格,结尾可以有回车。

样例输入 Sample Input

2 0 0 0 1 0 8 9 0 0 0 7 0 0 0 0 0 0 0 0 0 9 0 0 0 0 7 0 6 0 0 0 1 3 0 0 0 9 0 7 3 4 0 8 0 0 0 3 6 0 0 0 5 0 6 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 5 9 0 8 0 0 0 3

样例输出 Sample Output

2 4 5 3 1 7 8 9 6 9 1 7 2 6 8 5 3 4 3 8 6 9 4 5 2 1 7 4 6 2 8 5 1 3 7 9 5 9 1 7 3 4 6 8 2 8 7 3 6 2 9 4 5 1 6 3 8 1 7 2 9 4 5 7 2 4 5 9 3 1 6 8 1 5 9 4 8 6 7 2 3

数据范围及提示 Data Size & Hint

保证有解,每个数独都由<a href="http://oubk.com/">http://oubk.com</a>数独网提供。

其中数据hard1.in为芬兰数学家提供。

做这个题其实是有很多小技巧的:

1.很多人不会判重同一个方格中的元素,这里我定义了一个所有方格中元素都相同的常量数组,这样在判重的时候只要遇到group数组中的元素一样的话就说名在一个方格中

2.有人搜索搜不出来,很可能是因为你搜索的顺序不对,这个题必修按行搜索或者按列搜索!

3.注意好刚开始非零元素的初始化

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 int map[10][10];
 7 int vis[10][10];
 8 int hang[10][10];
 9 int lie[10][10];
10 int group[10][10]=
11 {
12     0,0,0,0,0,0,0,0,0,0,
13     0,1,1,1,2,2,2,3,3,3,
14     0,1,1,1,2,2,2,3,3,3,
15     0,1,1,1,2,2,2,3,3,3,
16     0,4,4,4,5,5,5,6,6,6,
17     0,4,4,4,5,5,5,6,6,6,
18     0,4,4,4,5,5,5,6,6,6,
19     0,7,7,7,8,8,8,9,9,9,
20     0,7,7,7,8,8,8,9,9,9,
21     0,7,7,7,8,8,8,9,9,9,    
22 };
23 int group_vis[10][10];
24 void dfs(int x,int y)
25 {
26     if(x==10)
27     {
28         for(int i=1;i<=9;i++)
29         {
30             for(int j=1;j<=9;j++)
31                 printf("%d ",map[i][j]);
32             printf("\n");
33         }
34         exit(0);}
35     
36     int wx=x;int wy=y+1;
37     if(wy==10)
38     {wy=1;
39     wx=x+1;}
40     
41     if(map[x][y]!=0)dfs(wx,wy);
42     else
43     {
44         for(int j=1;j<=9;j++)
45         {
46                 if(hang[x][j]==0&&lie[y][j]==0&&group_vis[group[x][y]][j]==0)
47                 {
48                     hang[x][j]=1;lie[y][j]=1;group_vis[group[x][y]][j]=1;
49                     map[x][y]=j;
50                     dfs(wx,wy);
51                     map[x][y]=0;
52                     hang[x][j]=0;lie[y][j]=0;group_vis[group[x][y]][j]=0;
53                 }
54         }
55     }
56 }
57 int main()
58 {
59     for(int i=1;i<=9;i++)
60         for(int j=1;j<=9;j++)
61         {
62             scanf("%d",&map[i][j]);
63             if(map[i][j]!=0){hang[i][map[i][j]]=1;lie[j][map[i][j]]=1;group_vis[group[i][j]][map[i][j]]=1;}
64         }
65     dfs(1,1);
66     return 0;
67 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

哲思片段 | 设计中的变与不变

古希腊哲学家巴门尼德认为:“人的思想和言语都有一个载体,如果你在这一时间和另外一个时间想到或者谈到同样一件东西,那就说明这件东西在这段时间内没有变化,如有变化的...

3957
来自专栏NetCore

关于某道C#上机题的OO

前两天在园子里,有人出了一道《关于一道C#上机题的一点想法》,大概的意思呢是利用OO的思想来进行编程,接着又有一位朋友,也写了自己的答案,此朋友非常厉害,从类图...

2266
来自专栏JetpropelledSnake

Python Web学习笔记之递归和迭代的区别

电影故事例证: 迭代——《明日边缘》 递归——《盗梦空间》 迭代是更新变量的旧值。递归是在函数内部调用自身。 迭代是将输出做为输入,再次进行处理。比如将摄像头对...

32512
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3624
来自专栏趣学算法

数据结构学习秘籍

网络上太多的同学吐槽被虐,如滔滔江水连绵不绝,数据结构太难了!真的很难吗?其实数据结构只是讲了三种:线性结构、树、图。到底难在哪里呢?通过调查了解大概有四个原因...

1192
来自专栏noteless

抽象工厂模式 创建型 设计模式(四)

所有的ConcreteCreator的返回类型都是Product,因为抽象工厂角色Creator就是返回Product 

592
来自专栏数据结构与算法

P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述 汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。 有一些航班将...

2788
来自专栏SnailTyan

枚举——生理周期

1. 枚举 枚举是基于逐个尝试答案的一种问题求解策略。 2. 生理周期 问题描述 人有体力、情商、智商的高峰日子,它们分别每隔23天、28天和33天出现一次...

2020
来自专栏阮一峰的网络日志

为什么Lisp语言如此先进?(译文)

上周,《黑客与画家》总算翻译完成,已经交给出版社了。 翻译完这本书,累得像生了一场大病。把书稿交出去的时候,心里空荡荡的,也不知道自己得到了什么,失去了什么。 ...

2996
来自专栏web前端教室

重学javascript 红皮高程(5)

JS这项技术,细节到位了,就会一通百通。经常在网上看到说学一个框架,最有效的办法是去看它的源码。但我经常看不懂,为什么呢?因为我基础不好,不明白源码中的一些写法...

2055

扫码关注云+社区

领取腾讯云代金券