题解 | #Sudoku#

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int mp[N][N];
bool find_answer_ok;
bool check(int row, int col, int val)
{
    for(int i = 0; i < 9; i++)if(mp[row][i] == val)return false;
    for(int i = 0; i < 9; i++)if(mp[i][col] == val)return false;
    for(int limit_row = row / 3 * 3,i = 0; i < 3; i++)
        for(int limit_col = col / 3 * 3,j = 0; j < 3; j++)
            if(mp[limit_row+i][limit_col+j] == val)return false;
    return true;
}
void dfs(int row, int col)//每个位置
{
    if(col == 9){row++;col = 0;}//下一行
    if(row == 9 && col == 0){find_answer_ok = true;return ;}//成功
    if(mp[row][col] == 0)//空
    {
        for(int i = 1; i <= 9; i++)//遍历
        {
            if(check(row, col, i))
            {
                mp[row][col] = i;
                dfs(row, col + 1);//递归
                if(find_answer_ok)return ;//结束
                mp[row][col] = 0; //dfs没找到能填的，回溯
            }
        }
    }
    else dfs(row, col + 1);
}
int main()
{
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            cin >> mp[i][j];
    dfs(0, 0);
    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
            cout << mp[i][j] << ' ';
        cout << endl;
    }
}