HDU-6341：Problem J. Let Sudoku Rotate（DFS）

Problem J. Let Sudoku Rotate
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)

Problem Description
Sudoku is a logic-based, combinatorial number-placement puzzle, which is popular around the world.
In this problem, let us focus on puzzles with 16×16 grids, which consist of 4×4 regions. The objective is to fill the whole grid with hexadecimal digits, i.e. 0123456789ABCDEF, so that each column, each row, and each region contains all hexadecimal digits. The figure below shows a solved sudoku.

Yesterday, Kazari solved a sudoku and left it on the desk. However, Minato played a joke with her - he performed the following operation several times.
* Choose a region and rotate it by 90 degrees counterclockwise.
She burst into tears as soon as she found the sudoku was broken because of rotations.
Could you let her know how many operations her brother performed at least?

Input
The first line of the input contains an integer T(1≤T≤103)$T(1\le T\le {10}^3)$ denoting the number of test cases.
Each test case consists of exactly 16 lines with 16 characters each, describing a broken sudoku.

Output
For each test case, print a non-negative integer indicating the minimum possible number of operations.

Sample Input
1
681D5A0C9FDBB2F7
0A734B62E167D9E5
5C9B73EF3C208410
F24ED18948A5CA63
39FAED5616400B74
D120C4B7CA3DEF38
7EC829A085BE6D51
B56438F129F79C2A
5C7FBC4E3D08719F
AE8B1673BF42A58D
60D3AF25619C30BE
294190D8EA57264C
C7D1B35606835EAB
AF52A1E019BE4306
8B36DC78D425F7C9
E409492FC7FA18D2

Sample Output
5

Hint

The original sudoku is same as the example in the statement.

题解：搜索加可行性剪枝即可通过。由于数独限制较强，剪枝效果良好。
深搜枚举每个4*4的小矩阵的旋转次数，判断是否冲突且满足每行的和为120。

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
char s[20][20];
char p[5][5];
int vis[20];
void roat(int x,int y)//顺时针旋转矩阵90度
{
    for(int i=1,a=y;i<=4;i++,a++)
    for(int j=1,b=x;j<=4;j++,b--)p[i][j]=s[b][a];
    for(int j=1,a=y;j<=4;j++,a++)
    for(int i=4,b=x;i>=1;i--,b--)s[b][a]=p[i][j];
}
int g(char c){return (c>='0'&&c<='9')?c-'0':c-'A'+10;}
int checkrow(int x)
{
    for(int i=x-3;i<=x;i++)//每行数的和要等于120
    {
        int sum=0;
        for(int j=1;j<=16;j++)sum+=g(s[i][j]);
        if(sum!=120)return 0;
    }
    for(int i=x-3;i<=x;i++)//每行不能有重复出现的数(有了这个，上面的那个貌似是多余的。。。)
    {
        memset(vis,0,sizeof vis);
        for(int j=1;j<=16;j++)
        {
            if(vis[g(s[i][j])])return 0;
            vis[g(s[i][j])]=1;
        }
    }
    for(int j=1;j<=16;j++)//每列不能有重复出现的数
    {
        memset(vis,0,sizeof vis);
        for(int i=1;i<=x;i++)
        {
            if(vis[g(s[i][j])])return 0;
            vis[g(s[i][j])]=1;
        }
    }
    return 1;
}
int ans;
void dfs(int k,int num)//k表示枚举到第k行，num表示旋转次数
{
    if(num>ans)return;
    if(k==20){ans=min(ans,num);return;}
    for(int a=0;a<=3;a++,roat(k,1))//枚举这4个子矩阵的旋转次数
    for(int b=0;b<=3;b++,roat(k,5))
    for(int c=0;c<=3;c++,roat(k,9))
    for(int d=0;d<=3;d++,roat(k,13))
    {
        if(checkrow(k)==0)continue;//判断前k行是否满足数独的条件
        dfs(k+4,num+a+b+c+d);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=1;i<=16;i++)scanf("%s",s[i]+1);
        ans=16*4;
        dfs(4,0);
        printf("%d\n",ans);
    }
    return 0;
}