基于C++使用回溯法求解数织问题.zip

## 编译 Windows-MSVC: ``` nmake msvc ``` Windows-MinGW: ``` mingw32-make gnu ``` Linux: ``` make gnu ``` ## 运行 ``` nonogram_solver INPUTFILE -v PRINTSTEPS # INPUTFILE：输入文件，PRINTSTEPS：每隔多少步打印一次中间状态 nonogram_solver INPUTFILE # 不打印中间状态 nonogram_solver INPUTFILE -v # 相当于：nonogram_solver INPUTFILE -v 10 nonogram_solver # 相当于：nonogram_solver input.txt ``` ## 代码简介 ``` solve ├ first_valid_row // 根据行约束，生成一行的初始解 ├ next_valid_row // 根据行约束，给定一行的一个解，生成该行下一个解 ├ prepare_column_check // 构造用于is_valid_columns的辅助数据结构 └ is_valid_columns // 检查 0~i 行是否符合列约束 ├ column_initial_check // 检查 0 行是否符合列约束 └ column_update_check // 当 i>0 时检查 0~i 行是否符合列约束 ``` 行初始解的生成方式：把所有的段都挤到最左边。例： ``` n = 15 row_constrain = [1, 2, 3] | | └--------┐ | └--┐ | v v v initial_solution = [1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] ``` 行下一个解的生成方式：从右往左找第一个能右移的段S，将S右移一格，并将S右边的所有段挤到紧挨着S ``` S | v previous_solution = [0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1] next_solution = [0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0] ``` 检查一列`[0,i]`号元素的方式： 1. 遍历`[0,i]`，检查已经出现的完整段是否匹配列约束的前几段； 2. 如果`i`号元素是黑色，则当前处在下一个段的开头部分，检查连续的黑色元素个数是否超过了该段长度； 3. 估计剩下的段至少要占据多大的空间，检查是否不超过`m-i-1`格。 `column_update_check`：当`i>0`时，由于在回溯过程中是逐行计算的，在检查`[0,i]`时，必然之前已经检查过`[0,i-1]`符合列约束。那么不需要遍历`[0,i]`，只需要记住前面检查时的状态，在此时进行从`(i-1)`到`i`的更新即可。 ## 测试数据来源 [数织-在线解谜游戏](https://cn.puzzle-nonograms.com)