sudoku/
sudoku.rs

1use sol::{score, solve, Error as SolveError};
2use Puzzle;
3use Score;
4use Solve;
5use DIMENSIONS;
6
7use std::{
8    fmt, ops::{Index, IndexMut}, str::FromStr,
9};
10
11/// Represents a single sudoku "square."
12///
13/// The quantum of the sudoku.
14#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
15pub struct Element(pub u8);
16
17/// A subdivision of the main sudoku; the smallest grouping to which rules are applied.
18#[derive(Clone, Debug)]
19pub enum Group {
20    /// A square set of [elements](struct.Element.html).
21    ///
22    /// A subdivision of a [sudoku](struct.sudoku.html).
23    ///
24    /// ### Rule
25    /// Each box may contain each element value only once.
26    Box(Vec<Option<Element>>),
27    /// A vertical set of [elements](struct.Element.html).
28    ///
29    /// A subdivision of a [sudoku](struct.sudoku.html).
30    ///
31    /// ### Rule
32    /// Each stack may contain each element value only once.
33    Stack(Vec<Option<Element>>),
34    /// A horizontal set of [elements](struct.Element.html).
35    ///
36    /// A subdivision of a [sudoku](struct.sudoku.html).
37    ///
38    /// ### Rule
39    /// Each band may contain each element value only once.
40    ///
41    /// ### Dimensionality
42    /// In *n* dimensions, `n - 1` bands apply to each element.
43    /// Each is linearly independent from the others and from the relevant stack.
44    Band(Vec<Option<Element>>),
45}
46
47impl Group {
48    /// Whether a group is valid (contains no errors).
49    ///
50    /// A group is considered valid if it contains only unique elements
51    /// (ignoring empty elements).
52    pub fn is_valid(&self) -> bool {
53        let elements = self.elements();
54        let elements = elements.iter().filter(|e| e.is_some()).collect::<Vec<_>>();
55        let len = elements.len();
56        let mut elements = elements.into_iter().collect::<Vec<_>>();
57        elements.sort();
58        elements.dedup();
59        elements.len() == len
60    }
61    /// Whether a group is complete.
62    ///
63    /// A group is considered complete if it contains every possible element
64    /// value exactly once.
65    pub fn is_complete(&self) -> bool {
66        let elements = self.elements();
67        let len = elements.len();
68        let mut elements = elements
69            .into_iter()
70            .filter(|e| e.is_some())
71            .collect::<Vec<_>>();
72        elements.sort();
73        elements.dedup();
74        elements.len() == len
75    }
76    /// Returns an owned copy of the group's constituent elements.
77    pub fn elements(&self) -> Vec<Option<Element>> {
78        use self::Group::*;
79        match self {
80            Box(elements) | Stack(elements) | Band(elements) => elements.clone(),
81        }
82    }
83}
84
85impl Default for Group {
86    fn default() -> Self {
87        Group::Box(vec![])
88    }
89}
90
91#[derive(Clone, Debug, PartialEq)]
92/// A (partial) grid of [elements](struct.Element.html).
93pub struct Sudoku {
94    /// The [order](trait.Puzzle.html#method.order) of this sudoku.
95    pub order: u8,
96    /// The [elements](struct.Element.html) composing this sudoku.
97    pub elements: Vec<Option<Element>>,
98}
99
100/// Specifies a sudoku element's location in space.
101///
102/// The point is fully specified in `DIMENSIONS` dimensions.
103///
104/// # Coordinate System
105/// The coordinate system used in this library sets the origin in the top-left
106/// corner, with increasing x to the right and increasing y downward.
107///
108/// Additional axes (if applicable) follow the right-hand rule.
109#[derive(Copy, Clone, Debug, PartialEq)]
110pub struct Point([u8; DIMENSIONS]);
111impl Point {
112    /// Compresses an *n*-dimensional point to a single coordinate.
113    ///
114    /// Inverse of [`Point::unfold`](#method.unfold).
115    pub fn fold(&self, order: u8) -> usize {
116        let axis = (order as usize).pow(2);
117        let mut sum = 0;
118        for i in 0..DIMENSIONS {
119            sum += (self[i] as usize) * axis.pow(i as u32);
120        }
121        sum
122    }
123
124    /// Decompresses a single coordinate into an *n*-dimensional point.
125    ///
126    /// Inverse of [`Point::fold`](#method.fold).
127    pub fn unfold(value: usize, order: u8) -> Self {
128        let mut total = value;
129        let axis = (order as usize).pow(2);
130        let mut point = [0; DIMENSIONS];
131        for i in 0..DIMENSIONS {
132            let j = DIMENSIONS - i - 1;
133            let discriminant = axis.pow(j as u32);
134            let dim = total / discriminant;
135            point[j] = dim as u8;
136            total = total % discriminant;
137        }
138        Point(point)
139    }
140
141    /// Snaps a point to the grid (returns the upper-left corner of the box).
142    pub fn snap(self, order: u8) -> Self {
143        let mut point = self;
144        for i in 0..DIMENSIONS {
145            point[i] = self[i] - self[i] % order;
146        }
147        point
148    }
149
150    /// Creates a point with the given x-coordinate and all other coordinates zero.
151    pub fn with_x(value: u8) -> Self {
152        let mut point = [0; DIMENSIONS];
153        point[0] = value;
154        Point(point)
155    }
156
157    /// Creates a point with the given y-coordinate and all other coordinates zero.
158    pub fn with_y(value: u8) -> Self {
159        let mut point = [0; DIMENSIONS];
160        point[1] = value;
161        Point(point)
162    }
163
164    #[cfg(feature = "3D")]
165    /// Creates a point with the given z-coordinate and all other coordinates zero.
166    pub fn with_z(value: u8) -> Self {
167        let mut point = [0; DIMENSIONS];
168        point[2] = value;
169        Point(point)
170    }
171
172    /// The point with all coordinates identically zero.
173    pub fn origin() -> Self {
174        Point([0; DIMENSIONS])
175    }
176}
177
178impl Index<usize> for Point {
179    type Output = u8;
180    fn index(&self, index: usize) -> &Self::Output {
181        &self.0[index]
182    }
183}
184
185impl IndexMut<usize> for Point {
186    fn index_mut(&mut self, index: usize) -> &mut u8 {
187        &mut self.0[index]
188    }
189}
190
191impl fmt::Display for Point {
192    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
193        write!(f, "(")?;
194        for i in 0..DIMENSIONS - 1 {
195            write!(f, "{}, ", self[i])?;
196        }
197        write!(f, "{})", self[DIMENSIONS - 1])
198    }
199}
200
201/// Represents an *n*-dimensional grid of values, indexable via [`Point`](struct.Point.html).
202pub trait Grid: Index<Point> {
203    /// Returns all points in the grid.
204    ///
205    /// Useful for enumeration with `Iterator::zip`.
206    fn points(&self) -> Vec<Point>;
207}
208
209impl Sudoku {
210    /// Constructs a new sudoku of the specified order.
211    ///
212    /// This method reserves space in memory for the puzzle's elements.
213    ///
214    /// # Notes
215    /// This method **does not** generate a valid, uniquely solvable sudoku.
216    /// If you wish to generate such a sudoku (which you likely do), use
217    /// [`Sudoku::generate`](#method.generate).
218    pub fn new(order: u8) -> Self {
219        Self {
220            order,
221            elements: vec![None; (order as usize).pow(2 + DIMENSIONS as u32)],
222        }
223    }
224
225    /// Returns whether the puzzle is completely full of values.
226    pub fn is_complete(&self) -> bool {
227        for point in self.points() {
228            if self[point].is_none() {
229                return false;
230            }
231        }
232        true
233    }
234
235    /// Returns the relevant groups for checking a given element in the grid.
236    ///
237    /// The number of groups is always equal to the number of dimensions plus
238    /// one.
239    pub fn groups(&self, pos: Point) -> [Group; DIMENSIONS + 1] {
240        for i in 0..DIMENSIONS {
241            assert!(pos[i] < self.order.pow(2));
242        }
243        let top_left = pos.snap(self.order);
244        let order = self.order as i32;
245        let points = self.points();
246        let b = points
247            .iter()
248            .zip(self.elements.iter())
249            .filter(|(index, _)| {
250                let y = index[1];
251                let x = index[0];
252                let dy = y as i32 - top_left[1] as i32;
253                let dx = x as i32 - top_left[0] as i32;
254                if dy < 0 || dx < 0 || dy >= order || dx >= order {
255                    return false;
256                }
257                true
258            })
259            .map(|(_, v)| *v)
260            .collect::<Vec<_>>();
261        let b = Group::Box(b);
262
263        let s = points
264            .iter()
265            .zip(self.elements.iter())
266            .filter(|(index, _)| {
267                if index[0] != pos[0] {
268                    return false;
269                }
270                for i in 2..DIMENSIONS {
271                    if index[i] != pos[i] {
272                        return false;
273                    }
274                }
275                true
276            })
277            .map(|(_, v)| *v)
278            .collect::<Vec<_>>();
279        let s = Group::Stack(s);
280        let bands = (1..DIMENSIONS)
281            .map(|i| {
282                // The variant dimension
283                let dimension = i - 1;
284                points
285                    .iter()
286                    .zip(self.elements.iter())
287                    .filter(|(index, _)| {
288                        for j in 0..DIMENSIONS {
289                            if j == dimension {
290                                continue;
291                            }
292                            if pos[j] != index[j] {
293                                return false;
294                            }
295                        }
296                        true
297                    })
298                    .map(|(_, v)| *v)
299                    .collect()
300            })
301            .map(|v| Group::Band(v))
302            .collect::<Vec<_>>();
303        let mut g = bands;
304        g.insert(0, s);
305        g.insert(0, b);
306        // Here be dragons (not really, but update this when 1.27 gets stabilized)
307        clone_into_array(&g[..=DIMENSIONS])
308    }
309
310    /// Places the specified value (or lack thereof) at the specified index,
311    /// returning an owned copy.
312    pub fn substitute(&self, index: Point, value: Option<Element>) -> Self {
313        let mut elements = self.elements.clone();
314        let order = self.order;
315        elements[index.fold(order)] = value;
316        Self { elements, order }
317    }
318}
319
320impl Grid for Sudoku {
321    fn points(&self) -> Vec<Point> {
322        (0..(self.order as usize).pow(2 + DIMENSIONS as u32))
323            .map(|p| Point::unfold(p, self.order))
324            .collect()
325    }
326}
327
328// https://stackoverflow.com/a/37682288
329fn clone_into_array<A, T>(slice: &[T]) -> A
330where
331    A: Default + AsMut<[T]>,
332    T: Clone,
333{
334    let mut a = Default::default();
335    <A as AsMut<[T]>>::as_mut(&mut a).clone_from_slice(slice);
336    a
337}
338
339impl Index<Point> for Sudoku {
340    type Output = Option<Element>;
341    fn index(&self, index: Point) -> &Self::Output {
342        &self.elements[index.fold(self.order)]
343    }
344}
345
346impl Puzzle for Sudoku {
347    fn order(&self) -> u8 {
348        self.order
349    }
350}
351
352impl Solve for Sudoku {
353    fn solution(&self) -> Result<Self, SolveError> {
354        solve(self)
355    }
356}
357
358impl Score for Sudoku {
359    fn score(&self) -> Option<usize> {
360        score(self)
361    }
362}
363
364#[cfg(feature = "2D")]
365impl fmt::Display for Sudoku {
366    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
367        let order = self.order;
368        let axis = order.pow(2);
369        for y in 0..axis {
370            for x in 0..axis {
371                let element = self[Point([x, y])];
372                match element {
373                    Some(Element(value)) => {
374                        write!(f, "{}", value)?;
375                    }
376                    None => {
377                        write!(f, "_")?;
378                    }
379                }
380                if x != axis - 1 {
381                    write!(f, " ")?;
382                }
383            }
384            write!(f, "\n")?;
385        }
386        Ok(())
387    }
388}
389
390/// Represents a deserialization error.
391#[derive(Clone, Copy, Debug)]
392pub enum ParseError {
393    /// Represents a grid with differing width and height.
394    UnequalDimensions,
395    /// Represents the presence of a value too large for the puzzle's dimensions.
396    ///
397    /// The associated values are the large value and its would-be location in the puzzle.
398    LargeValue(u8, Point),
399    /// Represents a grid with a non-perfect-square axial length.
400    NonSquareAxis,
401}
402
403// TODO((#7): Higher dimensions
404#[cfg(feature = "2D")]
405impl FromStr for Sudoku {
406    type Err = ParseError;
407    fn from_str(s: &str) -> Result<Self, Self::Err> {
408        let mut rows = s
409            .split("\n")
410            .map(|row| {
411                row.split(" ")
412                    .map(|cell| cell.parse().ok().map(|value| Element(value)))
413                    .collect::<Vec<_>>()
414            })
415            .collect::<Vec<_>>();
416        let order = (rows.len() as f64).sqrt() as usize;
417        if rows.len() == order * order + 1 {
418            let last = rows.pop().unwrap();
419            if last.len() != 1 || last[0] != None {
420                return Err(ParseError::NonSquareAxis);
421            }
422        }
423        let axis = rows.len();
424        if order * order != axis {
425            return Err(ParseError::NonSquareAxis);
426        }
427        let mut elements = Vec::with_capacity(axis.pow(2));
428        for j in 0..axis {
429            let row = &rows[j];
430            if row.len() != axis {
431                return Err(ParseError::UnequalDimensions);
432            }
433            for i in 0..axis {
434                if let Some(Element(value)) = row[i] {
435                    if value > axis as u8 {
436                        return Err(ParseError::LargeValue(value, Point([i as u8, j as u8])));
437                    }
438                }
439                elements.push(row[i]);
440            }
441        }
442        Ok(Sudoku {
443            order: order as u8,
444            elements,
445        })
446    }
447}
448
449#[cfg(test)]
450mod tests {
451    use sudoku::{Element, Group, Point, Sudoku};
452    use Puzzle;
453    use DIMENSIONS;
454
455    // TODO(#9): Procedural macro-ify these tests
456    // TODO(#8): Implement positive tests for Sudoku::groups
457    #[test]
458    #[should_panic]
459    fn test_sudoku_groups_index_x_3() {
460        let sudoku = Sudoku::new(3);
461        let _ = sudoku.groups(Point::with_x(9));
462    }
463
464    #[test]
465    #[should_panic]
466    fn test_sudoku_groups_index_y_3() {
467        let sudoku = Sudoku::new(3);
468        let _ = sudoku.groups(Point::with_y(9));
469    }
470
471    #[test]
472    #[should_panic]
473    fn test_sudoku_groups_index_x_4() {
474        let sudoku = Sudoku::new(4);
475        let _ = sudoku.groups(Point::with_x(16));
476    }
477
478    #[test]
479    #[should_panic]
480    fn test_sudoku_groups_index_y_4() {
481        let sudoku = Sudoku::new(4);
482        let _ = sudoku.groups(Point::with_y(16));
483    }
484
485    #[test]
486    fn test_sudoku_groups_length_3_2d() {
487        let sudoku = Sudoku::new(3);
488        let groups = sudoku.groups(Point::origin());
489        assert_eq!(groups[0].elements().len(), 3_usize.pow(DIMENSIONS as u32));
490        assert_eq!(groups[1].elements().len(), 9);
491        assert_eq!(groups[2].elements().len(), 9);
492    }
493
494    #[test]
495    fn test_sudoku_groups_length_4_2d() {
496        let sudoku = Sudoku::new(4);
497        let groups = sudoku.groups(Point::origin());
498        assert_eq!(groups[0].elements().len(), 4_usize.pow(DIMENSIONS as u32));
499        assert_eq!(groups[1].elements().len(), 16);
500        assert_eq!(groups[2].elements().len(), 16);
501    }
502
503    #[test]
504    fn test_sudoku_new() {
505        for order in 2..10usize {
506            let sudoku = Sudoku::new(order as u8);
507            assert_eq!(sudoku.elements.capacity(), order.pow(2 + DIMENSIONS as u32));
508        }
509    }
510
511    #[test]
512    fn test_group_is_valid() {
513        let group = Group::Box(vec![]);
514        assert!(group.is_valid());
515        let group = Group::Box(vec![Some(Element(1)), Some(Element(1))]);
516        assert!(!group.is_valid());
517    }
518
519    #[test]
520    fn test_group_is_complete() {
521        for vec in [vec![], vec![Some(Element(1)), Some(Element(2))]].into_iter() {
522            let group = Group::Box(vec.clone());
523            assert!(group.is_complete());
524        }
525        let group = Group::Box(vec![Some(Element(1)), Some(Element(1))]);
526        assert!(!group.is_complete());
527    }
528
529    #[test]
530    fn test_group_elements() {
531        for vec in [vec![], vec![Some(Element(2)), Some(Element(6)), None]].into_iter() {
532            let group = Group::Box(vec.clone());
533            assert_eq!(&group.elements(), vec);
534        }
535    }
536
537    #[test]
538    fn test_sudoku_order() {
539        for order in 1..10 {
540            let sudoku = Sudoku::new(order);
541            assert_eq!(sudoku.order(), order);
542        }
543    }
544
545    #[cfg_attr(feature = "2D", test)]
546    #[cfg(feature = "2D")]
547    fn test_point_compose() {
548        for i in 0..9 {
549            for j in 0..9 {
550                let point = Point([i, j]);
551                assert_eq!(point, Point::unfold(point.fold(3), 3));
552            }
553        }
554        for i in 0..16 {
555            for j in 0..16 {
556                let point = Point([i, j]);
557                assert_eq!(point, Point::unfold(point.fold(4), 4));
558            }
559        }
560    }
561
562    #[cfg_attr(feature = "2D", test)]
563    #[cfg(feature = "2D")]
564    fn test_point_index() {
565        for i in 0..9 {
566            for j in 0..9 {
567                let point = Point([i, j]);
568                assert_eq!(point.0[0], point[0]);
569            }
570        }
571    }
572
573    #[cfg_attr(feature = "2D", test)]
574    #[cfg(feature = "2D")]
575    fn test_point_index_mut() {
576        for i in 0..9 {
577            for j in 0..9 {
578                let mut point = Point([i, j]);
579                point[0] = j;
580                point[1] = i;
581                assert_eq!(point[0], j);
582                assert_eq!(point[1], i);
583            }
584        }
585    }
586
587    #[cfg_attr(feature = "2D", test)]
588    #[cfg(feature = "2D")]
589    fn test_point_snap() {
590        for i in 0..9 {
591            for j in 0..9 {
592                let x = match i {
593                    0...2 => 0,
594                    3...5 => 3,
595                    6...8 => 6,
596                    _ => unreachable!(),
597                };
598                let y = match j {
599                    0...2 => 0,
600                    3...5 => 3,
601                    6...8 => 6,
602                    _ => unreachable!(),
603                };
604                let point = Point([i, j]);
605                assert_eq!(point.snap(3), Point([x, y]));
606            }
607        }
608        for i in 0..16 {
609            for j in 0..16 {
610                let x = match i {
611                    0...3 => 0,
612                    4...7 => 4,
613                    8...11 => 8,
614                    12...15 => 12,
615                    _ => unreachable!(),
616                };
617                let y = match j {
618                    0...3 => 0,
619                    4...7 => 4,
620                    8...11 => 8,
621                    12...15 => 12,
622                    _ => unreachable!(),
623                };
624                let point = Point([i, j]);
625                assert_eq!(point.snap(4), Point([x, y]));
626            }
627        }
628    }
629    #[cfg_attr(rustfmt, rustfmt_skip)]
630    #[cfg_attr(feature = "2D", test)]
631    #[cfg(feature = "2D")]
632    fn test_sudoku_from_str() {
633        let possible = [
634            include_str!("../tests/sudokus/solvable/2D-O3.txt"),
635            include_str!("../tests/sudokus/solvable/2D-O4.txt"),
636        ];
637        for s in possible.iter() {
638            let puzzle = s.parse::<Sudoku>();
639            assert!(puzzle.is_ok());
640        }
641        let impossible = [
642            include_str!("../tests/sudokus/invalid/2D-O3.txt"),
643            include_str!("../tests/sudokus/invalid/2D-O4.txt"),
644        ];
645        for s in impossible.iter() {
646            let puzzle = s.parse::<Sudoku>();
647            assert!(puzzle.is_err());
648        }
649    }
650
651    #[cfg_attr(rustfmt, rustfmt_skip)]
652    #[cfg_attr(feature = "2D", test)]
653    #[cfg(feature = "2D")]
654    fn test_sudoku_from_str_parse_compose() {
655        let s = include_str!("../tests/sudokus/solvable/2D-O3.txt");
656        let puzzle = s.parse::<Sudoku>();
657        assert!(puzzle.is_ok());
658        assert_eq!(&format!("{}", puzzle.unwrap()), s);
659    }
660}
sudoku/sudoku.rs

sudoku/
sudoku.rs
