數獨挑戰（牛客網 2019年華南理工大學程式設計競賽（春季賽））

連結：https://ac.nowcoder.com/acm/contest/625/E

來源：牛客網

數獨是一種填數字遊戲，英文名叫 Sudoku，起源于瑞士，上世紀 70 年代由美國一家數學邏輯遊戲雜志首先發表，名為 Number Place，後在日本流行，1984 年将 Sudoku 命名為數獨，即 “獨立的數字” 的縮寫，意思是 “在每一格隻有一個數字”。

2004 年，曾任中國香港高等法院法官的高樂德 (Wayne Gould) 把這款遊戲帶到英國，成為英國流行的數學智力拼圖遊戲。

玩家需要根據 9×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

每次比賽都做不出搜尋題，真的要好好補補了qwq，要求每行每列和每個小正方形裡都要出現一次1~9

#include<cmath>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define memset(a,b) memset(a,sizeof(a),b)
using namespace std;
int mapp[10][10];
int flag=0;
int check(int x,int y,int n)
{
    for(int i=0; i<9; i++)
        if(mapp[x][i]==n)      //該行不能出現這個數
            return 0;
    for(int j=0; j<9; j++)
        if(mapp[j][y]==n)      //該列不能出現這個數
            return 0;
    int xx=x/3*3;
    int yy=y/3*3;
    for(int i=xx; i<=xx+2; i++)        //這個數所在的九宮格裡隻能出現一次這個數
    {
        for(int j=yy; j<=yy+2; j++)
            if(mapp[i][j]==n)
                return 0;
    }
    return 1;
}
void DFS(int x,int y)
{
    if(flag)
        return ;
    if( x== 9 && y== 0)     //搜尋到8行8列的下一個了
    {
        for(int i=0; i<9; i++)
        {
            for(int j=0; j<9; j++)
                cout<<mapp[i][j]<<" ";
            cout<<endl;
        }
        flag=1;
        return ;
    }
    if(y >= 9)
        DFS(x+1,0);      //搜尋到這一行的最後一個，開始搜尋下一行第一列
    else
    {
        if(mapp[x][y])              //這個位置不是0
            DFS(x,y+1);
        if(!mapp[x][y])           
        {
            for(int k=1; k<=9; k++)
            {
                if(check(x,y,k))
                {
                    mapp[x][y]=k;     //儲存這個數值
                    DFS(x,y+1);       //繼續搜尋下一列
                    mapp[x][y]=0;     //這個數恢複為0，回溯
                }
            }
        }

    }
}
int main()
{

    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
        {
            scanf("%d",&mapp[i][j]);
        }

    DFS(0,0);

    return 0;
}