Sudoku Verifier

[ainwood]

Hello! I'm relatively new to Rust, and have mostly been working in C. I'd be happy to have some feedback on some code I wrote.

I wrote a program to verify Sudoku solutions. One of my favourite features of Rust is iterators, so my goal was to write a verifier that iterates over rows, columns, and squares, and verifies that each contains the numbers 1-9. Doing it this way, I can treat rows, column, and squares the same.

use std::collections::HashSet;
use std::io;
use std::io::prelude::*;

const WIDTH : usize = 9;
const GRID_SIZE : usize = WIDTH * WIDTH;

pub struct Sudoku {
    grid: [i32; WIDTH * WIDTH]
}

impl Sudoku {
    pub fn new() -> Sudoku {
        Sudoku {
            grid: [0; GRID_SIZE]
        }
    }

    pub fn get_row_iter(&self, idx: usize) -> impl Iterator<Item = &i32>  {
        let slice = &self.grid[WIDTH * idx ..];
        slice.iter().take(WIDTH)
    }

    pub fn get_col_iter(&self, idx: usize) -> impl Iterator<Item = &i32>  {
        let slice = &self.grid[idx..];
        slice.iter().step_by(WIDTH)
    }

    pub fn get_square_iter(&self, idx: usize) -> impl Iterator<Item = &i32> {
        let idx1 = (idx / 3) * 3 * WIDTH + (idx % 3) * 3;
        let idx2 = idx1 + WIDTH;
        let idx3 = idx2 + WIDTH;
        let it1 = self.grid[idx1..].iter().take(3);
        let it2 = self.grid[idx2..].iter().take(3);
        let it3 = self.grid[idx3..].iter().take(3);

        it1.chain(it2.chain(it3))
    }

    pub fn as_rows(&self) -> Vec<impl Iterator<Item = &i32>> {
        let v : Vec<usize> = (0..WIDTH).collect();
        v.iter().map( |&i| self.get_row_iter(i) ).collect()
    }

    pub fn as_cols(&self) -> Vec<impl Iterator<Item = &i32>> {
        let v : Vec<usize> = (0..WIDTH).collect();
        v.iter().map( |&i| self.get_col_iter(i) ).collect()
    }

    pub fn as_squares(&self) -> Vec<impl Iterator<Item = &i32>> {
        let v : Vec<usize> = (0..WIDTH).collect();
        v.iter().map( |&i| self.get_square_iter(i) ).collect()
    }

    fn is_section_complete<'a> (it : impl Iterator<Item = &'a i32>) -> bool {
        static VALUES : [i32; WIDTH] = [1,2,3,4,5,6,7,8,9];

        let set1 : HashSet<&i32> = VALUES.iter().collect();
        let set2 : HashSet<&i32> = it.collect();

        set1 == set2
    }

    pub fn is_solved(&self) -> bool {
        for row in self.as_rows() {
            if !Sudoku::is_section_complete(row) { return false }
        }

        for col in self.as_cols() {
            if !Sudoku::is_section_complete(col) { return false }
        }

        for sqr in self.as_squares() {
            if !Sudoku::is_section_complete(sqr) { return false }
        }

        true
    }
}

One of my friends, who is a Python developer, suggested that I could simplify the solution part to iterate over types as well, as in

for as_section in (self.as_rows, self.as_cols, self.as_squares)

But I struggled with this, because the row, column, and square iterators have different types. I'd welcome any feedback, as well as ideas on how to implement iterating over types.

[2e71828]

@ainwood

I'd welcome any ... ideas on how to implement iterating over types

You can use dynamic dispatch to store different types of iterator inside the same Vec, and then iterate over it only once. For example,

fn main() {
   let vals:Vec<u32> = vec![1,2,3,4,5,6,7,8,9];
   let mut iters:Vec<Box<dyn Iterator<Item=u32>>> = vec![];

   iters.push(Box::new(vals.iter().copied()));
   iters.push(Box::new(vals.iter().copied().filter(|x| x % 3 == 0)));

   for it in iters {
      println!("{:?}", it.collect::<Vec<_>>()) ;
   }
}

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[3, 6, 9]

[alice]

I don't think dynamic dispatch like that improves the solution, though.

[raidwas]

I think your current code is fine, but if it bothers you to have the same code three times (the if in the for loops), you could create a function that takes an arbitrary iterator and iterates over it. Then you would just have to call the function three times.

[parasyte]

Something like this?

    pub fn is_solved(&self) -> bool {
        let rows = self.as_rows().into_iter().all(Sudoku::is_section_complete);
        let cols = self.as_cols().into_iter().all(Sudoku::is_section_complete);
        let squares = self.as_squares().into_iter().all(Sudoku::is_section_complete);

        rows && cols && squares
    }

[CAD97]

Disclaimer: this aggressively refactors the code eventually into a drastically new shape and uses some more advanced features in the name of making things "better" in ways that don't really apply to a small-scale toy solver and only really conditionally applicable in larger codebases, depending on what properties are desired where.

Honestly, your code is fine, and exceptionally clear about what its doing and how its doing it. At a point, my aggressive refactoring gets in the way of that clarity to show off some clever techniques that might be more applicable in other cases. Clarity and cleverness is a tradeoff, and you've honestly hit a pretty good balance here!

---

I'd personally suggest going more iterator!

You're collecting where you don't have to. For example, you can rewrite

    pub fn as_rows(&self) -> Vec<impl Iterator<Item = &i32>> {
        let v : Vec<usize> = (0..WIDTH).collect();
        v.iter().map( |&i| self.get_row_iter(i) ).collect()
    }

as

    pub fn as_rows(&self) -> Vec<impl Iterator<Item = &i32>> {
        (0..WIDTH).map( |i| self.get_row_iter(i) ).collect()
    }

and similarly for as_cols and as_squares. If you want to go even further, you can remove the remaining collect as well:

    pub fn as_rows(&self) -> impl '_ + Iterator<Item=impl Iterator<Item = &i32>> {
        (0..WIDTH).map( move |i| self.get_row_iter(i) )
    }

The '_ + here just notes that the return type borrows from the input, so you cannot modify the Sudoku while holding onto the as_rows iterator. (The expanded signautre would be fn as_rows<'a>(&'a self) -> impl 'a + ....)

The move is required to the &self into the closure, because otherwise the compiler tries to reborrow from it again (unsuccessfully, as we're trying to return it).

---

To go even further beyond, you can use iterator adapters to further obfuscate compress is_solved as well. Specifically, Iterator::all.

    pub fn is_solved(&self) -> bool {
        self.as_rows().all(Sudoku::is_section_complete)
            && self.as_cols().all(Sudoku::is_section_complete)
            && self.as_squares().all(Sudoku::is_section_complete)
    }

This is a very functional approach to this method, and it's mostly a matter of taste if you prefer this or the more imperative way of spelling the checks here. But it does read quite similarly to prose here, if in an odd order.

---

Minor naming nit: by common rust conventions, accessors are just named the property that they are accessing. So get_row_iter => row, and as_rows => rows.

Additionally, since sudoku squares only need to hold numerals 0 through 9, you can store grid numbers as u8 instead of i32 to save a bit of space. (Specifically, Sudoku goes from 324 bytes to 81 bytes.)

You can use Iterator::copied to easily go from an iterator of type &T to an iterator of T (for trivially copiable types like numerics). This will require putting a '_ lifetime on the iterator return value themselves, however, as they are no longer implicitly bound to that lifetime.

---

The final thing I might suggest is to rewrite is_section_complete to avoid the HashMap. We've gotten rid of all the other collects into heap allocated types, and we can get rid of this one too with a clever fixed-space counting trick:

    fn is_section_complete(it: impl Iterator<Item = u8>) -> bool {
        let mut seen = [0; 9];
        for num in it {
            seen[num as usize] += 1; // panics if numbers greater than 9 are present!
        }
        seen.iter().all(|&count| count == 1)
    }

Any further tweaking would be overengineering much more than I already have, so I'll leave it there.

[TomP]

Your "so I'll leave it there" is just about perfect. The only addition I'd make, which I saw on first reading, would be replacing

@ainwood

pub struct Sudoku {
    grid: [i32; WIDTH * WIDTH]

with

pub struct Sudoku {
    grid: [i32; GRID_SIZE]

since the grid size is defined as WIDTH * WIDTH immediately before the struct declaration. But I suppose eliminating that redundancy (with its potential for error) is primarily a matter of taste.

[ainwood]

Thanks for the detailed response!
My original intent was to have iterators of iterators like what you did, but I couldn't figure out how to make that work so I went with a vector of iterators. Looking at what you did with anonymous lifetimes, I can't say I find it intuitive, but I guess that comes with experience. Can you point me to any other good examples of using anonymous lifetimes?

I like your functional solution, I could use that even with a vector of iterators.

Also what you did for is_section_complete is what I would have done in C, but I wanted to play with some Rust features.