使用C++实现数独求解器：解密数独的算法之美

引言：

int board[9][9] = {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
};

bool solveSudoku(int row, int col) {
    if (row == 9) {
        // 数独已解决
        return true;
    }
    
    if (col == 9) {
        // 当前行已填充完毕，进入下一行
        return solveSudoku(row + 1, 0);
    }
    
    if (board[row][col] != 0) {
        // 当前格子已填充数字，进入下一列
        return solveSudoku(row, col + 1);
    }
    
    for (int num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {
            // 填充数字并进入下一列
            board[row][col] = num;
            if (solveSudoku(row, col + 1)) {
                return true;
            }
            // 回溯，尝试其他数字
            board[row][col] = 0;
        }
    }
    
    return false;
}

bool isValid(int row, int col, int num) {
    // 判断当前数字是否已存在于同一行或同一列
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }
    
    // 判断当前数字是否已存在于同一个3x3的小方格内
    int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

#include <IOStream>

using namespace std;

int board[9][9] = {
    {5, 3, 0, 0, 7, 0, 0, 0, 0},
    {6, 0, 0, 1, 9, 5, 0, 0, 0},
    {0, 9, 8, 0, 0, 0, 0, 6, 0},
    {8, 0, 0, 0, 6, 0, 0, 0, 3},
    {4, 0, 0, 8, 0, 3, 0, 0, 1},
    {7, 0, 0, 0, 2, 0, 0, 0, 6},
    {0, 6, 0, 0, 0, 0, 2, 8, 0},
    {0, 0, 0, 4, 1, 9, 0, 0, 5},
    {0, 0, 0, 0, 8, 0, 0, 7, 9}
};

bool isValid(int row, int col, int num) {
    // 判断当前数字是否已存在于同一行或同一列
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }
    
    // 判断当前数字是否已存在于同一个3x3的小方格内
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

bool solveSudoku(int row, int col) {
    if (row == 9) {
        // 数独已解决
        return true;
    }
    
    if (col == 9) {
        // 当前行已填充完毕，进入下一行
        return solveSudoku(row + 1, 0);
    }
    
    if (board[row][col] != 0) {
        // 当前格子已填充数字，进入下一列
        return solveSudoku(row, col + 1);
    }
    
    for (int num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {
            // 填充数字并进入下一列
            board[row][col] = num;
            if (solveSudoku(row, col + 1)) {
                return true;
            }
            // 回溯，尝试其他数字
            board[row][col] = 0;
        }
    }
    
    return false;
}

void printBoard() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

int mAIn() {
    if (solveSudoku(0, 0)) {
        cout << "数独已解决：" << endl;
        printBoard();
    } else {
        cout << "数独无解" << endl;
    }
    
    return 0;
}