# NonogramSolver

**Repository Path**: N_M_L_/nonogram-solver

## Basic Information

- **Project Name**: NonogramSolver
- **Description**: 使用回溯法求解数织问题
- **Primary Language**: C++
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-08-14
- **Last Updated**: 2024-01-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 编译

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)