2924 数独挑战

2018-06-17 22:40:50来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Leetcode: 11. Container With Most Water

下一篇:bzoj2588 -- 树链剖分+主席树