nyoj--722-数独

心已赠人 2022-05-29 05:57 156阅读 0赞

## 数独 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 4

描述

数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个3\*3宫内的数字均含1-9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

有一天hrdv碰到了一道号称是世界上最难的数独的题目，作为一名合格的程序员，哪能随随便便向困难低头，于是他决定编个程序来解决它。。

![20130604182400_52995.jpg][]

输入

第一行有一个数n（0< n <100），表示有n组测试数据，每组测试数据是由一个9\*9的九宫格构成，0表示对应的格子为空

输出

输出一个9\*9的九宫格，为这个数独的答案

样例输入

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

样例输出

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

思路：暴力深搜就可以水过，注意有三个判断条件，1,所在的行。2,所在的列。3,所在的宫格。其中宫格这个不太好想。其他的和            普通深搜差不多，细节上的东西在代码里面注释。

代码：

C++ Code

<table style="font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;"> 
 #include&nbsp;&lt;stdio.h&gt; 
 
 #include&nbsp;&lt;string.h&gt; 
 
 int&nbsp;num[ 
 10][ 
 10];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///存储整个方格 
 int&nbsp;r[ 
 10][ 
 10];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///存储行的情况 
 int&nbsp;c[ 
 10][ 
 10];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///存储列的情况 
 int&nbsp;tab[ 
 3][ 
 3][ 
 10];&nbsp;&nbsp;&nbsp;&nbsp; 
 ///存储3*3宫格的情况 
 int&nbsp;n,&nbsp;flag; 
 
 void&nbsp;dfs( 
 int&nbsp;n) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x&nbsp;=&nbsp;n&nbsp;/&nbsp; 
 9;&nbsp;&nbsp; 
 ///获取行 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;y&nbsp;=&nbsp;n&nbsp;%&nbsp; 
 9;&nbsp;&nbsp; 
 ///获取列 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(flag)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///优化语句 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return; 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(n&nbsp;==&nbsp; 
 81)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///说明已经全部填完 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp; 
 9;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 0;&nbsp;j&nbsp;&lt;&nbsp; 
 9;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d&nbsp;",&nbsp;num[i][j]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "\n"); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(num[x][y]&nbsp;==&nbsp; 
 0)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///为零表示还没有填数，可以考虑 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;k&nbsp;=&nbsp; 
 1;&nbsp;k&nbsp;&lt;=&nbsp; 
 9;&nbsp;k++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!(r[x][k]&nbsp;||&nbsp;c[y][k]&nbsp;||&nbsp;tab[x&nbsp;/&nbsp; 
 3][y&nbsp;/&nbsp; 
 3][k]))&nbsp; 
 ///上面说得三个判断条件 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[x][y]&nbsp;=&nbsp;k;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///填数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r[x][k]&nbsp;=&nbsp;c[y][k]&nbsp;=&nbsp;tab[x&nbsp;/&nbsp; 
 3][y&nbsp;/&nbsp; 
 3][k]&nbsp;=&nbsp; 
 1;&nbsp; 
 ///对所在行，列，宫格进行标记 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs(n&nbsp;+&nbsp; 
 1); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[x][y]&nbsp;=&nbsp; 
 0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///回溯还原标记 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r[x][k]&nbsp;=&nbsp;c[y][k]&nbsp;=&nbsp;tab[x&nbsp;/&nbsp; 
 3][y&nbsp;/&nbsp; 
 3][k]&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs(n&nbsp;+&nbsp; 
 1);&nbsp;&nbsp;&nbsp; 
 ///&nbsp;如果已经填的有数，跳到下一个 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(n--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(r,&nbsp; 
 0,&nbsp; 
 sizeof(r)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(c,&nbsp; 
 0,&nbsp; 
 sizeof(c)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(tab,&nbsp; 
 0,&nbsp; 
 sizeof(tab)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp; 
 9;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 0;&nbsp;j&nbsp;&lt;&nbsp; 
 9;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;num[i][j]); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t&nbsp;=&nbsp;num[i][j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r[i][t]&nbsp;=&nbsp; 
 1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///表示第i行已经出现这个数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c[j][t]&nbsp;=&nbsp; 
 1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///表示第j列已经出现这个数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tab[i&nbsp;/&nbsp; 
 3][j&nbsp;/&nbsp; 
 3][t]&nbsp;=&nbsp; 
 1;&nbsp; 
 ///表示这个宫格已经出现了这个数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs( 
 0); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div></td> 
 </tr> 
 </tbody> 
</table>

[20130604182400_52995.jpg]: http://acm.nyist.edu.cn/JudgeOnline/admin/kind/attached/20130604182400_52995.jpg