数独
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
-
数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个3*3宫内的数字均含1-9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。
有一天hrdv碰到了一道号称是世界上最难的数独的题目，作为一名合格的程序员，哪能随随便便向困难低头，于是他决定编个程序来解决它。。
- 输入
- 第一行有一个数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
DFS暴搜
#include
<iostream>02.using namespace std;03. 04.int num[9][9];05.//{06.//
{0,0,5,3,0,0,0,0,0},07.//
{8,0,0,0,0,0,0,2,0},08.//
{0,7,0,0,1,0,5,0,0},09.//
{4,0,0,0,0,5,3,0,0},10.//
{0,1,0,0,7,0,0,0,6},11.//
{0,0,3,2,0,0,0,8,0},12.//
{0,6,0,5,0,0,0,0,9},13.//
{0,0,4,0,0,0,0,3,0},14.//
{0,0,0,0,0,9,7,0,0}15.//};16. 17.bool Check(int x,int y,int k)18.{19.for(int i=0;i<9;i++)20.if(num[i][y]==k)return false;21.for(int j=0;j<9;j++)22.if(num[x][j]==k)return false;23.int sx=(x/3)*3;24.int sy=(y/3)*3;25.for(int i=sx;i<sx+3;i++)26.for(int j=sy;j<sy+3;j++)27.if(num[i][j]==k)return false;28.return true;29.}30. 31.bool Solve(int x,int y)32.{33.if(num[x][y])34.{35.if(y+1<9)36.{37.if(Solve(x,y+1))38.return true;39.}40.else if(x+1<9)41.{42.if(Solve(x+1,0))43.return true;44.}45.else46.return true;47.}48.else49.{50.for(int k=1;k<=9;k++)51.{52.if(Check(x,y,k))53.{54.num[x][y]=k;55.if(y+1<9)56.{57.if(Solve(x,y+1))58.return true;59.}60.else if(x+1<9)61.{62.if(Solve(x+1,0))63.return true;64.}65.else66.return true;67.num[x][y]=0;68.}69.}70.}71.return false;72.}73. 74.int main()75.{76.int n;77.cin>>n;78.while(n--)79.{80.for(int i=0;i<9;i++)81.for(int j=0;j<9;j++)82.cin>>num[i][j];83.Solve(0,0);84.for(int i=0;i<9;i++)85.for(int j=0;j<9;j++)86.cout<<num[i][j]<<(j==8?'\n':'
');87.}88.return 0;89.}