sudoku/
lib.rs

1//! # zero-alloc-sudoku
2//!
3//! A zero-heap-allocation, sub-microsecond Sudoku solver for Rust.
4//!
5//! ## Algorithm
6//!
7//! The solver combines two techniques:
8//!
9//! - **9-bit bitboard constraint propagation** — each of the 27 constraint
10//!   groups (9 rows + 9 columns + 9 boxes) is represented as a `u16` bitmask
11//!   where bit *k* is set when digit *k+1* has been placed. The available
12//!   digits for any empty cell are computed with a single bitwise NOT and AND
13//!   in `O(1)`.
14//!
15//! - **MRV (Minimum Remaining Values) heuristic backtracking** — at each
16//!   recursive step the empty cell with the fewest legal digits is chosen
17//!   first. This prunes the search tree dramatically on hard puzzles.
18//!
19//! The entire solver state is a single `#[repr(C, align(64))]` struct (~216 bytes)
20//! that fits within two cache lines, eliminating cache misses during search.
21//!
22//! ## Quick start
23//!
24//! ```rust
25//! use sudoku::Sudoku;
26//!
27//! let mut sudoku: Sudoku = "800000000003600000070090200050007000\
28//!                           000045700000100030001000068008500010\
29//!                           090000400"
30//!     .parse()
31//!     .expect("valid puzzle");
32//!
33//! assert!(sudoku.solve());
34//! println!("{}", sudoku);
35//! ```
36//!
37//! ## Performance
38//!
39//! On a modern x86-64 CPU with `--release` and `target-cpu=native`:
40//!
41//! | Puzzle          | Average (ns) | Throughput        |
42//! |-----------------|--------------|-------------------|
43//! | Al Escargot     | ~400 ns      | ~2 500 000 /s     |
44//! | Hardest 2012    | ~600 ns      | ~1 600 000 /s     |
45//! | Platinum Blonde | ~350 ns      | ~2 800 000 /s     |
46
47#![warn(missing_docs)]
48#![allow(clippy::needless_range_loop)]
49
50use std::fmt;
51use std::str::FromStr;
52
53// ── Internal lookup tables (generated at compile time) ────────────────────
54
55/// Bitmask with all 9 digit-bits set: `0b1_1111_1111 == 0x1FF == 511`.
56pub(crate) const FULL_MASK: u16 = 0x1FF;
57
58pub(crate) const ROW: [u8; 81] = generate_row();
59pub(crate) const COL: [u8; 81] = generate_col();
60pub(crate) const BOX: [u8; 81] = generate_box();
61
62const fn generate_row() -> [u8; 81] {
63    let mut a = [0u8; 81];
64    let mut i = 0;
65    while i < 81 { a[i] = (i / 9) as u8; i += 1; }
66    a
67}
68const fn generate_col() -> [u8; 81] {
69    let mut a = [0u8; 81];
70    let mut i = 0;
71    while i < 81 { a[i] = (i % 9) as u8; i += 1; }
72    a
73}
74const fn generate_box() -> [u8; 81] {
75    let mut a = [0u8; 81];
76    let mut i = 0;
77    while i < 81 { a[i] = ((i / 27) * 3 + (i % 9 / 3)) as u8; i += 1; }
78    a
79}
80
81// ── Error type ────────────────────────────────────────────────────────────
82
83/// Error returned when a puzzle string cannot be parsed into a valid [`Sudoku`].
84///
85/// # Examples
86///
87/// ```rust
88/// use sudoku::{Sudoku, ParseError};
89///
90/// // Wrong length
91/// let err = "12345".parse::<Sudoku>().unwrap_err();
92/// assert_eq!(err, ParseError::InvalidLength(5));
93///
94/// // Invalid character
95/// let s = "x".repeat(1) + &"0".repeat(80);
96/// let err = s.parse::<Sudoku>().unwrap_err();
97/// assert_eq!(err, ParseError::InvalidCharacter { position: 0, ch: 'x' });
98/// ```
99#[derive(Debug, Clone, PartialEq, Eq)]
100pub enum ParseError {
101    /// The string did not contain exactly 81 characters.
102    InvalidLength(usize),
103    /// A character other than `'0'`–`'9'` was found.
104    InvalidCharacter {
105        /// Zero-based index in the input string.
106        position: usize,
107        /// The offending character.
108        ch: char,
109    },
110    /// A digit appears more than once in the same row, column, or 3×3 box.
111    DuplicateDigit {
112        /// Zero-based cell index (0 = top-left, 80 = bottom-right).
113        position: usize,
114        /// The duplicated digit (1–9).
115        digit: u8,
116    },
117}
118
119impl fmt::Display for ParseError {
120    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
121        match self {
122            ParseError::InvalidLength(n) =>
123                write!(f, "puzzle must be 81 characters, got {}", n),
124            ParseError::InvalidCharacter { position, ch } =>
125                write!(f, "invalid character {:?} at position {}", ch, position),
126            ParseError::DuplicateDigit { position, digit } =>
127                write!(f, "digit {} at position {} conflicts with its row/column/box",
128                       digit, position),
129        }
130    }
131}
132
133impl std::error::Error for ParseError {}
134
135// ── Core solver ───────────────────────────────────────────────────────────
136
137/// A zero-allocation Sudoku board and solver.
138///
139/// The entire state (cells + bitboard constraints + empty-cell work list) fits
140/// in a single `#[repr(C, align(64))]` struct (~216 bytes), keeping all working
141/// data in L1 cache throughout the solve.
142///
143/// # Examples
144///
145/// Parse and solve:
146///
147/// ```rust
148/// use sudoku::Sudoku;
149///
150/// let mut sudoku: Sudoku = "530070000600195000098000060800060003\
151///                           400803001700020006060000280000419005\
152///                           000080079"
153///     .parse()
154///     .unwrap();
155///
156/// assert!(sudoku.solve());
157/// // Every cell is now filled with a valid digit.
158/// assert!(sudoku.cells().iter().all(|&v| v >= 1 && v <= 9));
159/// ```
160///
161/// Detect an invalid puzzle:
162///
163/// ```rust
164/// use sudoku::{Sudoku, ParseError};
165///
166/// let result = "119000000000000000000000000000000000\
167///               000000000000000000000000000000000000\
168///               00000000000".parse::<Sudoku>();
169/// assert!(result.is_err());
170/// ```
171#[repr(C, align(64))]
172#[derive(Clone, Copy)]
173pub struct Sudoku {
174    /// Raw cell values: `0` = empty, `1`–`9` = placed digit.
175    pub cells: [u8; 81],
176    rows:  [u16; 9],
177    cols:  [u16; 9],
178    boxes: [u16; 9],
179    empty: [u8; 81],
180}
181
182impl Sudoku {
183    // ── Construction ──────────────────────────────────────────────────
184
185    /// Parses a Sudoku from a string of exactly 81 ASCII digits (`'0'` = empty).
186    ///
187    /// Prefer the [`FromStr`] implementation (`.parse()`) in new code;
188    /// this method is kept for backwards compatibility.
189    ///
190    /// Returns `None` on any parse error. Use `.parse::<Sudoku>()` to
191    /// obtain a detailed [`ParseError`] instead.
192    ///
193    /// # Examples
194    ///
195    /// ```rust
196    /// use sudoku::Sudoku;
197    ///
198    /// let puzzle = "0".repeat(81);
199    /// assert!(Sudoku::from_string(&puzzle).is_some());
200    /// assert!(Sudoku::from_string("short").is_none());
201    /// ```
202    pub fn from_string(s: &str) -> Option<Self> {
203        s.parse().ok()
204    }
205
206    // ── Accessors ─────────────────────────────────────────────────────
207
208    /// Returns a reference to the 81-element cell array.
209    ///
210    /// Each element is `0` (empty) or a digit `1`–`9`.
211    ///
212    /// # Examples
213    ///
214    /// ```rust
215    /// use sudoku::Sudoku;
216    ///
217    /// let sudoku: Sudoku = "0".repeat(81).parse().unwrap();
218    /// assert_eq!(sudoku.cells().len(), 81);
219    /// assert!(sudoku.cells().iter().all(|&v| v == 0));
220    /// ```
221    #[inline]
222    pub fn cells(&self) -> &[u8; 81] {
223        &self.cells
224    }
225
226    /// Returns `true` if every cell has been filled (no zeros remain).
227    ///
228    /// # Examples
229    ///
230    /// ```rust
231    /// use sudoku::Sudoku;
232    ///
233    /// let mut s: Sudoku = "0".repeat(81).parse().unwrap();
234    /// assert!(!s.is_solved());
235    /// s.solve();
236    /// assert!(s.is_solved());
237    /// ```
238    #[inline]
239    pub fn is_solved(&self) -> bool {
240        self.cells.iter().all(|&v| v != 0)
241    }
242
243    /// Returns the digit at row `r`, column `c` (both 0-indexed).
244    ///
245    /// Returns `0` if the cell is empty.
246    ///
247    /// # Panics
248    ///
249    /// Panics if `r >= 9` or `c >= 9`.
250    ///
251    /// # Examples
252    ///
253    /// ```rust
254    /// use sudoku::Sudoku;
255    ///
256    /// let s: Sudoku = "530070000600195000098000060800060003\
257    ///                  400803001700020006060000280000419005\
258    ///                  000080079".parse().unwrap();
259    /// assert_eq!(s.get(0, 0), 5);
260    /// assert_eq!(s.get(0, 1), 3);
261    /// assert_eq!(s.get(0, 2), 0); // empty
262    /// ```
263    #[inline]
264    pub fn get(&self, r: usize, c: usize) -> u8 {
265        assert!(r < 9 && c < 9, "row and column must be 0..9");
266        self.cells[r * 9 + c]
267    }
268
269    // ── Solver ────────────────────────────────────────────────────────
270
271    /// Solves the puzzle **in place** using MRV backtracking with bitboard
272    /// constraint propagation.
273    ///
274    /// Returns `true` if a solution was found (cells are updated), or `false`
275    /// if the puzzle has no solution (cells are **unchanged**).
276    ///
277    /// # Examples
278    ///
279    /// ```rust
280    /// use sudoku::Sudoku;
281    ///
282    /// // Arto Inkala's "AI Sudoku" (2010) — rated world's hardest at the time.
283    /// let mut s: Sudoku = "800000000003600000070090200050007000\
284    ///                      000045700000100030001000068008500010\
285    ///                      090000400".parse().unwrap();
286    ///
287    /// assert!(s.solve());
288    /// assert!(s.is_solved());
289    /// ```
290    pub fn solve(&mut self) -> bool {
291        let mut n = 0usize;
292        for i in 0..81 {
293            if self.cells[i] == 0 {
294                self.empty[n] = i as u8;
295                n += 1;
296            }
297        }
298        self.solve_recursive(n)
299    }
300
301    #[inline(always)]
302    fn get_mask(&self, idx: usize) -> u16 {
303        debug_assert!(idx < 81);
304        unsafe {
305            let r = *ROW.get_unchecked(idx) as usize;
306            let c = *COL.get_unchecked(idx) as usize;
307            let b = *BOX.get_unchecked(idx) as usize;
308            debug_assert!(r < 9 && c < 9 && b < 9);
309            !(*self.rows.get_unchecked(r)
310                | *self.cols.get_unchecked(c)
311                | *self.boxes.get_unchecked(b))
312                & FULL_MASK
313        }
314    }
315
316    fn solve_recursive(&mut self, num_empty: usize) -> bool {
317        if num_empty == 0 { return true; }
318
319        let mut best_i = 0;
320        let mut min_c = 10u32;
321        let mut best_mask = 0u16;
322
323        for i in 0..num_empty {
324            debug_assert!(i < 81);
325            let idx = unsafe { *self.empty.get_unchecked(i) as usize };
326            debug_assert!(idx < 81);
327            let mask = self.get_mask(idx);
328            let count = mask.count_ones();
329            if count == 0 { return false; }
330            if count < min_c {
331                min_c = count;
332                best_i = i;
333                best_mask = mask;
334                if count == 1 { break; }
335            }
336        }
337
338        let idx = self.empty[best_i] as usize;
339        let last = num_empty - 1;
340        let saved = self.empty[last];
341        self.empty[best_i] = saved;
342
343        let mut m = best_mask;
344        while m != 0 {
345            let bit = m & m.wrapping_neg();
346            m ^= bit;
347            let digit = (bit.trailing_zeros() + 1) as u8;
348            let r = ROW[idx] as usize;
349            let c = COL[idx] as usize;
350            let b = BOX[idx] as usize;
351
352            self.cells[idx] = digit;
353            self.rows[r]  |= bit;
354            self.cols[c]  |= bit;
355            self.boxes[b] |= bit;
356
357            if self.solve_recursive(last) { return true; }
358
359            self.rows[r]  &= !bit;
360            self.cols[c]  &= !bit;
361            self.boxes[b] &= !bit;
362        }
363
364        self.cells[idx] = 0;
365        self.empty[best_i] = idx as u8;
366        self.empty[last] = saved;
367        false
368    }
369
370    // ── Formatting helpers ────────────────────────────────────────────
371
372    /// Returns the board as an 81-character string of digits (`'0'` = empty).
373    ///
374    /// # Examples
375    ///
376    /// ```rust
377    /// use sudoku::Sudoku;
378    ///
379    /// let puzzle = "0".repeat(81);
380    /// let s: Sudoku = puzzle.parse().unwrap();
381    /// assert_eq!(s.to_digit_string(), puzzle);
382    /// ```
383    pub fn to_digit_string(&self) -> String {
384        self.cells.iter().map(|&v| (v + b'0') as char).collect()
385    }
386
387    /// Prints the board as a human-readable 9×9 grid with box dividers to stdout.
388    pub fn print_grid(&self) {
389        for row in 0..9 {
390            if row % 3 == 0 && row != 0 {
391                println!("------+-------+------");
392            }
393            for col in 0..9 {
394                if col % 3 == 0 && col != 0 { print!("| "); }
395                let v = self.cells[row * 9 + col];
396                if v == 0 { print!(". "); } else { print!("{} ", v); }
397            }
398            println!();
399        }
400    }
401}
402
403// ── Trait implementations ─────────────────────────────────────────────────
404
405impl FromStr for Sudoku {
406    type Err = ParseError;
407
408    /// Parses a Sudoku from a string of exactly 81 ASCII digits.
409    ///
410    /// # Errors
411    ///
412    /// Returns [`ParseError::InvalidLength`] if `s.len() != 81`,
413    /// [`ParseError::InvalidCharacter`] for non-digit bytes, or
414    /// [`ParseError::DuplicateDigit`] if any digit appears twice in a
415    /// row, column, or 3×3 box.
416    ///
417    /// # Examples
418    ///
419    /// ```rust
420    /// use sudoku::Sudoku;
421    ///
422    /// let s: Sudoku = "800000000003600000070090200050007000\
423    ///                  000045700000100030001000068008500010\
424    ///                  090000400".parse().unwrap();
425    /// assert_eq!(s.get(0, 0), 8);
426    /// ```
427    fn from_str(s: &str) -> Result<Self, Self::Err> {
428        if s.len() != 81 {
429            return Err(ParseError::InvalidLength(s.len()));
430        }
431        let mut board = Sudoku {
432            cells: [0; 81],
433            rows:  [0; 9],
434            cols:  [0; 9],
435            boxes: [0; 9],
436            empty: [0; 81],
437        };
438        for (i, ch) in s.bytes().enumerate() {
439            let val = match ch {
440                b'0'..=b'9' => ch - b'0',
441                _ => return Err(ParseError::InvalidCharacter {
442                    position: i,
443                    ch: ch as char,
444                }),
445            };
446            if val != 0 {
447                let bit: u16 = 1 << (val - 1);
448                let r = ROW[i] as usize;
449                let c = COL[i] as usize;
450                let b = BOX[i] as usize;
451                if (board.rows[r] | board.cols[c] | board.boxes[b]) & bit != 0 {
452                    return Err(ParseError::DuplicateDigit { position: i, digit: val });
453                }
454                board.cells[i] = val;
455                board.rows[r]  |= bit;
456                board.cols[c]  |= bit;
457                board.boxes[b] |= bit;
458            }
459        }
460        Ok(board)
461    }
462}
463
464/// Displays the board as an 81-character digit string (same as [`to_digit_string`]).
465///
466/// [`to_digit_string`]: Sudoku::to_digit_string
467///
468/// # Examples
469///
470/// ```rust
471/// use sudoku::Sudoku;
472///
473/// let s: Sudoku = "0".repeat(81).parse().unwrap();
474/// assert_eq!(format!("{}", s), "0".repeat(81));
475/// ```
476impl fmt::Display for Sudoku {
477    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
478        for &v in &self.cells {
479            write!(f, "{}", v)?;
480        }
481        Ok(())
482    }
483}
484
485/// Formats the board as a compact digit string (identical to [`Display`]).
486impl fmt::Debug for Sudoku {
487    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
488        write!(f, "Sudoku(\"{}\")", self)
489    }
490}
491
492impl PartialEq for Sudoku {
493    fn eq(&self, other: &Self) -> bool {
494        self.cells == other.cells
495    }
496}
497
498impl Eq for Sudoku {}
499
500// ── Default: empty (all-zeros) board ──────────────────────────────────────
501
502/// Creates an empty board where every cell is unset.
503///
504/// # Examples
505///
506/// ```rust
507/// use sudoku::Sudoku;
508///
509/// let mut s = Sudoku::default();
510/// assert!(!s.is_solved());
511/// assert!(s.solve()); // any valid completion exists
512/// ```
513impl Default for Sudoku {
514    fn default() -> Self {
515        Sudoku {
516            cells: [0; 81],
517            rows:  [0; 9],
518            cols:  [0; 9],
519            boxes: [0; 9],
520            empty: [0; 81],
521        }
522    }
523}
524
525// ============================================================
526//  CORRECTNESS PROOF — TEST SUITE  (L1–L5)
527// ============================================================
528#[cfg(test)]
529mod tests {
530    use super::*;
531
532    // ── Internal helpers ────────────────────────────────────────────
533
534    impl Sudoku {
535        fn bitboard_matches_cells(&self) -> bool {
536            let mut er = [0u16; 9];
537            let mut ec = [0u16; 9];
538            let mut eb = [0u16; 9];
539            for i in 0..81 {
540                let v = self.cells[i];
541                if v != 0 {
542                    let bit = 1u16 << (v - 1);
543                    er[ROW[i] as usize] |= bit;
544                    ec[COL[i] as usize] |= bit;
545                    eb[BOX[i] as usize] |= bit;
546                }
547            }
548            self.rows == er && self.cols == ec && self.boxes == eb
549        }
550    }
551
552    fn is_valid_solution(cells: &[u8; 81]) -> bool {
553        for r in 0..9 {
554            let mut m = 0u16;
555            for c in 0..9 {
556                let v = cells[r * 9 + c];
557                if v == 0 || v > 9 { return false; }
558                let bit = 1u16 << (v - 1);
559                if m & bit != 0 { return false; }
560                m |= bit;
561            }
562            if m != FULL_MASK { return false; }
563        }
564        for c in 0..9 {
565            let mut m = 0u16;
566            for r in 0..9 {
567                let v = cells[r * 9 + c];
568                let bit = 1u16 << (v - 1);
569                if m & bit != 0 { return false; }
570                m |= bit;
571            }
572            if m != FULL_MASK { return false; }
573        }
574        for br in 0..3 { for bc in 0..3 {
575            let mut m = 0u16;
576            for dr in 0..3 { for dc in 0..3 {
577                let v = cells[(br * 3 + dr) * 9 + (bc * 3 + dc)];
578                let bit = 1u16 << (v - 1);
579                if m & bit != 0 { return false; }
580                m |= bit;
581            }}
582            if m != FULL_MASK { return false; }
583        }}
584        true
585    }
586
587    fn assert_clues_preserved(puzzle: &str, s: &Sudoku) {
588        for (i, ch) in puzzle.bytes().enumerate() {
589            if ch != b'0' {
590                assert_eq!(s.cells[i], ch - b'0',
591                    "Clue at pos {} (row {}, col {}) overwritten", i, i/9, i%9);
592            }
593        }
594    }
595
596    // ── L1: Constant & table integrity ──────────────────────────────
597
598    #[test]
599    fn l1_full_mask_is_9_bit_all_ones() {
600        assert_eq!(FULL_MASK, 0b1_1111_1111);
601        assert_eq!(FULL_MASK, 0x1FF);
602        assert_eq!(FULL_MASK, 511u16);
603        assert_eq!(FULL_MASK.count_ones(), 9);
604        assert_eq!(FULL_MASK & !0x1FF, 0);
605    }
606
607    #[test]
608    fn l1_row_table_is_correct() {
609        for i in 0..81usize { assert_eq!(ROW[i], (i / 9) as u8); assert!(ROW[i] < 9); }
610        let mut c = [0u8; 9]; for &r in ROW.iter() { c[r as usize] += 1; }
611        assert_eq!(c, [9u8; 9]);
612    }
613
614    #[test]
615    fn l1_col_table_is_correct() {
616        for i in 0..81usize { assert_eq!(COL[i], (i % 9) as u8); assert!(COL[i] < 9); }
617        let mut c = [0u8; 9]; for &v in COL.iter() { c[v as usize] += 1; }
618        assert_eq!(c, [9u8; 9]);
619    }
620
621    #[test]
622    fn l1_box_table_is_correct() {
623        for i in 0..81usize {
624            assert_eq!(BOX[i], ((i / 27) * 3 + (i % 9 / 3)) as u8);
625            assert!(BOX[i] < 9);
626        }
627        let mut c = [0u8; 9]; for &b in BOX.iter() { c[b as usize] += 1; }
628        assert_eq!(c, [9u8; 9]);
629    }
630
631    #[test]
632    fn l1_row_col_box_partition_is_consistent() {
633        for i in 0..81usize {
634            let r = ROW[i] as usize; let c = COL[i] as usize; let b = BOX[i] as usize;
635            assert_eq!(r * 9 + c, i);
636            assert_eq!(b, (r / 3) * 3 + (c / 3));
637        }
638    }
639
640    // ── L2: Input validation ─────────────────────────────────────────
641
642    #[test]
643    fn l2_rejects_row_duplicate() {
644        let s = "110000000000000000000000000000000000000000000000000000000000000000000000000000000";
645        assert!(s.parse::<Sudoku>().is_err());
646    }
647
648    #[test]
649    fn l2_rejects_col_duplicate() {
650        let s = "000050000000050000000000000000000000000000000000000000000000000000000000000000000";
651        assert!(s.parse::<Sudoku>().is_err());
652    }
653
654    #[test]
655    fn l2_rejects_box_duplicate() {
656        // Box 4 (centre): 3 at (3,3) and (5,5)
657        let s = "000000000000000000000000000000300000000000000000003000000000000000000000000000000";
658        assert!(s.parse::<Sudoku>().is_err());
659    }
660
661    #[test]
662    fn l2_parse_error_variants() {
663        assert_eq!("12345".parse::<Sudoku>().unwrap_err(), ParseError::InvalidLength(5));
664        let non_digit = format!("x{}", "0".repeat(80));
665        assert_eq!(non_digit.parse::<Sudoku>().unwrap_err(),
666            ParseError::InvalidCharacter { position: 0, ch: 'x' });
667        let dup_row = format!("11{}", "0".repeat(79));
668        assert!(matches!(dup_row.parse::<Sudoku>().unwrap_err(),
669            ParseError::DuplicateDigit { digit: 1, .. }));
670    }
671
672    #[test]
673    fn l2_rejects_wrong_length() {
674        assert!("0".repeat(80).parse::<Sudoku>().is_err());
675        assert!("0".repeat(82).parse::<Sudoku>().is_err());
676    }
677
678    #[test]
679    fn l2_accepts_all_zeros() {
680        assert!("0".repeat(81).parse::<Sudoku>().is_ok());
681    }
682
683    // ── L3: Output soundness ─────────────────────────────────────────
684
685    #[test]
686    fn l3_al_escargot_solution_is_valid() {
687        let p = "100007060900020008080500000000305070020010000800000400004000000000460010030900005";
688        let mut s: Sudoku = p.parse().unwrap();
689        assert!(s.solve());
690        assert!(is_valid_solution(&s.cells));
691        assert_clues_preserved(p, &s);
692        assert!(s.is_solved());
693    }
694
695    #[test]
696    fn l3_hardest_2012_solution_is_valid() {
697        let p = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";
698        let mut s: Sudoku = p.parse().unwrap();
699        assert!(s.solve());
700        assert!(is_valid_solution(&s.cells));
701        assert_clues_preserved(p, &s);
702        assert!(s.is_solved());
703    }
704
705    #[test]
706    fn l3_platinum_blonde_solution_is_valid() {
707        let p = "000000012000000003002300400001800005060000070004000600000050090000200001000000000";
708        let mut s: Sudoku = p.parse().unwrap();
709        assert!(s.solve());
710        assert!(is_valid_solution(&s.cells));
711        assert_clues_preserved(p, &s);
712        assert!(s.is_solved());
713    }
714
715    // ── L4: State integrity ──────────────────────────────────────────
716
717    #[test]
718    fn l4_bitboard_consistent_after_parse() {
719        let s: Sudoku = "800000000003600000070090200050007000000045700000100030001000068008500010090000400"
720            .parse().unwrap();
721        assert!(s.bitboard_matches_cells());
722    }
723
724    #[test]
725    fn l4_bitboard_consistent_after_solve() {
726        let p = "100007060900020008080500000000305070020010000800000400004000000000460010030900005";
727        let mut s: Sudoku = p.parse().unwrap();
728        s.solve();
729        assert!(s.bitboard_matches_cells());
730    }
731
732    #[test]
733    fn l4_already_solved_board_returns_true() {
734        let solved = "123456789456789123789123456231564897564897231897231564312645978645978312978312645";
735        let mut s: Sudoku = solved.parse().unwrap();
736        let before = s.cells;
737        assert!(s.solve());
738        assert_eq!(s.cells, before);
739    }
740
741    #[test]
742    fn l4_unsolvable_board_returns_false_and_preserves_clues() {
743        // Cell (0,0) needs 9 (row) but col-0 already has 9 → impossible
744        let p = "012345678900000000000000000000000000000000000000000000000000000000000000000000000";
745        let mut s: Sudoku = p.parse().unwrap();
746        let snap: Vec<u8> = p.bytes().enumerate()
747            .filter(|(_, b)| *b != b'0').map(|(i, _)| s.cells[i]).collect();
748        assert!(!s.solve());
749        for (k, (i, _)) in p.bytes().enumerate().filter(|(_, b)| *b != b'0').enumerate() {
750            assert_eq!(s.cells[i], snap[k]);
751        }
752    }
753
754    #[test]
755    fn l4_solve_is_deterministic() {
756        let p = "000000012000000003002300400001800005060000070004000600000050090000200001000000000";
757        let mut a: Sudoku = p.parse().unwrap();
758        let mut b: Sudoku = p.parse().unwrap();
759        a.solve(); b.solve();
760        assert_eq!(a.cells, b.cells);
761    }
762
763    #[test]
764    fn l4_display_round_trips() {
765        let p = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";
766        let s: Sudoku = p.parse().unwrap();
767        assert_eq!(format!("{}", s), p);
768        assert_eq!(s.to_digit_string(), p);
769    }
770
771    #[test]
772    fn l4_default_is_empty_board() {
773        let s = Sudoku::default();
774        assert!(s.cells.iter().all(|&v| v == 0));
775    }
776
777    // ── L5: Batch completeness ───────────────────────────────────────
778
779    #[test]
780    fn l5_batch_hard_puzzles() {
781        let corpus = [
782            ("Al Escargot",
783             "100007060900020008080500000000305070020010000800000400004000000000460010030900005"),
784            ("Hardest 2012",
785             "800000000003600000070090200050007000000045700000100030001000068008500010090000400"),
786            ("Platinum Blonde",
787             "000000012000000003002300400001800005060000070004000600000050090000200001000000000"),
788            ("Norvig hard",
789             "400000805030000000000700000020000060000080400000010000000603070500200000104000000"),
790            ("Classic easy",
791             "003020600900305001001806400008102900700000008006708200002609500800203009005010300"),
792        ];
793        for (name, puzzle) in &corpus {
794            let mut s: Sudoku = puzzle.parse()
795                .unwrap_or_else(|e| panic!("{}: parse error: {}", name, e));
796            assert!(s.solve(),               "{}: no solution", name);
797            assert!(is_valid_solution(&s.cells), "{}: invalid solution", name);
798            assert_clues_preserved(puzzle, &s);
799            assert!(s.is_solved(),           "{}: cells not all filled", name);
800            assert!(s.bitboard_matches_cells(), "{}: bitboard mismatch", name);
801        }
802    }
803}
sudoku/lib.rs

sudoku/
lib.rs
