sudoku/
sudoku.rs

1//! # Example: Sudoku as Exact Cover
2//!
3//! [Sudoku] can be solved as a pure exact cover problem. There are 729 options
4//! that correspond to the placement of 9 digits in 81 cells. There are 324
5//! items in 4 categories of 81: each of the 81 cells must have 1 digit, each of
6//! the 9 rows must have exactly 1 of each of the 9 digits, each of the 9
7//! columns must have exactly 1 of each of the 9 digits, and each of the 9 3x3
8//! boxes must have exactly 1 of each of the 9 digits. Each option thus covers
9//! exactly 4 items.
10//!
11//! [Sudoku]: <https://en.wikipedia.org/wiki/Sudoku>
12
13use xcov::{DlxBuilder, ExactCoverProblem, MrvExactCoverSearch};
14
15/// Solves a standard sudoku puzzle given as an 81 character `str` (starting
16/// with the top left cell and listed in row-major order). Any character other
17/// than 1-9 is interpreted as a blank.
18#[must_use]
19pub fn solve(puzzle: &str) -> Option<String> {
20    if puzzle.len() != 81 {
21        return None;
22    }
23
24    let mut builder = DlxBuilder::new(9 * 9 * 4, 0);
25    let mut givens = IntSet::<{ (324 + 63) / 64 }>::new();
26
27    // add puzzle givens
28    for (i, ch) in puzzle.chars().enumerate() {
29        let Some(digit) = ch.to_digit(10) else {
30            continue;
31        };
32        if !(1..=9).contains(&digit) {
33            continue;
34        }
35        let digit = (digit - 1) as usize;
36        let option = sudoku_items(i, digit);
37        builder.add_option(&option);
38        for &item in &option {
39            givens.insert(item);
40        }
41    }
42
43    // add all options that do not conflict with givens
44    for cell in 0..81 {
45        for digit in 0..9 {
46            let option = sudoku_items(cell, digit);
47            if option.iter().any(|&i| givens.get(i)) {
48                continue;
49            }
50            builder.add_option(&option);
51        }
52    }
53
54    let mut ec = MrvExactCoverSearch::new(builder.build());
55    ec.search();
56
57    let solution = ec.current_solution()?;
58    let mut result = vec![b' '; 81];
59    const DIGIT_BYTES: &[u8] = b"123456789";
60    for option in solution {
61        let Ok(option): Result<[usize; 4], _> = option.try_into() else {
62            unreachable!()
63        };
64        let [cell, digit] = sudoku_invert_items(&option);
65        result[cell] = DIGIT_BYTES[digit];
66    }
67    Some(String::from_utf8(result).expect("valid utf8 that we constructed ourselves"))
68}
69
70/// Converts a sudoku cell and digit into its 4 items
71fn sudoku_items(cell: usize, digit: usize) -> [usize; 4] {
72    let row = cell / 9;
73    let col = cell % 9;
74    [
75        1 + cell,
76        1 + 81 + row * 9 + digit,
77        1 + 81 * 2 + col * 9 + digit,
78        1 + 81 * 3 + (row / 3 * 3 + col / 3) * 9 + digit,
79    ]
80}
81
82/// Converts 4 items into a sudoku cell and digit
83fn sudoku_invert_items(items: &[usize; 4]) -> [usize; 2] {
84    let digit = (items[1] - 81 - 1) % 9;
85    [items[0] - 1, digit]
86}
87
88/// A set of integers with fixed maximum
89struct IntSet<const N: usize> {
90    bits: [u64; N],
91}
92
93impl<const N: usize> IntSet<N> {
94    fn new() -> Self {
95        Self { bits: [0; N] }
96    }
97
98    fn coords(n: usize) -> (usize, u32) {
99        let i = n / 64;
100        assert!(i < N);
101        let sh = (n % 64).try_into().expect("mod 64 fits in u32");
102        (i, sh)
103    }
104
105    fn insert(&mut self, n: usize) {
106        let (i, sh) = Self::coords(n);
107        self.bits[i] |= 1 << sh;
108    }
109
110    fn get(&self, n: usize) -> bool {
111        let (i, sh) = Self::coords(n);
112        self.bits[i] & 1 << sh != 0
113    }
114}
115
116fn main() {
117    let Some(puzzle) = std::env::args().nth(1) else {
118        panic!("Missing puzzle argument")
119    };
120    if let Some(solution) = solve(&puzzle) {
121        println!("{solution}");
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128
129    #[test]
130    fn puzzle1() {
131        let solution = solve(
132            "769000028000400009000000005005000000090860070280003000008300091002080600000000200",
133        )
134        .unwrap();
135        let expected =
136            "769531428521478369834296715175942836493865172286713954648327591352189647917654283";
137        assert_eq!(solution, expected);
138    }
139}
sudoku/sudoku.rs

sudoku/
sudoku.rs
