题解 | Sudoku

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

bool isValidNum(const vector<vector<int>>& sudoku, int x, int y, int num) {
    //检查(x,y)所在的行和列有没有重复 
    for(int i = 0; i < 9; ++i) {
        if(sudoku[x][i] == num || sudoku[i][y] == num) {
            return false;
        }
    }

    //检查(x,y)所在的3x3方格里有没有重复
    int start_row = (x / 3) * 3;
    int start_col = (y / 3) * 3;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            if(sudoku[start_row + i][start_col + j] == num) {
                return false;
            }
        }
    }
    return true;
}

bool backTrack(vector<vector<int>>& sudoku) {
    for(int i = 0; i < 9; ++i) {
        for(int j = 0; j < 9; ++j) {
            if(sudoku[i][j] == 0) {
                for(int k = 1; k <= 9; ++k) {
                    if(isValidNum(sudoku, i, j, k)) {
                        sudoku[i][j] = k;
                        if(backTrack(sudoku)) {
                            return true;
                        }
                        sudoku[i][j] = 0; //撤销 回溯
                    }
                }
                return false;
            }
        }
    }
    return true;
}



int main() {
    vector<vector<int>> sudoku(9, vector<int>(9, 0));
    for(int i = 0; i < 9; ++i) {
        for(int j = 0; j < 9; ++j) {
            cin >> sudoku[i][j];
        }
    }
    backTrack(sudoku);
    for(int i = 0; i < 9; ++i) {
        for(const int& n: sudoku[i]) {
            cout << n << " ";
        }
        cout << endl;
    }
    return 0;
}