如何用C++编写数独求解器 回溯算法和二维数组应用

#include <iostream>
#include <vector>

using namespace std;

// 打印数独棋盘
void printBoard(const vector<vector<int>>& board) {
    for (int i = 0; i < 9; ++i) {
        if (i % 3 == 0 && i != 0) {
            cout << "-----------" << endl;
        }
        for (int j = 0; j < 9; ++j) {
            if (j % 3 == 0 && j != 0) {
                cout << "|";
            }
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

// 检查数字是否可以放置在指定位置
bool isValid(vector<vector<int>>& board, int row, int col, int num) {
    // 检查行
    for (int i = 0; i < 9; ++i) {
        if (board[row][i] == num) {
            return false;
        }
    }

    // 检查列
    for (int i = 0; i < 9; ++i) {
        if (board[i][col] == num) {
            return false;
        }
    }

    // 检查3x3子网格
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[startRow + i][startCol + j] == num) {
                return false;
            }
        }
    }

    return true;
}


// 使用回溯算法解决数独
bool solveSudoku(vector<vector<int>>& board) {
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (board[row][col] == 0) {
                for (int num = 1; num <= 9; ++num) {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num;

                        if (solveSudoku(board)) {
                            return true; // 找到解决方案
                        } else {
                            board[row][col] = 0; // 回溯
                        }
                    }
                }
                return false; // 当前位置无法找到有效数字
            }
        }
    }
    return true; // 数独已解决
}


int main() {
    vector<vector<int>> board = {
        {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}
    };

    cout << "初始数独棋盘:" << endl;
    printBoard(board);

    if (solveSudoku(board)) {
        cout << "\n数独解决方案:" << endl;
        printBoard(board);
    } else {
        cout << "数独无解" << endl;
    }

    return 0;
}