langford_pairs/
langford_pairs.rs

1//! The following program finds all ways to put $2n$ numbers $\\{1,1,2,2,\dots,n,n\\}$
2//! into $2n$ slots $s_1,\dots,s_{2n}$ so that there are exactly $i$ numbers
3//! between the two appearances of $i$, for all $1\le i\le n$. This task is
4//! known as _Langford's problem_, since it was first described by C. D. Langford
5//! [[_The Mathematical Gazette_ **42** (October 1958), 228][mathgaz]]. Its encoding
6//! as an exact cover problem is well explained in D. E. Knuth's book
7//! [_The Art of Computer Programming_ **4B** (2022)][taocp4b], Part 2, page 70.
8//! His approach can be summarized as follows:
9//!
10//! Regard the $n$ values of $i$ and the $2n$ slots as the items to be covered.
11//! Then the legal options for permuting the first $n$ integers into a Langford
12//! sequence are $`i\\;s_j\\;s_k'$ for $1\le i\le n$, $1\le j<k\le 2n$, and
13//! $k=i+j+1$. In this way the distance between slots $s_j$ and $s_k$ for item
14//! $i$ is $k-j=i+j+1-j=i+1$, as desired.
15//!
16//! [mathgaz]: https://www.cambridge.org/core/journals/mathematical-gazette/article/abs/problem/557F7BBB739F5B3E0D152C270642B102
17//! [taocp4b]: https://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4
18
19use exact_covers::{DlSolver, Solver};
20use std::ops::ControlFlow;
21
22/// A Langford pair can exist only when $n$ is congruent to 0 or 3 modulo 4.
23/// This is because the two entries of an odd number must either both go in
24/// even or in odd positions, while the entries of an even number must fall
25/// in positions of different parity. There are $\lfloor n/2\rfloor$ even
26/// numbers in $\\{1,\dots,n\\}$, so $n-\lfloor n/2\rfloor=\lceil n/2\rceil$
27/// positions of each parity remain available for the odd numbers. Since these
28/// come in pairs that occupy positions of the same parity, $\lceil n/2\rceil$
29/// must be an even number. This happens only if $n\equiv 0$ or $n\equiv 3$
30/// (modulo 4).
31const N: usize = 15;
32
33#[derive(Eq, PartialEq, Copy, Clone, Ord, PartialOrd)]
34enum Item {
35    Number(usize),
36    Slot(usize),
37}
38
39fn main() {
40    let numbers = (1..=N).map(Item::Number);
41    let slots = (1..=2 * N).map(Item::Slot);
42    let items: Vec<_> = numbers.chain(slots).collect();
43
44    let mut solver: DlSolver<Item, ()> = DlSolver::new(&items, &[]);
45    for i in 1..=N {
46        // Optimization: half of the Langford pairs for a given value of $n$
47        // are the reverses of the others. Reduce the search space by placing
48        // the first 1 in position $1\le s_j<n$.
49        let first_slot_range = 1..if i == 1 { N } else { 2 * N - i };
50        for j in first_slot_range {
51            let k = i + j + 1;
52            let items = [Item::Number(i), Item::Slot(j), Item::Slot(k)];
53            solver.add_option(items, []);
54        }
55    }
56
57    let mut options = Vec::new();
58    solver.solve(|mut solution| {
59        assert_eq!(solution.option_count(), N);
60        // Convert the set of options into the corresponding placement.
61        let mut placement = [0usize; 2 * N];
62        while solution.next(&mut options) {
63            // Sort the items in `options` so we can perform pattern matching.
64            // Note that `Item` derives `Ord`, so item variants are ordered by
65            // their discriminants: numbers come before slots.
66            options.sort();
67            if let &[(&Item::Number(i), _), (&Item::Slot(j), _), (&Item::Slot(k), _)] = &options[..]
68            {
69                placement[j - 1] = i;
70                placement[k - 1] = i;
71            } else {
72                unreachable!("ordered option should match (number, slot, slot) pattern");
73            }
74        }
75        // Print the found Langford sequence, and its reverse.
76        println!("{:?}", placement);
77        placement.reverse();
78        println!("{:?}", placement);
79        ControlFlow::Continue(())
80    });
81}
langford_pairs/langford_pairs.rs

langford_pairs/
langford_pairs.rs
