C++数独求解器适配16x16/25x25网格及性能优化问题求助

首先导致16x16、25x25规格无法运行的核心问题有2个：

• 全局isValid函数的数值范围校验硬编码了最大值为9，16x16规格的合法数值最大为16，25x25为25，所有大于9的输入都会被直接判定为非法输入，直接阻断了大规格数独的求解流程。
• 宫格校验时直接将sqrt(grid.size())的浮点返回值赋值给int，极端情况下会出现浮点精度损失导致的取整错误，比如sqrt(25)因精度问题返回4.9999999999，转int后得到4，导致宫格范围计算错误。

另外还有两处不影响运行的问题：

• getFreeCellList函数注释仍标注最大自由格数为81，仅适用于9x9规格。
• search函数回溯分支的注释写死“grid[i][j]是9，回溯”，和大规格逻辑不符。

1. 修复数值范围校验 #

修改isValid(vector<vector<int>> grid)函数的范围校验逻辑：

// 原有错误代码
// if ((grid[i][j] < 0) || (grid[i][j] > 9))

// 修复后代码
int maxValidVal = grid.size();
if ((grid[i][j] < 0) || (grid[i][j] > maxValidVal))

2. 修复浮点精度问题 #

修改isValid(int i, int j, vector<vector<int>> grid)函数中宫格大小计算逻辑：

// 原有错误代码
// int n = sqrt(grid.size());

// 修复后代码，加小epsilon避免浮点精度损失导致取整错误
int boxSize = static_cast<int>(sqrt(grid.size()) + 1e-6);

3. 消除不必要的网格拷贝（同时解决适配问题+优化性能） #

所有isValid、printGrid、getFreeCellList函数的网格参数均为值传递，每次调用都会完整拷贝整个网格，大规格下拷贝开销极高，统一改为const引用传递：

// 原有函数声明
// bool isValid(int i, int j, vector<vector<int>> grid);
// bool isValid(vector<vector<int>> grid);
// void printGrid(vector<vector<int>> grid);
// int getFreeCellList(vector<vector<int>> grid, vector<pair<int, int>> &freeCellList);

// 修改后声明
bool isValid(int i, int j, const vector<vector<int>>& grid);
bool isValid(const vector<vector<int>>& grid);
void printGrid(const vector<vector<int>>& grid);
int getFreeCellList(const vector<vector<int>>& grid, vector<pair<int, int>> &freeCellList);

• 引入MRV最小剩余值启发式：当前代码按固定顺序填充空闲格子，大规格下会导致回溯分支爆炸，每次优先选择候选数最少的格子填充，能大幅减少无效搜索的次数，是数独求解的核心优化手段。
• 位运算加速候选数校验：当前每次判断数值是否合法需要遍历行、列、宫三次，大规格下开销极高，可以用位掩码提前记录每行、每列、每宫已使用的数字，判断和更新操作都可以通过一次位运算完成，性能可提升数倍。
• 加入前向检查剪枝：每次填充一个格子后，直接更新相关行、列、宫的候选数，如果发现存在无候选数的空闲格子，直接回溯剪枝，不用等到填充到该格子才发现路径错误，进一步减少无效搜索。
• 预计算宫格索引：提前把每个格子所属的宫格索引存到数组中，不用每次校验时重复做除法乘法运算，降低计算开销。

内容的提问来源于stack exchange，提问作者Izzy