本文主要是介绍TOJ 4972: 数独 4*4 dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
预计的周末天气非常不错，小T和小伙伴在满足的吃完烧烤后，玩起了数独。所谓数独就是在N*N的表格上填补数字，使得每行每列每块上都存在1~N这N个不同的数字。不过这是小T临时找的表格，所以只有4*4的大小。
对于4*4的表格，它的每行上都应该含有1~4四个数字，每列上也含有1~4四个数字。然后将其分为4份2*2的小块，每个小块也含有1~4这4个数字。一个满足要求的数独表格如下所示：
1 2 | 4 3
3 4 | 2 1
一一一一
2 3 | 1 4
4 1 | 3 2
那么问题来了，给你一张没填完的4*4表格，请问你能将它填完吗？
输入
输入第一行包含一个T，代表一共包含T组数据。
每组数据包含四行四列的表格，每个数字之间以空格隔开。其中Aij代表第i行第j列的数字，如果Aij=?则说明该处还没有填上数字。
每组数据之间含有一个空行。
保证Aij∈{1,2,3,4,?}。
输出
每组数据输出占一行。
如果表格可以被填满则输出Yes，否则输出No。
具体格式见样例。
样例输入
3
1 ? ? 3
? ? 2 1
2 3 ? ?
4 ? 3 2
1 ? ? 4
? 1 ? ?
2 ? ? ?
? 4 ? ?
1 ? 4 3
? 2 ? ?
2 1 ? ?
4 ? ? 2
样例输出
Case #1: Yes
Case #2: No
Case #3: No
数独规则：横向，纵向，2*2的小方格里，1-4各出现一次。（2*(i/2)+j/2是计算在第几个小方格里）
题意：判断可否完成数独，dfs中如果可以走到最后（flag=1）说明可行。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
int a[20][20],flag;
int r[20][20],l[20][20],s[20][20];//r行 l列 s小方阵
void dfs(int i,int j)
{if(i==4&&j==0)flag=1; else{if(a[i][j]!=0){if(j<3)dfs(i,j+1);elsedfs(i+1,0);}else{for(int k=1;k<=4;k++){if(!r[i][k]&&!l[j][k]&&!s[2*(i/2)+j/2][k]){a[i][j]=k;r[i][k]=1;l[j][k]=1;s[2*(i/2)+j/2][k]=1;if(j<3)dfs(i,j+1);elsedfs(i+1,0);if(flag)return;//回溯重置 a[i][j]=0;r[i][k]=0;l[j][k]=0;s[2*(i/2)+j/2][k]=0;}}}}
}
int main()
{int t,i,j,o=1;char aa;scanf("%d",&t);while(t--){memset(r,0,sizeof r);memset(l,0,sizeof l); memset(s,0,sizeof s);for(i=0;i<4;i++){for(j=0;j<4;j++){getchar();scanf("%c",&aa);if(aa=='?')a[i][j]=0;elsea[i][j]=aa-'0'; if(a[i][j]){r[i][a[i][j]]=1;l[j][a[i][j]]=1;s[2*(i/2)+j/2][a[i][j]]=1;}}} flag=0;dfs(0,0);if(flag)printf("Case #%d: Yes\n",o++);elseprintf("Case #%d: No\n",o++);getchar();}
}
这篇关于TOJ 4972: 数独 4*4 dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
