题解 | #Sudoku#

#include <iostream>

using namespace std;

/**
 * 回溯算法
 * row[i][num]表示第i行是否出现过num
 * col[j][num]表示第j列是否出现过num
 * area[k][num]表示第k个3*3单元格是否出现过num k = 3*(row/3) + (col/3)
 * 回溯过程：
 *      当前格子没有数字--->遍历并根据限制条件选取可靠数字填入，更新限制条件，递归填写下一格
 *      当前格子存在数字--->递归填写下一格
 *      当前无法填入任何数字--->还原限制条件和已填入的数字，回到上一格再尝试下一个可用数字
 *      知道所有格子都填上数字，遍历结束
 */

int num[9][9], flag = 0;
bool row[9][10] = {0}, col[9][10] = {0}, area[9][10] = {0};

void dfs(int index) {
    if (index == 81) {
        flag = 1;
        return;
    }

    int i = index / 9;
    int j = index % 9;
    if (num[i][j]) dfs(index + 1);
    else {
        for (int k = 1; k < 10; ++k) {
            int curRow = row[i][k];
            int curCol = col[j][k];
            int curArea = area[3 * (i / 3) + (j / 3)][k];
            if (!row[i][k] && !col[j][k] && !area[3 * (i / 3) + (j / 3)][k]) {
                num[i][j] = k;
                row[i][k] = 1;
                col[j][k] = 1;
                area[3 * (i / 3) + (j / 3)][k] = 1;
                dfs(index + 1);
                if (flag) return;
                num[i][j] = 0;
                row[i][k] = curRow;
                col[j][k] = curCol;
                area[3 * (i / 3) + (j / 3)][k] = curArea;
            }
        }
    }
}

int main() {
    int x;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> x;
            num[i][j] = x;
            // 初始化状态
            if (x) {
                row[i][x] = 1;
                col[j][x] = 1;
                area[3 * (i / 3) + (j / 3)][x] = 1;
            }
        }
    }
    dfs(0);
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cout << num[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}