题解 | #Sudoku#

编写check函数检查某个位置能够设置某个数，然后从第一个空缺位置开始使用深度优先遍历的方式尝试所有可能的数字，失败是进行回溯。

#include <iostream>
#include <sstream>
#include <cstring>
#include <vector>

using namespace std;

bool check(int x, int y, int value, int map[9][9]) {
    int m[10];

    bzero(m, sizeof(m));
    for(int i=0; i<9; i++) {
        int v = (i==y)? value : map[x][i];
        if (v != 0 && m[v] != 0) {
            return false;
        }
        m[v] = 1;
    }

    bzero(m, sizeof(m));
    for(int i=0; i<9; i++) {
        int v = (i==x)? value : map[i][y];
        if (v != 0 && m[v] != 0) {
            return false;
        }
        m[v] = 1;
    }

    bzero(m, sizeof(m));
    int x_start = (x / 3) * 3;
    int y_start = (y / 3) * 3;
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            int p_x = x_start + i;
            int p_y = y_start + j;
            int v = (p_x == x && p_y == y)? value : map[p_x][p_y];
            if (v != 0 && m[v] != 0) {
                return false;
            }
            m[v] = 1;
        }
    }
    return true;
}

struct Coor{
    int x;
    int y;
    Coor(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

bool dfs(vector<Coor> &blanks, int n, int map[9][9]) {
    int x = blanks[n].x;
    int y = blanks[n].y;

    if (n >= blanks.size()) {
        return true;
    }

    for(int i=1; i<=9; i++) {
        if (check(x, y, i, map)) {
            map[x][y] = i;
            if (dfs(blanks, n + 1, map)) {
                return true;
            } else {
                map[x][y] = 0;
            }
        }
    }
    return false;
}

int main () {
    int map[9][9];
    string line;

    while(getline(cin, line)) {
        stringstream ss;
        vector<Coor> blanks;

        for(int i=0; i<9; i++) {
            ss.clear();
            ss.str(line);
            for(int j=0; j<9; j++) {
                ss >> map[i][j];
                if (map[i][j] == 0) {
                    blanks.push_back(Coor(i, j));
                }
            }
            if (i<9) {
                getline(cin, line);
            }
        }
        dfs(blanks, 0, map);
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout << map[i][j] << ' ';
            }
            cout << endl;
        }
    }
    return 0;
}