xcov 0.3.1

Knuth's Algorithm X (featuring dancing links) for solving exact cover problems
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

//! # Example: Sudoku as Exact Cover
//!
//! [Sudoku] can be solved as a pure exact cover problem. There are 729 options
//! that correspond to the placement of 9 digits in 81 cells. There are 324
//! items in 4 categories of 81: each of the 81 cells must have 1 digit, each of
//! the 9 rows must have exactly 1 of each of the 9 digits, each of the 9
//! columns must have exactly 1 of each of the 9 digits, and each of the 9 3x3
//! boxes must have exactly 1 of each of the 9 digits. Each option thus covers
//! exactly 4 items.
//!
//! [Sudoku]: <https://en.wikipedia.org/wiki/Sudoku>

use xcov::{DlxBuilder, ExactCoverProblem, MrvExactCoverSearch};

/// Solves a standard sudoku puzzle given as an 81 character `str` (starting
/// with the top left cell and listed in row-major order). Any character other
/// than 1-9 is interpreted as a blank.
#[must_use]
pub fn solve(puzzle: &str) -> Option<String> {
    if puzzle.len() != 81 {
        return None;
    }

    let mut builder = DlxBuilder::new(9 * 9 * 4, 0);
    let mut givens = IntSet::<{ (324 + 63) / 64 }>::new();

    // add puzzle givens
    for (i, ch) in puzzle.chars().enumerate() {
        let Some(digit) = ch.to_digit(10) else {
            continue;
        };
        if !(1..=9).contains(&digit) {
            continue;
        }
        let digit = (digit - 1) as usize;
        let option = sudoku_items(i, digit);
        builder.add_option(&option);
        for &item in &option {
            givens.insert(item);
        }
    }

    // add all options that do not conflict with givens
    for cell in 0..81 {
        for digit in 0..9 {
            let option = sudoku_items(cell, digit);
            if option.iter().any(|&i| givens.get(i)) {
                continue;
            }
            builder.add_option(&option);
        }
    }

    let mut ec = MrvExactCoverSearch::new(builder.build());
    ec.search();

    let solution = ec.current_solution()?;
    let mut result = vec![b' '; 81];
    const DIGIT_BYTES: &[u8] = b"123456789";
    for option in solution {
        let Ok(option): Result<[usize; 4], _> = option.try_into() else {
            unreachable!()
        };
        let [cell, digit] = sudoku_invert_items(&option);
        result[cell] = DIGIT_BYTES[digit];
    }
    Some(String::from_utf8(result).expect("valid utf8 that we constructed ourselves"))
}

/// Converts a sudoku cell and digit into its 4 items
fn sudoku_items(cell: usize, digit: usize) -> [usize; 4] {
    let row = cell / 9;
    let col = cell % 9;
    [
        1 + cell,
        1 + 81 + row * 9 + digit,
        1 + 81 * 2 + col * 9 + digit,
        1 + 81 * 3 + (row / 3 * 3 + col / 3) * 9 + digit,
    ]
}

/// Converts 4 items into a sudoku cell and digit
fn sudoku_invert_items(items: &[usize; 4]) -> [usize; 2] {
    let digit = (items[1] - 81 - 1) % 9;
    [items[0] - 1, digit]
}

/// A set of integers with fixed maximum
struct IntSet<const N: usize> {
    bits: [u64; N],
}

impl<const N: usize> IntSet<N> {
    fn new() -> Self {
        Self { bits: [0; N] }
    }

    fn coords(n: usize) -> (usize, u32) {
        let i = n / 64;
        assert!(i < N);
        let sh = (n % 64).try_into().expect("mod 64 fits in u32");
        (i, sh)
    }

    fn insert(&mut self, n: usize) {
        let (i, sh) = Self::coords(n);
        self.bits[i] |= 1 << sh;
    }

    fn get(&self, n: usize) -> bool {
        let (i, sh) = Self::coords(n);
        self.bits[i] & 1 << sh != 0
    }
}

fn main() {
    let Some(puzzle) = std::env::args().nth(1) else {
        panic!("Missing puzzle argument")
    };
    if let Some(solution) = solve(&puzzle) {
        println!("{solution}");
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn puzzle1() {
        let solution = solve(
            "769000028000400009000000005005000000090860070280003000008300091002080600000000200",
        )
        .unwrap();
        let expected =
            "769531428521478369834296715175942836493865172286713954648327591352189647917654283";
        assert_eq!(solution, expected);
    }
}