#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

class SudokuSolver {
private:
    std::array<std::array<int, 9>, 9> board;
    
public:
    SudokuSolver() {
        // C++11: 使用范围for循环初始化
        for(auto& row : board) {
            row.fill(0);
        }
    }
    
    // 输入数独
    void inputBoard() {
        std::cout << "请输入9x9数独（0表示空白，数字用空格或换行分隔）：" << std::endl;
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                std::cin >> board[i][j];
                // 输入验证
                if(board[i][j] < 0 || board[i][j] > 9) {
                    std::cout << "输入无效，请输入0-9之间的数字！" << std::endl;
                    return;
                }
            }
        }
    }
    
    // 打印数独
    void printBoard() const {
        std::cout << "\n+-------+-------+-------+" << std::endl;
        for(int i = 0; i < 9; ++i) {
            std::cout << "| ";
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] == 0)
                    std::cout << ". ";
                else
                    std::cout << board[i][j] << " ";
                
                if((j + 1) % 3 == 0)
                    std::cout << "| ";
            }
            std::cout << std::endl;
            if((i + 1) % 3 == 0)
                std::cout << "+-------+-------+-------+" << std::endl;
        }
    }
    
    // 检查在(row, col)位置放置num是否有效
    bool isValid(int row, int col, int num) const {
        // 检查行
        for(int j = 0; j < 9; ++j) {
            if(board[row][j] == 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 findEmptyPosition(int& row, int& col) const {
        for(row = 0; row < 9; ++row) {
            for(col = 0; col < 9; ++col) {
                if(board[row][col] == 0)
                    return true;
            }
        }
        return false;
    }
    
    // 回溯法求解数独
    bool solve() {
        int row, col;
        
        // 如果没有空白位置，说明数独已填满
        if(!findEmptyPosition(row, col))
            return true;
        
        // 尝试填入1-9
        for(int num = 1; num <= 9; ++num) {
            if(isValid(row, col, num)) {
                board[row][col] = num;
                
                // 递归求解
                if(solve())
                    return true;
                
                // 如果当前数字导致无解，回溯
                board[row][col] = 0;
            }
        }
        
        return false; // 无解
    }
    
    // 检查初始数独是否有效
    bool isValidBoard() const {
        // 检查每一行
        for(int i = 0; i < 9; ++i) {
            std::array<bool, 10> rowCheck;
            rowCheck.fill(false);
            for(int j = 0; j < 9; ++j) {
                if(board[i][j] != 0) {
                    if(rowCheck[board[i][j]])
                        return false;
                    rowCheck[board[i][j]] = true;
                }
            }
        }
        
        // 检查每一列
        for(int j = 0; j < 9; ++j) {
            std::array<bool, 10> colCheck;
            colCheck.fill(false);
            for(int i = 0; i < 9; ++i) {
                if(board[i][j] != 0) {
                    if(colCheck[board[i][j]])
                        return false;
                    colCheck[board[i][j]] = true;
                }
            }
        }
        
        // 检查每个3x3宫格
        for(int block = 0; block < 9; ++block) {
            std::array<bool, 10> blockCheck;
            blockCheck.fill(false);
            int startRow = (block / 3) * 3;
            int startCol = (block % 3) * 3;
            
            for(int i = 0; i < 3; ++i) {
                for(int j = 0; j < 3; ++j) {
                    int num = board[startRow + i][startCol + j];
                    if(num != 0) {
                        if(blockCheck[num])
                            return false;
                        blockCheck[num] = true;
                    }
                }
            }
        }
        
        return true;
    }
    
    // 重置数独
    void reset() {
        for(auto& row : board) {
            row.fill(0);
        }
    }
    
    // C++11: 移动构造函数
    SudokuSolver(SudokuSolver&& other) noexcept 
        : board(std::move(other.board)) {}
    
    // C++11: 移动赋值运算符
    SudokuSolver& operator=(SudokuSolver&& other) noexcept {
        if(this != &other) {
            board = std::move(other.board);
        }
        return *this;
    }
    
    // 获取当前数独状态（C++11: 返回const引用）
    const std::array<std::array<int, 9>, 9>& getBoard() const {
        return board;
    }
    
    // 设置指定位置的值
    void setCell(int row, int col, int value) {
        if(row >= 0 && row < 9 && col >= 0 && col < 9 && value >= 0 && value <= 9) {
            board[row][col] = value;
        }
    }
};

// C++11: 使用lambda表达式的辅助函数
void printWelcomeMessage() {
    auto printLine = []() {
        std::cout << std::string(50, '=') << std::endl;
    };
    
    printLine();
    std::cout << "           数独求解器 (C++11 版本)" << std::endl;
    printLine();
}

int main() {
    printWelcomeMessage();
    
    SudokuSolver sudoku;
    int choice;
    
    std::cout << "1. 手动输入数独" << std::endl;
    std::cout << "2. 使用示例数独" << std::endl;
    std::cout << "请选择 (1-2): ";
    std::cin >> choice;
    
    if(choice == 1) {
        sudoku.inputBoard();
    } else {
        // 提供一个示例数独（中等难度）
        // C++11: 使用初始化列表
        std::array<std::array<int, 9>, 9> example = {{
            {{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}}
        }};
        
        // 使用setCell方法设置示例数独
        for(int i = 0; i < 9; ++i) {
            for(int j = 0; j < 9; ++j) {
                sudoku.setCell(i, j, example[i][j]);
            }
        }
        std::cout << "已加载示例数独：" << std::endl;
    }
    
    std::cout << "\n输入的数独：" << std::endl;
    sudoku.printBoard();
    
    // 检查初始数独是否有效
    if(!sudoku.isValidBoard()) {
        std::cout << "\n错误：输入的数独无效（存在冲突）！" << std::endl;
        return 1;
    }
    
    // 求解数独
    std::cout << "\n正在求解..." << std::endl;
    
    if(sudoku.solve()) {
        std::cout << "\n求解成功！结果如下：" << std::endl;
        sudoku.printBoard();
    } else {
        std::cout << "\n无解：该数独没有有效解！" << std::endl;
    }
    
    return 0;
}