Let Sudoku Rotate (dfs+剪枝)

2018-08-02

Let Sudoku Rotate

题意

数独，有一个16*16的数独数独内的数字从0~E，一开始数独是完美的，可是有个人逆时针旋转了数独中的某几块（4x4），导致数独不完美了，给你这个旋转后的数独，要求还原他至少要再旋转几步？

思路

dfs+剪枝。

写出下列几个操作：

顺时针旋转4*4的方块；
判断每行的总和是否都为120；
判断每行和每列的元素是否都不重复；
dfs，由于一行块有4个分块，因此四重循环，同一个x分别对应y的起始：0，4，8，12，循环+1表示旋转次数+1，如果在2、3的判断中都满足这写要求，说明可以进行下一个x+4（起始行）块的旋转操作dfs，step+本次旋转的操作（i，j，k，l四重循环），要是不满足还是要继续。当x==16或者是step比当前已知的最小ans要大的时候都可以return。

看！代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
const long long MOD =1e9+7;
typedef long long ll;
char m[20][20];
char cop[4][4];
int ans=64;
void print()
{
    printf("\n");
    for(int i=0;i<16;i++,printf("\n"))
        for(int j=0;j<16;j++)
            printf("%c",m[i][j]);
    printf("\n");
}
int rol(int x,int y)
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            cop[i][j]=m[x+3-j][y+i];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            m[i+x][j+y]=cop[i][j];
}
bool sum(int x)
{
    for(int j=x;j<x+4;j++)
    {
        int temp=0;
        for(int i=0;i<16;i++)
        {
            temp=temp+((m[x][i]>='0'&&m[x][i]<='9')?(m[x][i]-'0'):(m[x][i]-'A'+10));
        }
        if(temp!=120) return false;
    }
    return true;
}
bool multi(int x)
{
    int vis[16]={0};
    for(int j=x;j<x+4;j++)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<16;i++)
        {
            int temp=((m[j][i]>='0'&&m[j][i]<='9')?(m[j][i]-'0'):(m[j][i]-'A'+10));
            vis[temp]++;
            if(vis[temp]>1) return false;
        }
    }

    for(int i=0;i<16;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=0;j<=x+3;j++)
        {
            int temp=((m[j][i]>='0'&&m[j][i]<='9')?(m[j][i]-'0'):(m[j][i]-'A'+10));
            vis[temp]++;
            if(vis[temp]>1) return false;
        }
    }
    return true;
}
void dfs(int x,int step)
{
    if(step>ans) return;
    if(x==16)
    {
        ans=min(ans,step);return;
    }
    for(int i=0;i<4;i++,rol(x,0))
    for(int j=0;j<4;j++,rol(x,4))
    for(int k=0;k<4;k++,rol(x,8))
    for(int l=0;l<4;l++,rol(x,12))
    {
        if(!(sum(x)&&multi(x))) continue;
        dfs(x+4,step+i+j+k+l);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        getchar();
        for(int i=0;i<16;i++)
            scanf("%s",m[i]);
        ans=64;
        dfs(0,0);
        printf("%d\n",ans);
    }
    return 0;
}