开发者社区> 华山青竹> 正文

POJ 2676 Sudoku (数独 DFS)

简介: Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 14368   Accepted: 7102   Special Judge   Description Sudoku is a very simple task.
+关注继续查看
 
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 14368   Accepted: 7102   Special Judge

 

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. 

Input

The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.

Output

For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

Source

 
http://bailian.openjudge.cn/practice/2982/
 
题目大意:就是数独咯,让你求解数独游戏,9乘9的矩阵要求每行每列和9个3*3的子矩阵内都出现数字1-9
 
题目分析:9乘9的矩阵,从第一个位置一直搜到最后一个位置,若当前位置有数字搜下一位置,否则枚举1-9并判断,
判断时当前行r = n/9当前列为c = n%9当前子矩阵的第一个元素位置为r / 3 * 3,c / 3 * 3
 1 #include <cstdio>  
 2 char s[10];  
 3 int num[9][9];  
 4 bool flag;  
 5   
 6 bool ok(int n, int cur)   
 7 {  
 8     int r = n / 9;      //当前行  
 9     int c = n % 9;      //当前列  
10     for(int j = 0; j < 9; j++)  //枚举列  
11         if (num[r][j] == cur)   
12             return false;  
13     for(int i = 0; i < 9; i++)  //枚举行  
14         if (num[i][c] == cur)   
15             return false;  
16     //得到当前所在的子矩阵的第一个元素位置  
17     int x = r / 3 * 3;    
18     int y = c / 3 * 3;  
19     //枚举子矩阵中的元素  
20     for(int i = x; i < x + 3; i++)  
21         for(int j = y; j < y + 3; j++)  
22             if (num[i][j] == cur)   
23                 return false;  
24     return true;  
25 }  
26   
27 void DFS(int n)  
28 {  
29     if(n > 80 || flag)   
30     {  
31         flag = true;  
32         return;  
33     }  
34     if(num[n / 9][n % 9])//当前位置有数字直接搜索下一位  
35     {  
36         DFS(n + 1);  
37         if(flag)  
38             return;  
39     }  
40     else  
41     {  
42         for(int cur = 1; cur <= 9; cur++)  //枚举数字  
43         {  
44             if(ok(n, cur)) //若ok则插入  
45             {  
46                 num[n / 9][n % 9] = cur;   
47                 DFS(n + 1);  
48                 if(flag)   
49                     return;  
50                 num[n / 9][n % 9] = 0; //还原  
51             }  
52         }  
53     }  
54 }  
55   
56 int main()  
57 {     
58     int T;  
59     scanf("%d", &T);  
60     while(T--)  
61     {  
62         flag = false;  
63         for(int i = 0; i < 9; i++) //得到数独矩阵  
64         {  
65             scanf("%s", s);  
66             for(int j = 0; j < 9; j++)  
67                 num[i][j] = (s[j] - '0');  
68         }  
69         DFS(0);  //从第一位开始搜  
70         for(int i = 0; i < 9; i++)  
71         {  
72             for(int j = 0; j < 9; j++)  
73                 printf("%d", num[i][j]);  
74             printf("\n");        
75         }  
76     }  
77 }  
View Code

题解来源:http://blog.csdn.net/tc_to_top/article/details/43699047 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19074 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28296 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15762 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20272 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14878 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23541 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22266 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载