深度遍历每一个点+在每个点处进行各种各样的尝试=》各个题目

dfs的入口可以是遍历的个数n也可以是坐标i，j，就是一些运算上的差别。是对每一种空间的遍历

#include<iostream>
using namespace std;
int empty[9][9] = { 0 };//记录该行该列有几个空格
int a[9][9];//输入数独
bool flag = false;
bool check(int n, int value)
{
    int row = n / 9;
    int column = n % 9;
    //行
    for (int j = 0; j < 9; j++)
    {
        if (a[row][j] == value)
        {
            return false;
        }
    }
    //列
    for (int j = 0; j < 9; j++)
    {
        if (a[j][column] == value)
        {
            return false;
        }
    }
    //九宫格
    int rr = row / 3;
    int cc = column / 3;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (a[i + rr * 3][j + cc * 3] == value)
            {
                return false;
            }
        }
    }
    return true;
}
void dfs(int n)
{
    if (n >= 81)
    {
        flag = true;
        return;
    }
    else {
        if (a[n / 9][n % 9] != 0)
        {
            n++;
            dfs(n);
        }
        else {//空格填数
            for (int i = 1; i <= 9; i++)
            {
                if (check(n, i))
                {
                    a[n / 9][n % 9] = i;
                    dfs(n + 1);
                    if (flag)
                        return;
                    a[n / 9][n % 9] = 0;
                }
            }
        }
    }

}


int main()
{

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> a[i][j];
        }
    }
    dfs(0);
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << a[i][j]<<' ';
        }
        cout << endl;
    }
    return 0;
}