题解 | #Sudoku#

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef struct pos_t {
    int x;
    int y;
} pos;

class Sudoku {
  public:
    Sudoku(const vector<vector<int>>& sudoku): m_sudoku(sudoku) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (m_sudoku[i][j] == 0) {
                    m_null_pos.push_back({i, j});
                }
            }
        }
        // cout<<m_null_pos.size()<<endl;
    }

    bool check_is_valid(pos current_pos, int val) {
        //3x3
        int current_3x3_pos_x = current_pos.x / 3 * 3;
        int current_3x3_pos_y = current_pos.y / 3 * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (m_sudoku[i + current_3x3_pos_x][j + current_3x3_pos_y] == val) {
                    return false;
                }
            }
        }

        //row
        for (int i = 0; i < 9; i++) {
            if (m_sudoku[current_pos.x][i] == val) {
                return false;
            }
        }

        //colomn
        for (int i = 0; i < 9; i++) {
            if (m_sudoku[i][current_pos.y] == val) {
                return false;
            }
        }
        return true;
    }

    int do_sudoku(int null_pos) {
        // cout<<"null_pos: "<<null_pos<<endl;
        if (null_pos >= m_null_pos.size()) {
            return 0;
        }

        int ret = 0;
        bool flag = false;
        pos current_pos = m_null_pos[null_pos];
        // cout<<"null_pos: "<<null_pos<<endl;
        int next_pos = null_pos + 1;
        for (int i = 1; i <= 9; i++) {
            // cout<<"    null_pos: "<<null_pos<<", i :"<<i<<endl;
            if (check_is_valid(current_pos, i)) {
                m_sudoku[current_pos.x][current_pos.y] = i;
                ret = do_sudoku(next_pos);
                // cout <<"        pos: "<<null_pos<<", "<< "current pos: "<<current_pos.x<<", "<<current_pos.y<<", val: "<<i<<", ret: "<<ret<<endl;
                if (ret == 0) {
                    flag = true;
                    break;
                }
            }
        }

        if (flag) {
            return 0;
        } else {
            m_sudoku[current_pos.x][current_pos.y] = 0;

            return -1;
        }

    }

    const vector<vector<int>>& get_sudoku() {
        return m_sudoku;
    }

  private:
    vector<vector<int>> m_sudoku;
    vector<pos> m_null_pos;
};

int main() {
    vector<vector<int>> sudoku(9, vector<int>(9));

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> sudoku[i][j];
        }
    }

    Sudoku object(sudoku);
    int ret = object.do_sudoku(0);
    sudoku = object.get_sudoku();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")