数织求解器 Nonogram Solver

本项目是一个基于 C++ 实现的高性能数织（Nonogram，又称 Picross, Griddlers 或 Hanjie）求解器。数织是一种图像逻辑谜题，玩家需要根据行和列的提示数字来填充或留空网格中的单元格，最终揭示隐藏的图片。本求解器采用回溯结合约束传播的算法，以高效地找到谜题的解决方案，并能够处理多解情况（输出所有解的数量，并显示第一个找到的解）。

项目结构

项目的目录结构如下：

.
├── CMakeLists.txt
├── nonogram_input.txt
└── src/
    ├── CMakeLists.txt
    ├── NonogramSolver.h
    ├── NonogramSolver.cpp
    └── main.cpp

编译与运行

本项目使用 CMake 进行构建：（以下代码都是在仓库的根目录执行）

mkdir -p build
cd build
cmake ..

使用 make 命令进行编译：

cd build
make

编译成功后，将在 ./build/src/ 目录下生成一个名为 NonogramSolver 的可执行文件。运行它来求解谜题：

./build/src/NonogramSolver

程序将读取 nonogram_input.txt 中的谜题数据，进行求解，并在控制台输出找到的解的数量以及第一个找到的解的网格表示。nonogram_input.txt 文件的格式如下：

<行数> <列数>
<行1提示数字，空格分隔>
<行2提示数字，空格分隔>
...
<行n提示数字，空格分隔>
<列1提示数字，空格分隔>
<列2提示数字，空格分隔>
...
<列m提示数字，空格分隔>

示例 nonogram_input.txt:

5 5
1
3
1 1 1
1 1 1
3
4
1
4
1
3

核心特性与实现细节

• 约束传播: 这是求解器性能的关键。在回溯搜索的每个阶段，求解器都会执行约束传播来自动填充那些可以通过逻辑推理确定的单元格。这大大减少了搜索空间，提高了效率。通过迭代地筛选每行和每列的可能模式，直到不再有新的单元格被确定或发现矛盾。如果某行或某列的所有剩余模式在一个特定单元格处都显示相同的状态（填充或空），则该单元格的状态被确定。
• 回溯搜索: 当约束传播无法进一步确定单元格时，求解器将回溯到第一个未确定的行，尝试为该行选择一个可能的模式，然后递归地继续。如果遇到矛盾，则回溯并尝试该行的下一个模式。
• 模式预生成: 在求解开始前，会预先计算并存储每行和每列所有可能的有效模式。这避免了在回溯过程中重复生成和验证模式，提高了效率。

示例

运行当前的 nonogram_input.txt，会输出：

数织谜题 (行: 25, 列: 25)
---------------------------------
---------------------------------
找到的解数量: 1
---------------------------------
最佳解 (第一个找到的解):
            ██████████    ████  ██████      ████  
██          ██████████      ██████████      ██    
████    ██████████████████  ██  ██████            
████      ████████████████          ██            
          ████████████  ██              ██  ██    
          ████████████████                        
████████████████      ██                  ██      
████████  ██      ██████████      ████    ██  ████
██████████████      ██████████    ██  ████████████
████  ██      ██  ██████████████████            ██
████████      ██    ██    ████████            ████
██████        ██████          ██████        ██████
████████    ██████████████    ██████  ██  ████████
████    ██████████████████  ██████      ██████████
      ████████████████████  ██████        ████████
        ██  ██████    ████████████                
        ██████████    ██████  ██                  
          ██████████████████████    ████          
          ██████  ██  ██      ██████████          
                  ██████      ██████████          
                              ████████            
            ██  ████████      ██████████████      
      ████████  ████  ██  ██      ██████████      
      ██████████████  ██  ██  ██  ████████████    
      ██      ██████  ██  ██  ██  ██████████████