苏多库根

数独谜题求解器和生成器库。

苏多库根可以使用基本策略和穷举法混合找到有效谜题的解决方案。它还可以生成新的最小谜题。这个库是我作为一个 Rust 学习项目构建的。

阅读文档并在 docs.rs/sudokugen 上探索该库

如何使用苏多库根

苏多库根提供了两个结构，用于解析、操作和显示数独棋盘和谜题。结构 Board 允许您从字符串解析棋盘，显示它并尝试解决它。结构 Puzzle 包含与新谜题相关的信息，初始棋盘及其解决方案。

您可以从字符串解析谜题

use sudokugen::Board;

let board: Board = "
     . . . | 4 . . | 8 7 .
     4 . 3 | . . . | . . .
     2 . . | . . 3 | . . 9
     ---------------------
     . . 6 | 2 . . | . . 7
     . . . | 9 . 6 | . . .
     3 . 9 | . 8 . | . . .
     ---------------------
     . . . | . . . | . 4 .
     8 7 2 | 5 . . | . . .
     . . . | 7 2 . | 6 . .
".parse().unwrap();

解析后，您可以使用 Board::solve 函数解决它

board.solve().unwrap();
assert_eq!(
    board,
    "695412873413879526287653419146235987728946135359187264561398742872564391934721658"
    .parse()
    .unwrap()
);

最后，您可以使用 Puzzle::generate 生成新的谜题，在这样做时，您必须指定要生成哪种大小的谜题，BoardSize 可以使这变得非常简单。

use sudokugen::{Puzzle, BoardSize};

let puzzle = Puzzle::generate(BoardSize::NineByNine);

println!("Puzzle\n{}", puzzle.board());
println!("Solution\n{}", puzzle.solution());

这将打印出类似这样的内容

> Puzzle
> . . . . . . . 6 .
> . 1 7 . 4 . . 9 .
> . . . . 9 . 5 3 .
> . . 5 . 7 2 8 . .
> 1 . . . . 8 4 5 .
> . 4 . 9 . . . . .
> 8 7 9 1 2 . . . .
> 4 5 . 8 . . . . .
> . . . . . . . . .
>
> Solution
> 9 2 3 5 8 1 7 6 4
> 5 1 7 6 4 3 2 9 8
> 6 8 4 2 9 7 5 3 1
> 3 6 5 4 7 2 8 1 9
> 1 9 2 3 6 8 4 5 7
> 7 4 8 9 1 5 6 2 3
> 8 7 9 1 2 6 3 4 5
> 4 5 6 8 3 9 1 7 2
> 2 3 1 7 5 4 9 8 6

谜题质量

评估谜题超出了本库的范围。正确评估谜题需要像人类一样解决它们，而一些像人类一样解决谜题的更复杂技术需要进行大量的计算，这些计算并不总是从性能角度获得回报。

尽管如此，生成的谜题通常具有22到26个线索，这使得它们可能位于大多数可用谜题的较难一侧。

它是否快速？

简单回答是，这取决于你的使用场景。`Board::solve` 函数针对 9x9 数独问题进行了优化，在我的 2017 年的 MacBook Pro 上，解决一个难题平均需要 300μs，这意味着每秒可以解决大约 3000 个难题。

`Puzzle::generate` 函数的优化程度较低，并且大量使用了 `Board::solve`，而没有尝试重用重复的计算，因此在我的基准测试中，生成一个新难题需要大约 18ms。

你可以使用 cargo bench 运行自己的基准测试。