P2924 数独挑战

时间限制: 1 s
空间限制: 1000 KB
题目等级 : 钻石 Diamond

题目描述 Description

“芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”这是英国《每日邮报》2012年6月30日的一篇报道。这个号称“世界最难数独”的“超级游戏”，却被扬州一位69岁的农民花三天时间解了出来。
看到这个新闻后，我激动不已，证明我们OI的实力的机会来了，我们虽然不是思考能力最快、头脑最聪明的人，但是我们可以保证在1s之内解题。
好了废话不多说了……
数独是一种填数字游戏，英文名叫Sudoku，起源于瑞士，上世纪70年代由美国一家数学逻辑游戏杂志首先发表，名为Number Place，后在日本流行，1984年将Sudoku命名为数独，即“独立的数字”的省略，解释为每个方格都填上一个个位数。2004年，曾任中国香港高等法院法官的高乐德(Wayne Gould)把这款游戏带到英国，成为英国流行的数学智力拼图游戏。
玩家需要根据9×9盘面上的已知数字，推理出所有剩余位置（数据表示为数字0）的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
现在给你一个数独，请你解答出来。每个数独保证有解且只有一个。

输入描述 Input Description

9行9列。
每个数字用空格隔开。0代表要填的数
行末没有空格，末尾没有回车。

输出描述 Output Despription

输出答案。
排成9行9列。
行末没有空格，结尾可以有回车。

样例输入 Sample Input

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

样例输出 Sample Output

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

数据范围及提示 Data Size & Hint

保证有解，每个数独都由http://oubk.com数独网提供。
其中数据hard1.in为芬兰数学家提供。

题解

用三个数组记录在每一行、每一列、每一个九宫格中某个数字是否出现过，然后就是正常的dfs了

C++代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int a[10][10];
int hang[10][10],lie[10][10],squ[10][10];

void ins(int x,int y,int num,int flag) { 
    if(flag)
        a[x][y]=num;
    if(!flag)
        a[x][y]=0;
    hang[x][num]=flag;
    lie[y][num]=flag;
    squ[(x-1)/3*3+(y-1)/3+1][num]=flag;
}

int check(int x,int y,int num) {
    if(hang[x][num])return 0;
    if(lie[y][num])return 0;
    if(squ[(x-1)/3*3+(y-1)/3+1][num])return 0;
    return 1;
}

void print() {
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
}

void dfs(int x,int y) {
    if(a[x][y]>0) {
        if(x==9 && y==9) {
            print();
            return;
        }
        if(y==9)
            dfs(x+1,1);
        else
            dfs(x,y+1);
    } else {
        for(int i=1; i<=9; i++)
            if(check(x,y,i)) {
                ins(x,y,i,1);
                if(x==9&&y==9) {
                    print();
                    return;
                }
                if(y==9)
                    dfs(x+1,1);
                else
                    dfs(x,y+1);
                ins(x,y,i,0);
            }
    }
}


int main() {
    ios::sync_with_stdio(0);
    memset(hang,0,sizeof(hang));
    memset(lie,0,sizeof(lie));
    memset(squ,0,sizeof(squ));
    for(int i=1; i<=9; i++)
        for(int j=1; j<=9; j++) {
            int t;
            cin>>t;
            ins(i,j,t,1);
        }
    dfs(1,1);
    return 0;
}