algoxcc 0.1.2

A solver for an exact cover with colors problem
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
94

# AlgoXCC

A Rust implementation of Donald Knuth’s algorithm for solving an exact cover with colors problem using the Dancing Cells data structure.

More information about this crate can be found in the [crate
documentation][dox].

[dox]: https://docs.rs/algoxcc

## Exact cover problems

The exact cover problem involves a set of items and a set of options, where each option is a subset of items. A solution to the problem is any subset of options in which all items are represented exactly once.

The generalized exact cover extends this with two types of items:
- primary items, which, as before, must be covered exactly once, and
- secondary items, which must be covered at most once.

The exact cover with colors problem extends this by assigning colors to secondary items within options, allowing a secondary item to be covered by multiple options if they have the same color.

## Usage

### The logic

The inputs to the algorithm are defined in a Problem with:
- primary items: list of unique item names as strings
- secondary items: list of unique item names as strings
- options: list of Options

Where an Option have:
- label: unique label as string identifying an option
- primary items: list of primary items covered by option as strings
- secondary items: list of secondary items covered by option

Secondary items covered by an option are tuples with two elements as strings:
- first element: the secondary item covered by the option
- second element: color used to cover the secondary item

Where a blank color for a secondary item is regarded as a unique color.

With prerequisites:
- A Problem must have at least one primary item.
- All items must be unique (also across primary and secondary items).
- All primary items must be represented in at least one Option.
- All items in an Option must exist in Problem list of items

### The code

To use `algoxcc`, first add this to your `Cargo.toml`:

```toml
[dependencies]
algoxcc = "0.1.1"
```

Next, add this to your crate:

```rust
use algoxcc::{Option, Problem, solve};

fn main() {
    // ...
}
```

## Examples

Solve a problem:

```rust
use algoxcc::{Option, Problem, solve};

// use new_validated constructors if we know input is valid
let problem = Problem::new_validated(
    &vec!["a", "b", "c", "d"],
    &vec![],
    &vec![
        Option::new_validated("o1", &vec!["b"], &vec![]),
        Option::new_validated("o2", &vec!["a"], &vec![]),
        Option::new_validated("o3", &vec!["b", "c"], &vec![]),
        Option::new_validated("o4", &vec!["a", "c", "d"], &vec![]),
    ]
);

let result = solve(&problem, true);
assert!(result.is_ok());
let solutions = result.unwrap();

assert_eq!(1, solutions.count(), "Expect to find 1 solution");
let first = solutions.first().unwrap();
assert_eq!(2, first.len(), "Expect 2 options in solution");
assert_eq!("o1", first[0], "First option is o1");
assert_eq!("o4", first[1], "Second option is o4");

```