数独

题目描述

数独是一种填数字游戏，英文名叫 Sudoku，起源于瑞士，上世纪 70 年代由美国一家数学逻辑游戏杂志首先发表，名为 Number Place，后在日本流行，1984 年将 Sudoku 命名为数独，即 “独立的数字” 的缩写，意思是 “在每一格只有一个数字”。

2004 年，曾任中国香港高等法院法官的高乐德 (Wayne Gould) 把这款游戏带到英国，成为英国流行的数学智力拼图游戏。

玩家需要根据 9×99 \times 99×9 盘面上的已知数字，推理出所有剩余位置的数字，并满足每一行、每一列、每一个粗线九宫格内的数字包含有 1-9 的数字，且不重复。

现在给你一个数独，请你解答出来。每个数独保证有且只有一个解。

输入描述:

输入仅一组数据，共 9 行 9 列，表示初始数独（其中 0 表示数独中的空位）。

输出描述:

输出共 9 行 9 列，表示数独的解。
注意⾏末没有空格。

示例1

输入

复制 

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

输出

复制 

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

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
struct ty{
    int x,y;
}kong[90];
int cnt=0;
int h[10][10],l[10][10],x[10][10],xiao[15][15]={{0,0,0,0,0,0,0,0,0,0},
                                                {0,1,1,1,2,2,2,3,3,3},
                                                {0,1,1,1,2,2,2,3,3,3},
                                                {0,1,1,1,2,2,2,3,3,3},
                                                {0,4,4,4,5,5,5,6,6,6},
                                                {0,4,4,4,5,5,5,6,6,6},
                                                {0,4,4,4,5,5,5,6,6,6},
                                                {0,7,7,7,8,8,8,9,9,9},
                                                {0,7,7,7,8,8,8,9,9,9},
                                                {0,7,7,7,8,8,8,9,9,9},
                                                {0,7,7,7,8,8,8,9,9,9}
                                                          };
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 dep){
    if(dep>cnt){print();return;};
    for(int i=1;i<=9;i++){
        int xx=kong[dep].x;
        int yy=kong[dep].y;
        if(h[xx][i]==0&&l[yy][i]==0&&x[xiao[xx][yy]][i]==0){
            h[xx][i]=1;
        l[yy][i]=1;
        x[xiao[xx][yy]][i]=1;
        a[xx][yy]=i;
        dfs(dep+1);
        h[xx][i]=0;l[yy][i]=0;x[xiao[xx][yy]][i]=0;
        }

    }
}
int main() {
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cin>>a[i][j];
            if(!a[i][j]){
                kong[++cnt].x=i;
                kong[cnt].y=j;
            }
            else{
                h[i][a[i][j]]=1;
                l[j][a[i][j]]=1;
                x[xiao[i][j]][a[i][j]]=1;
            }
        }
    }
    // cout<<cnt;
    dfs(1);
    return 0;
}