题解 | #Sudoku# c++ 回溯

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> board(9, vector<int>(9));

bool isValid(int row, int col, int val, vector<vector<int>>& board) {
    for (int i = 0; i < 9; ++i) {// 判断行里是否重复
        if (board[row][i] == val) {
            return false;
        }
    }
    for (int j = 0; j < 9; ++j) {// 判断列里是否重复
        if (board[j][col] == val) {
            return false;
        }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; ++i) {// 判断9方格里是否重复
        for (int j = startCol; j < startCol + 3; ++j) {
            if (board[i][j] == val) {
                return false;
            }
        }
    }
    return true;
}


bool backtrack(vector<vector<int>>& board) {
    for (int i = 0; i < 9; ++i) {// 遍历行
        for (int j = 0; j < 9; ++j) {// 遍历列
            if (board[i][j] != 0) {
                continue;
            }
            for (int k = 1; k <= 9; ++k) {// (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) { 
                    board[i][j] = k; // 放置k
                    if (backtrack(board)) { 
                        return true;// 如果找到合适一组立刻返回
                    }
                    board[i][j] = 0;// 回溯，撤销k
                }
            }
            return false;// 9个数都试完了，都不行，那么就返回false
        }
    }
    return true;
}


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

    backtrack(board);

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (j == 8) {
                cout << board[i][j];
            } else {
                cout << board[i][j] << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}