也许是一个需要题解的题解

也许是一个需要题解的题解

---

用一些方法做就是会增加内存和耗时，所以我kil my mind做了一个内存和耗时都较少的 (也许可能也没有很少)。

#include <cstdio>
#include <cstring>
#include <tuple>
#include <algorithm>
using namespace std;

const int SIZE = 9;
int grid[SIZE][SIZE]; // Sudoku grid // 数独网格
int score[SIZE][SIZE] = { // Score matrix for maximizing // 用于求最大分数的得分矩阵
    {6, 6, 6, 6, 6, 6, 6, 6, 6},
    {6, 7, 7, 7, 7, 7, 7, 7, 6},
    {6, 7, 8, 8, 8, 8, 8, 7, 6},
    {6, 7, 8, 9, 9, 9, 8, 7, 6},
    {6, 7, 8, 9, 10, 9, 8, 7, 6},
    {6, 7, 8, 9, 9, 9, 8, 7, 6},
    {6, 7, 8, 8, 8, 8, 8, 7, 6},
    {6, 7, 7, 7, 7, 7, 7, 7, 6},
    {6, 6, 6, 6, 6, 6, 6, 6, 6}
};
int rowUsed[SIZE], colUsed[SIZE], boxUsed[SIZE]; // Bitmasks for used numbers in rows, columns, and boxes // 行、列和盒子中使用数字的位掩码
int maxScore = -1, curScore = 0; // Track maximum and current score // 记录最大得分和当前得分

// [High] Calculate box index from row and column coordinates -> Used to determine which 3x3 box a cell belongs to
// [重要] 根据行和列坐标计算3x3盒子的索引 -> 用于确定某个单元格属于哪个3x3区域
int getBoxIndex(int i, int j) {
    return (i / 3) * 3 + j / 3; // Calculate box index by row and column // 根据行和列计算盒子索引
}

// [High] Mark or unmark a number as used in a row, column, and box -> Adjusts the bitmasks accordingly
// [重要] 在行、列和盒子中标记或取消标记某个数字 -> 相应调整位掩码
void setUsed(int r, int c, int num, bool flag) {
    int mask = 1 << (num - 1); // Create a bitmask for the number // 为数字创建一个位掩码
    if (flag) {
        rowUsed[r] |= mask; // Set bit in row bitmask // 在行位掩码中设置该数字
        colUsed[c] |= mask; // Set bit in column bitmask // 在列位掩码中设置该数字
        boxUsed[getBoxIndex(r, c)] |= mask; // Set bit in box bitmask // 在盒子位掩码中设置该数字
    } else {
        rowUsed[r] &= ~mask; // Clear bit in row bitmask // 清除行位掩码中的该数字
        colUsed[c] &= ~mask; // Clear bit in column bitmask // 清除列位掩码中的该数字
        boxUsed[getBoxIndex(r, c)] &= ~mask; // Clear bit in box bitmask // 清除盒子位掩码中的该数字
    }
}

// [Medium] Check if a number can be placed in a specific cell -> Returns true if the number can be placed without conflicts
// [中等] 检查某个数字是否可以放置在指定单元格中 -> 如果没有冲突可以放置则返回true
inline bool canPlace(int r, int c, int num) {
    int mask = 1 << (num - 1); // Create a bitmask for the number // 为数字创建一个位掩码
    return !(rowUsed[r] & mask) && !(colUsed[c] & mask) && !(boxUsed[getBoxIndex(r, c)] & mask); // Check row, column, and box // 检查行、列和盒子中是否冲突
}

// [High] Get all possible numbers that can be placed in a specific cell -> Uses bitmasking to find valid numbers quickly
// [重要] 获取可以放置在某个单元格中的所有可能数字 -> 使用位掩码快速找到可用的数字
int getPossibleValues(int r, int c) {
    return ~(rowUsed[r] | colUsed[c] | boxUsed[getBoxIndex(r, c)]) & 0x1FF;
    /* 
       Combine the row, column, and box bitmasks using OR, then invert the result (~) 
       to get valid positions for placing numbers, mask it with 0x1FF (which is 9 bits of 1's)
       to ensure we only care about the first 9 bits (numbers 1-9). 
       将行、列和盒子的位掩码通过按位或操作组合，然后取反(~)，
       得到可以放置数字的有效位置，并与0x1FF（9位全1）进行按位与操作，
       确保只关心前9位（数字1-9）。
    */
}

// [High] Find the next cell with the fewest possible number choices -> Uses minimum remaining values (MRV) heuristic
// [重要] 找到可选数字最少的下一个单元格 -> 使用最少剩余值（MRV）启发式策略
tuple<int, int> findNextPosition() {
    int minOptions = 10; // Start with more than 9 options (invalid max) // 初始值设为超过9个选项（无效最大值）
    int bestR = -1, bestC = -1; // Store best position (row, column) // 存储最佳位置（行，列）
    for (int r = 0; r < SIZE; ++r) {
        for (int c = 0; c < SIZE; ++c) {
            if (grid[r][c] == 0) { // Only check empty cells // 只检查空单元格
                int options = __builtin_popcount(getPossibleValues(r, c)); // Count valid options using built-in function // 使用内置函数计算有效选项的数量
                if (options < minOptions) {
                    minOptions = options; // Update minimum options found // 更新找到的最小选项数
                    bestR = r;
                    bestC = c;
                }
                if (minOptions == 1) return {bestR, bestC}; // Early exit if only 1 option left // 如果只剩一个选项，提前退出
            }
        }
    }
    return {bestR, bestC}; // Return the cell with the fewest options // 返回具有最少选项的单元格
}

// [High] Recursive backtracking solver -> Fills the grid and calculates maximum score while solving
// [重要] 递归回溯求解器 -> 在求解过程中填充网格并计算最大得分
bool solve() {
    auto [r, c] = findNextPosition(); // Find the best position to fill // 找到最适合填充的单元格位置
    if (r == -1) { // No empty cells left, solution found // 没有剩余空单元格，已找到解决方案
        if (curScore > maxScore) {
            maxScore = curScore; // Update maximum score // 更新最大得分
        }
        return true;
    }

    bool solved = false;
    int options = getPossibleValues(r, c); // Get valid options as bitmask // 获取有效选项的位掩码
    while (options) {
        int num = __builtin_ctz(options) + 1; // Find the lowest set bit (first available number) // 找到最低位的1（第一个可用的数字）
        options &= options - 1; // Remove the lowest set bit (mark the number as used) // 清除最低位的1（标记数字为已用）

        grid[r][c] = num; // Place the number in the grid // 将数字放入网格
        setUsed(r, c, num, true); // Mark the number as used in row, column, and box // 在行、列和盒子中标记该数字为已用
        curScore += num * score[r][c]; // Add to current score based on the cell's weight // 根据该单元格的权重增加当前得分

        solved |= solve(); // Recursive call, continue solving // 递归调用，继续求解

        curScore -= num * score[r][c]; // Backtrack: undo the score update // 回溯：撤销得分更新
        setUsed(r, c, num, false); // Backtrack: unmark the number as used // 回溯：取消该数字的已用标记
        grid[r][c] = 0; // Backtrack: remove the number from the grid // 回溯：从网格中移除该数字
    }
    return solved; // Return whether a solution was found // 返回是否找到解决方案
}

int main() {
    // [Medium] Read the input Sudoku grid -> Initialize the state with given numbers
    // [中等] 读取输入的数独网格 -> 使用给定的数字初始化状态
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            scanf("%d", &grid[i][j]); // Read input for each cell // 读取每个单元格的输入
            if (grid[i][j] != 0) { // If the cell is pre-filled // 如果单元格已预填充
                int num = grid[i][j];
                setUsed(i, j, num, true); // Mark the pre-filled number as used // 标记预填充的数字为已用
                curScore += num * score[i][j]; // Add to current score based on the cell's weight // 根据该单元格的权重增加当前得分
            }
        }
    }

    // [High] Start solving the Sudoku -> Output the maximum score if solvable, else output -1
    // [重要] 开始求解数独 -> 如果可解，输出最大得分，否则输出-1
    bool success = solve();
    if (success) {
        printf("%d\n", maxScore); // Print the maximum score // 输出最大得分
    } else {
        printf("-1\n"); // If no solution, print -1 // 如果无解，输出-1
    }

    return 0;
}

贴心的加了中英双语注释哦，希望有用吧。
看懂的人记得题解一下题解 :-[]
Thanks to everybody.