Part my Sudoku Board Generation Series:
- Part 1: Structure & Algorithm
- Part 2: Implementation Comparison
- Part 3: Rust for WebAssembly
- Part 4: C++ for WebAssembly
Nothing is more doomed than a follow up to a blog post with “Part 1” in the title. It took over a year, but I was able to avoid this embarrassment and finally got around to part two.
This article compares and contrasts three implementations of the Sudoku board generator I wrote about previously. I outline a few differences between TypeScript, Rust, and C++ implementations. C++ and Rust were chosen because it’s relatively easy to build those for Web Assembly (will cover in a later post). And Typescript is serving as a performance baseline.
You can find the repositories here:
Subtask Differences
As outlined in my previous post, two major subtasks of generating the boards are: creating related nodes that represent board location, and filling the cells recursively.
Generating Neighbors
Somewhat surprisingly, the Rust and C++ implementations were a little simpler than the TypeScript versions. The key difference between is the use of the support for user-defined types by standard library data structures and algorithms.
The Set data structure ensures that no two equivalent values are contained within the set. So if we add a duplicate cell, it is ignored. TypeScript has a Set class. However, the equality operation used can’t be customized for a user-defined type. It’s not quite ===`, however for most values it simplest to think that way.
C++ and Rust sets, by contrast, do allow for some customization. The C++ implementation accomplishes this by overloading the == and < operators between two Coord structs.
1
2
3
4
5
6
7
8
9
10
struct coord {
int i = 0;
int j = 0;
};
inline bool operator == (const coord &lhs, const coord &rhs) {
return lhs.i == rhs.i && lhs.j == rhs.j;
}
inline bool operator < (const coord &lhs, const coord &rhs) {
return lhs.i < rhs.i || (lhs.i == rhs.i && lhs.j < rhs.j);
}
The Rust implementation does this by applying some macros to the structsCoord. It’s fairly simple to do and saves us a lot of additional work of sorting and filtering the arrays.
1
2
3
4
5
6
7
8
9
10
struct coord {
int i = 0;
int j = 0;
};
inline bool operator == (const coord &lhs, const coord &rhs) {
return lhs.i == rhs.i && lhs.j == rhs.j;
}
inline bool operator < (const coord &lhs, const coord &rhs) {
return lhs.i < rhs.i || (lhs.i == rhs.i && lhs.j < rhs.j);
}
Another smaller difference in Rust and C++ favor is that being able to use int and usize for the coordinates, in C++ and Rust respectively, made the use of floor operation unnecessary. In TypeScript is use the Number type which includes decimals, so the Math.floor operation is required. The following snippets show how the top left block position is identified in the three implementations.
1
2
3
// identify block top left
const iBase = Math.floor(position.i / BOARD_SIZE) * BOARD_SIZE;
const jBase = Math.floor(position.j / BOARD_SIZE) * BOARD_SIZE;
1
2
3
// find the top left block position
let i_floor = (pos_i / board_config.size) * board_config.size;
let j_floor = (pos_j / board_config.size) * board_config.size;
1
2
3
// find the block top left coordinate
auto iFloor = (pos.i / BOARD_SIZE) * BOARD_SIZE;
auto jFloor = (pos.j / BOARD_SIZE) * BOARD_SIZE;
Filling the Board
All three implementations use the recursive algorithm outlined in the previous post. So the implementations are mostly the same. Rust is a bit different due to it’s more restrictive memory rules. Rust has unique restrictions on references and borrowing. These restrictions allow guarantees of memory safety without having a garbage collector and help prevent some classes of memory errors in multi-threaded programs.
The primary restriction with regards to filling our Sudoku board is that only one reference to a mutable value is allowed at any one time. This makes the recursive algorithm a little more complicated because we can’t pass a mutable reference to the recursive step.
In particular, the member cell.neighbors could not be accessed directly by the function SudokuBoard::doFillCells Instead they needed to be cloned, fortunately, this is trivial.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#[derive(Clone, Hash, Eq, PartialEq, PartialOrd)]
struct Coord {
i: usize,
j: usize
}
struct SudokuCell {
neighbors: Vec<Coord>
}
struct SudokuBoard {
cells: Vec<SudokuCell>,
}
impl SudokuBaord {
fn neighbors(&self, coord: &Coord) -> Vec<Coord> {
let index = coord_to_index(coord, &self.board_config);
let ref cell = self.cells.get(index).unwrap();
cell.neighbors.clone()
}
}
The Clone macro enables the cell.neighbors vector to be cloned as a full collection. This makes the memory restrictions less honorous at a source code level, though figuring out this solution was a bit of a pain. In my opinion, the reference, ownership and borrowing rules represent the biggest obstacle for learning / working with Rust.
Having data structures and algorithms that support user-defined types also made filling the board a bit simpler. A sub-operation is figuring out what options are available for the current cell given the neighbor values. The TypeScript implementation, using lodash, is a little unnatural.
1
2
neighborValues = _sortedUniq(neighborValues);
const remainingOptions = _difference(validValues, neighborValues);
It’s not too verbose, but it requires two separate operations to perform a set difference. First, all the neighbor values have to be sorted uniquely, and then the difference can be taken. The lodash difference operation requires the elements to be in order, and unique. If there are duplicates, then there will be remaining instances.
In C++ and Rust versions are more straightforward.
1
2
3
4
5
6
std::vector<int> options;
set_difference(
VALID_VALUES.begin(), VALID_VALUES.end(),
neighborValues.begin(), neighborValues.end(),
std::inserter(options, options.begin())
);
1
2
3
4
5
// get remaining values and shuffle them
let mut remaining_values: Vec<u64> = self.valid_values
.difference(&neighbor_values)
.cloned()
.collect();
The Rust version is easy to parse, while the C++ version might look a little funky if you are unfamiliar with the argument order of STL algorithm functions and iterators. However, both allow the desired operation to be expressed directly as set operations.
It would be possible to implement a set difference operation that worked as expected with TypeScript arrays, but that’s the point. These operations are part of the Rust and C++ standard library and have high-quality implementations.
Conclusion
Despite having more experience writing Typescript, I found it more straightforward to implement what I wanted in C++. Set support for user-defined types, STL algorithms, and having more than a single number type allowed the program to be more expressive. The Rust implementation was a little frustrating due mostly to the most restrictive memory rules.