dlx-rs 0.0.2

Implementation of dancing links in Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

# dlx_rs

[![Documentation](https://docs.rs/dlx-rs/badge.svg)](https://docs.rs/dlx-rs/)
[![Crates.io](https://img.shields.io/crates/v/dlx-rs.svg)](https://crates.io/crates/dlx-rs)
[![Build status](https://github.com/tveness/dlx-rs/workflows/CI/badge.svg)](https://github.com/tveness/dlx-rs/actions/workflows/rust.yml)

 dlx_rs is a  Rust library for solving exact cover/constraint problems
 problems using Knuth's [Dancing Links](https://en.wikipedia.org/wiki/Dancing_Links) (DLX) algorithm.

 It also provides specific interfaces for some common exact cover problems,
 specifically:

 * arbitrary Sudokus
 * N queens problem
 * Pentomino tilings (TODO)
 * graph colouring (TODO)


 ## Setting up a general constraint problem

 A constraint problem may be expressed in terms of a number of items \[i_1,...,i_N\] and options \[o_1,...,o_M\].
 Each of the options "covers" some of the items, e.g. picking option o1 might involve selecting items i1, i5, and i7.
 The constraint problem is to find a collection of options which cover all of the items exactly once.

 This can be expressed in terms of a matrix, where each option covers the
 items for which the corresponding entry is 1, and doesn't if it is 0
 ```text
      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
 ```
 The exact cover problem is that of finding a collection of options such that
 a 1 appears exactly once in each column.

 This is achieved in the case above by selecting options \[o_1,o_4,o_5\].

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

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

 ```

 ## Solving a Sudoku


 ```rust
 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);
 ```