用 Rust 语言编写的终极数独求解器。

$ wget -qO- https://webpbn.com/export.cgi --post-data "id=32480&fmt=nin&go=1" | cargo run

特性

• 解决二进制（空白和白色）和彩色（<32 种颜色）数独；

• 支持多种格式；

  • 自己的基于 TOML 的格式（示例）（具有 ini 功能）；
  • webpbn-s 主要 XML 格式（具有 xml 功能）；
  • 一些其他可以从 webpbn 导出的格式： faase, ish, keen, makhorin, nin, olsak, ss, syro。其中，除了 olsak，其余都只支持黑白谜题；
  • https://nonograms.org 的编码格式。

• 结合多种求解方法，以实现各种谜题类型的速度；

  • 简单谜题按行解决（line + propagation）；
  • 如果谜题无法解决，则开始 probing 阶段，在该阶段对每个未解决的单元格做出一些假设，然后分析它们带来的影响；
  • 如果即使在这里也无法解决谜题，则启用搜索算法：默认情况下使用 backtracking，该方法一次着色一个单元格，然后另一个单元格，以此类推，直到找到解决方案。还有一个选项（具有 sat 功能）：特殊的 SAT 求解器，该求解器使用先前阶段的结果来更有效地探索解决方案空间。

默认情况下，启用了 --features="args std_time logger ini"，但您几乎可以禁用任何功能来加快速度和/或减小二进制的大小。

参数解析

为了支持命令行参数，默认启用了 args 功能。您可以选择禁用它，但这样您将无法设置求解超时或要找到的最大解决方案数。它也可以在将求解器作为库用于其他项目时禁用，例如 这里

超时（std_time）

默认情况下，您可以使用--timeout选项来在达到指定时间限制后停止回溯。您可以禁用此功能（std_time），此时超时选项将被忽略。

日志支持

为了支持格式化的日志，默认启用了由env_logger crate提供的功能。查看它们的简单方法是提供环境变量RUST_LOG=nonogrid=<log_level>。例如，在基准脚本中，使用RUST_LOG=nonogrid=warn来检查求解的中间结果。一如既往，您可以通过在构建时省略--features=logger来禁用此选项。

TOML谜题解析支持

默认情况下，通过功能ini支持我的基于TOML的自定义格式。当将求解器作为库用于其他项目时，可以禁用它，例如此处。

SAT

默认情况下，使用回溯算法解决难题。功能sat允许使用SAT求解器来完成这项工作。使用此选项可以显著加快大多数难题的解决速度。

最新的基准测试显示，SAT求解器对最困难的webpbn难题非常有效（实际上，只有两个难题的解决时间超过一小时：25820和26520）。

XML谜题解析支持

通过功能xml支持Jan Wolter的XML格式。您可以通过构建时使用--features=xml来启用它。

彩色非ogram

您可以通过启用功能colors来允许使用真实终端颜色打印彩色非ogram。

wget -qO- https://webpbn.com/export.cgi --post-data "fmt=olsak&go=1&id=2192" |
cargo run --no-default-features --features=colors

HTTP客户端

可以使用reqwest库自动从互联网下载已解决的谜题，但这需要太多的依赖项，并会增加编译时间，因此默认情况下是可选的。启用它非常简单：

cargo run --features=web,xml -- --webpbn 5933

多线程

默认情况下，求解器和所有算法都是单线程的。要在多线程环境中使用求解器的结构，请提供threaded功能。本质上，此功能将替换所有Rc/RefCell的实例为Arc/RwLock。

探测调整

当'逻辑'求解（line/propagation）陷入僵局时，会启动probing阶段，尝试每个未解决的单元格的每个变体。它通过计算每个单元格的优先级来实现这一点。

P = N + R + C,

where 0<=N<=4 - number of neighbours which are solved cells or puzzle edges.
For example, the cell which has all 4 heighboring cells solved, has N = 4.
The upper left cell of the puzzle without any neighbours solved, has N = 2,
since it has 2 edges of the puzzle.

0<=R<=1 - row solution rate, the ratio of solved cells in the row to total number of cells (width)
0<=C<=1 - column solution rate, the ratio of solved cells in the column to total number of cells (height)

默认情况下，检查所有具有P>=0的单元格，但您可以通过指定LOW_PRIORITY环境变量来自定义阈值。

例如，运行

LOW_PRIORITY=1 nonogrid puzzles/6574.xml

可以通过跳过具有P < 1的单元格的探测来比标准方式快3倍地解决问题。

使用示例

从https://webpbn.com（XML格式）解决本地保存的谜题

cargo build --features="xml"

# solve puzzle https://webpbn.com/2992
wget 'https://webpbn.com/XMLpuz.cgi?id=2992' -O 2992.xml
target/debug/nonogrid 2992.xml

# with pipe
wget -qO- 'https://webpbn.com/XMLpuz.cgi?id=2992' | target/debug/nonogrid

使用嵌入的HTTP客户端从https://webpbn.com解决谜题

cargo build --features="web,xml"

# solve puzzle https://webpbn.com/5933
target/debug/nonogrid -w 5933

从https://nonograms.org解决本地保存的谜题

cargo build

# solve puzzle https://webpbn.com/2992
wget -qO- 'https://www.nonograms.org/nonograms/i/2581' | grep 'var d=' > 2581.js
target/debug/nonogrid 2581.js

# with pipe
wget -qO- 'https://www.nonograms.org/nonograms/i/2581' | target/debug/nonogrid

使用嵌入的HTTP客户端从https://nonograms.org解决谜题

cargo build --features="web"

# solve puzzle https://www.nonograms.org/nonograms/i/13588
target/debug/nonogrid -o 13588

# solve puzzle https://www.nonograms.org/nonograms2/i/10270
target/debug/nonogrid -o 10270

解决其他格式

TOML格式

cargo build

target/debug/nonogrid examples/hello.toml

Webpbn的可导出格式

wget -qO- https://webpbn.com/export.cgi --post-data "fmt=syro&go=1&id=2040" |
cargo run --no-default-features

开发

查看INFO日志并在panic时展开回溯

RUST_BACKTRACE=1 RUST_LOG=nonogrid=info cargo run -- examples/hello.toml