Monadic Sudoku Solver


#1

Hello!

I coded along a nice article series describing an Haskell implementation of a Sudoku solver. I also applied a tutorial on Rust profiling to guide my implementation, and as a result my code is ~33 times faster than the original.

Yet, I am a bit surprised about the 3-fold multiplication in code size. Moreover, in many places I chose to move or pass the values by reference to minimise the amount of copying, without really knowing the best practices and I feel like it is a bit all over the place.

Altough I liked that the monadic operations of Haskell translate well into functions like Option::or_else and Option::and_then, a nice Haskell implementation probably doesn’t translate directly to a nice Rust implementation, which is why I would be very interested by a quick code review, if someone would be kind enough to have a glance at it and point me at obvious points of improvement, either towards performance or best practices.

Thank you!


#2

enum Cell { Fixed(u16), Possible(u16) }

That takes 32 bits, have you tried to represent the Fixed/Possible with just one of the bits of the u16 to see if this improves the performance a bit? Probably it doesn’t improve performance.

let mut grid = [[Cell::Possible((1<<9) - 1); 9]; 9];

Isn’t it a good idea to use a Cell::new() (and generally to handle Cell only with its methods)?

Grid::transpose(&self) and Grid::blocks(&self): are normal loops too much slow here?