拼图求解器

关于

通过简单地描述拼图的规则作为约束条件来解决逻辑拼图。这适用于解决整数变量的拼图，如数独、杀手数独、卡卡罗和斑马拼图。

拼图求解器维护每个拼图变量的候选列表。它通过消除会导致矛盾候选并采取在过程中暴露的任何强制移动来解决拼图。重复此操作，直到它陷入困境，此时将执行回溯搜索——将分配一个变量并再次进行候选消除步骤。

示例

在 tests/ 目录中提供了几个示例程序

• 希多 - https://en.wikipedia.org/wiki/Hidato
• 卡卡罗 - https://en.wikipedia.org/wiki/Kakuro
• 杀手数独 - https://en.wikipedia.org/wiki/Killer_sudoku
• 魔术方阵 - https://en.wikipedia.org/wiki/Magic_square
• N-皇后问题 - https://en.wikipedia.org/wiki/Eight_queens_puzzle
• 非ogram（汉捷，Picross） - https://en.wikipedia.org/wiki/Nonogram
• Send More Money - https://en.wikipedia.org/wiki/Verbal_arithmetic
• 数独 - https://en.wikipedia.org/wiki/Sudoku
  • 萨缪拉苏多克
• 斯吉科 - https://en.wikipedia.org/wiki/Sujiko
• 塔库兹（Binairo） - https://en.wikipedia.org/wiki/Takuzu
• xkcd - https://xkcd.com/287/
• 斑马拼图（爱因斯坦难题） - https://en.wikipedia.org/wiki/Zebra_Puzzle

要克隆此仓库，请运行

git clone https://github.com/wangds/puzzle-solver.git

然后使用Cargo构建库并运行测试程序。

cargo test --test sudoku -- --nocapture

基本用法

我们将演示如何解决方程 "SEND + MORE = MONEY"。将Puzzle Solver作为依赖项添加到项目的Cargo.toml文件中

[dependencies]
puzzle-solver = "0.4"

在项目中导入库，例如

extern crate puzzle_solver;

use puzzle_solver::Puzzle;

首先，我们创建一个拼图对象和8个拼图变量 (S,E,N,D,M,O,R,Y)。

let mut puzzle = Puzzle::new();
let vars = puzzle.new_vars_with_candidates_1d(8, &[0,1,2,3,4,5,6,7,8,9]);
let (s, e, n, d) = (vars[0], vars[1], vars[2], vars[3]);
let (m, o, r, y) = (vars[4], vars[5], vars[6], vars[7]);

所有八个拼图变量都被初始化为0到9之间的任意数字。然而，我们知道这些数字不能以0开头，所以我们排除了S = 0和M = 0的选择。

puzzle.remove_candidates(s, &[0]);
puzzle.remove_candidates(m, &[0]);

我们添加了变量应该全部不同的约束

puzzle.all_different(&vars);

我们将方程作为另一个拼图约束来编写

puzzle.equals(
    (1000 * s + 100 * e + 10 * n + d) + (1000 * m + 100 * o + 10 * r + e),
    10000 * m + 1000 * o + 100 * n + 10 * e + y);

然后我们解决它！

let solution = puzzle.solve_any().expect("solution");
assert_eq!(solution[o], 0);
assert_eq!(solution[m], 1);
assert_eq!(solution[y], 2);
assert_eq!(solution[e], 5);
assert_eq!(solution[n], 6);
assert_eq!(solution[d], 7);
assert_eq!(solution[r], 8);
assert_eq!(solution[s], 9);

文档

• 文档.

作者

王大卫