This is a continuation of research into Prof. Knuth's Algorithm X, and an attempt to learn Rust at the same time. I've started the research by implementing the algorithm with Dancing Links. That did work well in C++, but when I tried to port that implementation to Rust I've ran into a number of, let's say, annoyances. The "Dancing Links" approach, as neat as it is, relies on tricks with pointers. Some of those tricks create temporary hanging pointers, something that Rust does not like. It is still implementable, but the implementation would involve creating an another layer of references. There is a crate with that implementation already, so I decided to try something different.
In that C++ repository I've mentioned before there is a smaller test implementation based on a 30-lines Python version. I've given that version another thought, and I would not call it "Dancing Links" at this point - it is still Algorithm X anyway. That's fine, Dancing Links is just an implementation technique, very cool and very fast, but not the only one possible.
So, with that in mind, I've tried to do something similar. It is not a direct line-by-line port (as I tried with C++), but it has a lot in common. It is enhanced with "optional conditions" and "preselected columns" similar to my C++ implementation, as I needed these features for the test problems. It also has a validation code that can catch problem inconsistencies. Most of that is commented in code.
There are a number of tricks I had to resort to. One is the use of RefCell. The way how algorithm works with the sparse matrix, there is a nested loop that goes by row, then by column, then by row again - and it can modify the row at the innermost level. The modification is safe by the algorithm constraints, but there is no way for compiler to identify it as such. The trick here is to wrap the row in RefCell - think of it as pushing borrowing to the execution time; it's not precise, but close enough.
The second trick is more interesting. Rust does not have yield... Well, it has some version of it in unstable, but even that one is not that great. It is possible that the proper yield is fundamentally not implementable within the language constraints. That's where I found a trick that looks like yield, and in certain sense even better for this particular purpose. The way it works - the entire execution of algorithm is offloaded to another thread. Instead of yielding, solutions are being given to sender. The caller just enumerates the receiver, and the code looks really clean.
Of course, it is not a true yield - there are significant semantical differences and the "solution" has to be copied to the sender which can be considered a waste of memory. However, that waste is very small considering the memory use in the entire algorithm. A potential issue of clogging the sender is nicely solved by the Rust implementation (pipe pressure would cause the sender to stall to prevent huge queues). Even better - the algorithm works in parallel to the caller, so in many cases the resulting performance may be improved. Finally, the code does not use any unsafe blocks.
I haven't done proper timing to tell the relative performance of this implementation compared to the C++ - this is still on my TODO list. At this point any measurement would not be a true apples to apples. Unscientific run of my old C++ version with all three problems (Queens, Sudoku, Pentominoes) vs this Rust implementation solving the same problem ended up in a tie - which is, for one, very impressive already, and also may be invalid if the entire test is bound by the screen output peformance. In any case, this means that this implementation is completely viable for practical use.
Another obvious TODO here is to provide a better documentation. I am planning to do a bit more work on the algorihtm before that to make sure the interface is clean and nice. Right now the recommended way of using it is behind a macro. The code samples in main.rs should provide sufficient information if anybody wants to try using it now.