dlx_rs

dlx_rs是一个使用Knuth的Dancing Links (DLX) 算法解决精确覆盖/约束问题的Rust库。

它还提供了针对一些常见精确覆盖问题的特定接口，具体包括

• 任意数独
• N皇后问题
• Aztec diamond
• Pentomino铺砖（待办）
• 图着色（待办）

设置一个通用约束问题

约束问题可以用一系列项目 [i_1,...,i_N] 和选项 [o_1,...,o_M] 来表达。每个选项“覆盖”一些项目，例如选择选项 o1 可能涉及选择项目 i1、i5 和 i7。约束问题是找到一组选项，这些选项恰好覆盖所有项目一次。

这可以用矩阵来表达，其中每个选项覆盖对应条目为 1 的项目，如果为 0 则不覆盖。

     i1  i2  i3  i4  i5  i6  i7
 o1   0   0   1   0   1   0   0
 o2   1   0   0   1   0   0   0
 o3   0   1   1   0   0   0   0
 o4   1   0   0   1   0   1   0
 o5   0   1   0   0   0   0   1
 o6   0   0   0   1   1   0   1

精确覆盖问题是找到一组选项，使得每一列中恰好出现一次 1。

上述情况是通过选择选项 [o_1,o_4,o_5] 来实现的。

解决此问题的代码是

use dlx_rs::Solver;
let mut s = Solver::new(7);
s.add_option("o1",&[3,5])
    .add_option("o2",&[1,5,7])
    .add_option("o3",&[2,3,6])
    .add_option("o4",&[1,4,6])
    .add_option("o5",&[2,7])
    .add_option("o6",&[4,5,7]);

let sol = s.next().unwrap();
assert_eq!(sol,["o4","o5","o1"]);

解决数独

use dlx_rs::Sudoku;
// Define sudoku grid, 0 is unknown number
let sudoku = vec![
    5, 3, 0, 0, 7, 0, 0, 0, 0,
    6, 0, 0, 1, 9, 5, 0, 0, 0,
    0, 9, 8, 0, 0, 0, 0, 6, 0,
    8, 0, 0, 0, 6, 0, 0, 0, 3,
    4, 0, 0, 8, 0, 3, 0, 0, 1,
    7, 0, 0, 0, 2, 0, 0, 0, 6,
    0, 6, 0, 0, 0, 0, 2, 8, 0,
    0, 0, 0, 4, 1, 9, 0, 0, 5,
    0, 0, 0, 0, 8, 0, 0, 7, 9,
];

// Create new sudoku from this grid
let mut s = Sudoku::new_from_input(&sudoku);

let true_solution = vec![
    5, 3, 4, 6, 7, 8, 9, 1, 2,
    6, 7, 2, 1, 9, 5, 3, 4, 8,
    1, 9, 8, 3, 4, 2, 5, 6, 7,
    8, 5, 9, 7, 6, 1, 4, 2, 3,
    4, 2, 6, 8, 5, 3, 7, 9, 1,
    7, 1, 3, 9, 2, 4, 8, 5, 6,
    9, 6, 1, 5, 3, 7, 2, 8, 4,
    2, 8, 7, 4, 1, 9, 6, 3, 5,
    3, 4, 5, 2, 8, 6, 1, 7, 9,
];
// Checks only solution is true solution
let solution = s.next().unwrap();
assert_eq!(solution, true_solution);
assert_eq!(s.next(), None);